0
  

XXIII Турнир городов
(решения)

Осенний тур, основной вариант, 8-9 классы

Задача 1

Искомый набор: ai = 2100-2100-i. Возрастание последовательности ai очевидно. Докажем, что НОД(ai,ai+1) = 299-i. Действительно, ai = k*2100-i, ai+1 = (2k+1)*299-i, где k = 2i-1 - нечётное число. Числа k и 2k+1 - взаимно простые, поэтому числа ai и ai+1 не имеют общих нечётных простых делителей. А наибольшая их общая степень двойки равна 99-i.

Задача 2

Пусть среди дуг, на которые разбивают окружность данные точки, имеется k дуг длины a, l дуг длины b и m дуг длины c. Дуги, на которые разбивают окружность красные точки, имеют длины a+b, a+c и b+c. Обозначим их количества через x, y и z. Тогда, очевидно, выполняются равенства x+y = k, x+z = l, y+z = m. Решив соответствующую систему, получим выражения для x, y и z через k, l и m. Те же самые значения мы получим и для многоугольника с вершинами в синих точках.

Поскольку равные дуги стягиваются равными хордами, наборы длин сторон красного и синего многоугольников равны (различие может быть лишь в порядке их следования). Значит, периметры многоугольников равны. Кроме того, многоугольники можно дополнить равными наборами сегментов до окружностей. Значит, их площади также равны.

Задача 3

В исходной таблице каждое число встречается по n-2 раза (так как она содержит n-2 строки, в каждой из которой каждое число встречается по разу). Если дописать в каждый столбец по два недостающих числа, каждое число будет встречаться по n раз (тогда "полный набор" будет представлен в каждом из n столбцов). Значит, каждое число будет дописано ровно по два раза.

Выпишем числа от 1 до n и соединим отрезками те номера, которые должны быть дописаны в один столбец. Получим граф с n вершинами, из каждой вершины которого выходит по два ребра. Значит, он является объединением нескольких циклов (длины более единица каждый). Ориентируем граф, нарисовав стрелки в каждом цикле в одном направлении. Тогда из каждого числа будет выходить одна стрелка и в каждое число будет входить одна стрелка. Если из числа выходит стрелка, поместим его в верхнюю из двух возможных строк, а если входит, то в нижнюю. Тогда каждое число по разу окажется в верхней и нижней строке. А это и значит, что в двух дописанных строчках все числа также будут различны.

Задача 4

Стороны треугольников являются либо сторонами, либо диагоналями исходного многоугольника. По крайней мере два треугольника содержат в качестве сторон по две стороны многоугольника (будем называть такие треугольники "малыми". Действительно, треугольников 2n-1, а сторон многоугольника 2n+1, при этом никакой треугольник не может содержать трёх таких сторон. Малые треугольники, очевидно, равнобедренные. Если их не менее трёх, то всё доказано.

Пусть их всего два. Это значит, что любой другой треугольник содержит в качестве ровно одной из своих сторон сторону многоугольника. Иными словами, если его вырезать, то многоугольник распадётся на две части. Будем двигаться от одного из двух малых треугольников к другому, переходя через общие стороны в соседние треугольники. При этом будем следить, сколько сторон исходного многоугольника лежит в одной и второй частях. Вначале эти числа равны 2 и 2n-2. При каждом переходе первое число увеличивается, а второе уменьшается на единицу. В какой-то момент они оба будут равны n, а это значит, что треугольник, в котором мы находимся, является равнобедренным.

Задача 5

Ответ: 63 ладьи.

Покажем сначала, как Саша может поставить 63 ладьи. Сначала заполняются три последовательных клетки a1, a8 и h8. Затем заполняется последовательно первая горизонталь (от b1 до g1) и последнюю вертикаль (от h8 до h2), кроме угловой клетки h1. Затем заполняем вертикали, сначала самую левую от a2 до a7, и наконец остальные вертикали заполняем по очереди снизу вверх.

Теперь докажем, что более 63 ладей поставить невозможно. Действительно, поставить ладьи во все четыре угловых клетки невозможно. Последняя из таких ладей будет бить две ладьи, что противоречит правилам.

Задача 6

Пусть числа записаны на карточках, выложенных в ряд. Будем менять карточки и увеличивать вдвое числа на них. Две карточки, раз поменявшись местами, обратно поменяться не могут. Предположим противное, и выберем пару (A,B), первой поменявшуюся обратно. Ясно, что в промежутке между прямым и обратным обменами была еще хотя бы одна операция с A или B, иначе левое число так и осталось бы меньше правого. Однако карточка, поменявшись с A, попадет между A и B. Снова с A она не менялась - иначе обратный обмен A и B - не первый.

Остаться между A и B она тоже не может - тогда A и B не смогут поменяться. Значит, она поменялась и с B. Но тогда сколько раз эта карточка поменялась с A, столько раз она поменялась и с B, и значит числа A и B увеличились в одно и то же число раз, правое осталось больше левого, и они таки не могли поменяться.

Задача 7

Очевидно, что для любого натурального числа N существует единственная степень двойки 2k такая, что N =< 2k < 2N.

Подставляя в это утверждение вместо N числа 10n-1, 2*10n-1 и 5*10n-1, получаем, что для любого n:
существует ровно одна n-значная степень двойки, десятичная запись которой начинается с цифры 1;
существует ровно одна n-значная степень двойки, десятичная запись которой начинается с цифры 2 или 3;
существует ровно одна n-значная степень двойки, десятичная запись которой начинается с одной из цифр: 5, 6, 7, 8 или 9.

Из этого следует, что ровно 100 выписанных в условии чисел начинаются с единицы (по одному для каждого количества разрядов от 2 до 101), ровно 100 - с двойки или тройки, ровно 100 - с одной из цифр от 5 до 9 (по одному для каждого количества разрядов от 1 до 100). Значит, оставшиеся 33 числа начинаются с четвёрки.

Осенний тур, основной вариант, 10-11 классы

Задача 1

Предположим, что нам удалось разместить все красные и все синие точки на одной окружности. Пусть М центр этой окружности; проведем прямую ОМ. В точке О восставим перпендикуляр к ОМ, получим прямую m. Обозначим за К и L точки пересечения окружности с прямой m. Луч МО пересекает окружность в точке N, а луч ОМ - в точке V.

Так как точка О лежит внутри треугольника с синими вершинами, то на каждой из дуг КNL и KVL есть хотя бы одна синяя точка. То же верно про красные точки. (*)

Докажем теперь, что расстояние от точки О до любой точки на дуге KNL меньше,чем расстояние до любой точки на дуге KVL. Построим на отрезке KL как на диаметре окружность. Ее центром будет точка О. Теперь замечаем, что расстояние до любой точки на дуге KVL больше радиуса построенной окружности, а расстояние до любой точки на дуге KNL меньше этого же радиуса. Отсюда и получаем требуемое утверждение. (**)

А теперь посмотрев на (*) и (**) находим, что в случае нашего предположения найдется синяя точка (на дуге KNL), расстояние до которой меньше, чем до какой-то красной точки (на дуге KVL). Противоречие.

Задача 2

Ответ: существуют. Проведем доказательство индукцией по количеству чисел.

База индукции : два. Очевидно существуют.

Пусть имеется к чисел: а1<...<а_к, для которых выполнено условие задачи.

Возьмем q>p>ak, где q и p - простые числа. Рассмотрим набор из к+1 числа: b1 = p, b2 = q*a1, b3 = q*a2, ... , bk+1 = q*ak. Тогда b12<... ...k+1, так как q*a1>p и q*an+1>q*an.

При этом НОК(bm+2,bm+1) = q*НОК(am+1,am), т.е. для НОК пар (b2,b3), ..., (bk,bk+1) все выполняется (неравенства умножаются на q, а q взаимнопросто с ai).

Далее: НОК(b1,b2) = p*q*a1   и  НОК(b2,b3) = q*НОК(a1,a2)

p*q*a1 > a2*q*a1 >= q*HOK(a1,a2) = НОК(b2,b3) т.к. p>ai

Т.е. НОК(b1,b2)>НОК(b2,b3).

По методу полной математической индукции получаем, что сущечтвует любое, наперед заданое, количество таких чисел, в том числе 100.

Задача 3

Ответ: 88.

Рассмотрим числа на диагонали а12,...,а8; индексы проставлены в том порядке, в котором числа появляются на диагонали. Например расположение может быть таким (а не обязательно по порядку):

а2
    а3
        а1
            ..
                а8
                    а7

Тогда а1>=1, a2>=3, a3>=5, ..., a7>=13. Утверждается, что а8>=39. Действительно, в тот момент, когда мы проходим через последнее поле на диагонали (последнее из тех, на которых мы еще не были), в покидаемой нами половине доски (доска разбивается диагональю на две половины) к этому моменту все поля должны быть уже заставлены числами, так как в противном случае мы уже не сможем на эти поля поставить числа. В итоге получаем а8>=36, т.е. общая сумма >=85.

Докажем, что оценку для восьмого поля можно улучшить до 39. Пусть наша диагональ белого цвета. Будем называть путь ладьи змейкой. Рассмотрим змейку, которая получится при прохождении первой половины доски. Она состоит из строго чередующихся белых и черных клеток. Белых клеток в этой половине доски 12, и еще 8 на диагонали, всего 20. Так как клетки разного цвета чередуются, то черных клеток в этой змейке должно быть не меньше 19. Черных же клеток здесь у нас 16! Т.е. 19-16 = 3 клетки черного цвета должны быть пройдены змейкой во второй половине доски еще до того, как мы закончим обход первой половины. Вот и получаем 3+36 = 39, т.е. а8>=39, и вся сумма >= 88.

Построим пример для 88:

   a  b  c  d  e  f  g  h
  _________________________
1 |  1  2 27 28 29 30 31 32
2 | 64  3 26 25 24 23 22 33
3 | 63  4  5  6 19 20 21 34
4 | 62 61 60  7 18 17 16 35
5 | 57 58 59  8  9 10 15 36
6 | 56 55 54 53 52 11 14 37
7 | 47 48 49 50 51 12 13 38
8 | 46 45 44 43 42 41 40 39
Сумма на диагонали а1...h8 равна 1+3+5+7+9+11+13+39 = 88.

Задача 4

Ответ: 6.

Пусть ABCD - исходный четырехугольник, сторону AB которого при наших преобразованиях будем считать неподвижной. Заметим, что все четырехугольники, содержащиеся в последовательности, имеют одинаковые суммы противолежащих углов. (т.е. для четырехугольника ABKL из последовательности обязательно выполнены равенства А поскольку три величины (эти длины) могут быть упорядочены ровно 3! = 6 способами, то среди любых 7 четырехугольников последовательности найдутся два, у которых порядок длин сторон совпадает.

Докажем, что такие четырехугольники ABKL и ABMN (BK=BM, KL=MN, LA=NA) равны; для этого достаточно установить равенство диагоналей AK=AM. Предположив, например, что AK > AM получим Следовательно, наша последовательность не может содержать более 6-ти попарно неравных прямоугольников.

Приведем пример: возьмем 4 точки на окружности так, чтобы у получившегося четырехугольника все стороны были различны. Очевидно, что в этом случае все четырехугольники будут выпуклые и не выродятся в треугольник. Остается взять следующую перестановку(a,b,c,d - это стороны 4-хугольника):

ab _ ba _ bc _ cb _ ca _ ac
dc   dc   da   da   db   db
Как видно, все они различны.

Задача 5

                                                 _____________
Пусть первое число арифметической прогресии А1 = а123'...'аm
(такая запись означает, что число А1 состоит из m цифр и его цифры а12,...,аm).
                         ___________
А разность прогресии D = d1'd2'...'dk.
Пусть n = 1000*max(m,k). В i-ом члене прогресии оказалось подчеркнуто число i. Пусть i = 1+10n, тогда аi = а1+d*10n, следовательно
     ________________________________
аi = d1'd2'...'dk'0'0'...'0'0'a1'...'ak 
(количество нулей равно n-m) Здесь подчеркнуто число 100...001 (n-1 ноль). Следовательно, так как а1 не равно нулю и перед ним стоят (n-m) нулей, то единственым возможным способом подчеркивания числа 1+10n является ситуация, когда а1 = 1 (в силу того, что n много больше k, n много больше m),иначе все это число должно быть среди
________      _________
d1'...'dk или  а1'...'аm ,
но это невозможно; т.е. а1 = 1. Тогда D оканчивается на число 100...00 (m-1 нулей), следовательно k>=m и D имеет вид
____________________
d1'...'dk-m'1'0'...'0 .
Рассмотрим аi+1 = ai+D. Прибавление числа D дает следующий результат:
_____________________________________________
d1'...'dk-m'1'0'...'0'd1'...'dk-m'2*a2'a3'...'am .
Но расположить в этом числе число 10..02 (n-1 ноль) можно только если d1,...,dk-m равны нулю (в силу n много больше k, n много больше m). Следовательно D = 100..00 = 10m-1. Что и требовалось доказать.

Задача 6

Ответ: можно.

Для начала покажем, как из расположения (k,k-1,k-2,...,3,2,1) получить (1,k,k-1,...,3,2) для любого k>=2. Будем перекладывать шары из 1-ой коробочки во 2-ю, из 2-й в 3-ю, и т.д. до k-ой. Легко проверить, что получится именно второе расположение шариков.

Теперь покажем, как можно получить из исходного расположения произвольное:
   1) переставим по циклу нужное число раз (может быть не одного) все коробочки, чтобы коробочка с k шарами (k = 23) оказалась на нужном нам месте (т.е. на 23-ем).
   2) не трогая коробочку с k шарами, переставим оставшиеся k-1 коробочки по циклу так, чтобы коробочка с k-1 шариком тоже оказалась на своем - на (k-1)-ом месте.
   ... и так далее, до тех пор, пока не получим требуемую расстановку.

Задача 7

а) Ответ: может. Например треугольник с вершинами в точках (0,0), (2/3,0) и (-2/3,2). Или такой: (0,0),(4/3,2/3) и (2/3,4/3). Площадь каждого из них 2/3, что больше чем 1/2.

б) Ответ: 2/3.

Лемма1. Если многоугольник можно переносить на целочисленный вектор без самоналожений, то его площадь не больше 1(единицы).

Док-во: Разрежем плоскость на единичные квадратики линиями координатной сетки. Наш многоугольник разрежется на несколько частей. Передвинем все эти части (сдвигом на целочисленный вектор) в один квадрат, получим некоторое заполнение квадрата; и по условию леммы - без самопересечений. Значит суммарная площадь кусочков - а следовательно и многоугольника - не превосходит единицы.

(*) Заметим, что если треугольник при переносе на целочисленный вектор не имеет самопересечений, то таким же свойством обладают треугольники, полученные из него переносом на ЛЮБОЙ вектор, а также центральносимметричные ему.

Пусть ABC - искомый треугольник. Предположим мы его нашли. Обозначим за A1,B1,C1 - середины сторон BC, CA, AB соответствено. Построим шестиугольник: A,C1,A1,C - это четыре его вершины. Еще две получаются центральной симметрией точек C1 и A1 относительно точки B1. Получили точки X и Y соответственно. Итак получили 6-угольник AC1A1CXY.

Докажем, что этот шестиугольник можно переносить на целочисленный вектор без самопересечений.

Если соединить точку B1 cо всеми вершинами шестиугольника, то получим шесть маленьких треугольничков.

Пронумеруем маленькие треугольнички, из которых составлен шестиугольник целыми числами от 1 до 6, считая по часовой стрелке (какой из них первый - не важно). Предположим противное: наш 6-тиугольник при переносе на какой-то целочисленный вектор накладывается на себя. Тогда рассмотрим точку, которая при этом движении переходит в себя. Отметим ее образ при движении и ее саму на шестиугольнике (далее будем называть эти две точки "образ" и "точка").

Возможны три случая:1) точка и образ попали в соседние треугольнички, например в 3 и 4; 2) они попали в треугольнички, между которыми находится ровно один треугольничек, например в 1 и 3; 3) они попали в противоположные треугольнички, например в 2 и 5. Случай когда они в одном треугольнике очевиден.

В случаях 1) и 2), оба маленьких треугольничка, в которых находятся точка и образ, могут быть помещены в один большой треугольник, равный ABC, (или центральносимметричный ему). Учитывая замечание (*) , эти случаи исключаются, так как иначе не выполняется "свойство движения треугольника ABC на целочисленный вектор без самопересечений".

Рассмотрим случай 3): пусть точка лежит в треугольничке С1A1B1, а образ в треугольничке B1XY. Возьмем треугольник ABC и наложим его на трапецию AC1XY. После чего начнем двигать наложенный треугольник параллельно YX, до тех пор, пока не покроем трапецию A1CXY. При этом, очевидно, наступит момент, когда мы будем накрывать и точку и ее образ. По вышесказанным соображениям, получаем противоречие.

Следовательно, ни один из случаев 1) - 3) не возможен, и получившийся шестиугольник обладает указаным свойством.

По Лемме1 его площадь не больше 1. Остается заметить, что площадь треугольника ABC составляет 2/3 от площади 6-ти угольника. Отсюда вывод: максимальная площадь искомого треугольника 2/3.

Пример построен в пункте а).


Дизайн сайта
интернет агентство "MindBridge Group"