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

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

Задача 1

Решение. Докажем сначала, что наибольшая разница зарплат двух сотрудников банка не может быть больше 3002 долларов.

Занумеруем людей "по часовой стрелке" числами от 1 до 2002, начиная с работника с минимальной зарплатой (из условия следует, что такой единственный). Пусть наибольшая зарплата у работника с номером N, тогда "по часовой стрелке" между 1-ым и N-ым работниками N-2 работника, а между N-ым и 1-ым работниками 2002-N работника, тогда искомая разница (обозначим ее за А) удовлетворяет неравенствам А<=(N-2+1)*3 и А<=(2002-N+1)*3 (так как разница зарплат у соседей не превышает 3 долларов). Складывая эти неравенства почленно, получаем неравенство 2*А<=2002*3 (1), откуда А<=3003.

Заметим, что разница А=3003 возможна, только если зарплаты между любыми двумя соседями отличаются на 3 доллара (если это не так, то рассмотренное выше неравенство превращается в строгое, откуда А<=3002<3003, так как число A натуральное). Но тогда у работника с минимальной зарплатой соседи имеют одинаковую зарплату, что противоречит условию, а значит, А<=3002.

Приведем теперь пример, когда наибольшая разница зарплат двух сотрудников банка равна 3002 доллара.

Пусть зарплата 2-го работника на 2 доллара больше, чем у 1-го, у каждого работника, начиная с 3-го и включая 1002-го, зарплата больше, чем у предыдущего на 3 доллара, у 1003-го работника зарплата меньше, чем у 1002-го на 2 доллара, а у каждого работника, начиная с 1004-го и включая 2002-го, зарплата меньше, чем у предыдущего на 3 доллара. Тогда зарплата 1002-го сотрудника на 2+3*1000=3002 доллара больше, чем у первого.

Задача 2

Решение 1. Возьмем номера 2¹³=8192 и 2¹⁴=16384 (две наибольшие степени двойки, меньшие 20000). У этих номеров НОДы со всеми остальными числами из заданного интервала совпадают. Поэтому различить их между собой не удастся.

Решение 2. Возьмем номера 101 и 101². Так как 101 простое, то со всеми числами 101 и 101² будут одновременно давать либо единицу, либо 101, так как уже 2*101² больше, чем 20000. Значит мы не можем отличить эти номера друг от друга.

Решение 3. Числа 19993 и 19997 больше 10000 и простые (поскольку не делятся на простые, меньшие 142, что можно проверить вручную). Тогда они со всеми числами будут давать НОД, равный единице, и их не отличишь друг от друга.

Задача 3

Договоримся также, что обозначение вида AB для дуги окружности (или стороны многоугольника) определяет дугу (сторону), отложенную на окружности от точки A по часовой стрелке до точки B.

Решение 1. Пусть есть стороны AB и CD нашего многоугольника. Тогда все остальные дуги (кроме AB и CD), на которые разделена окружность, расположены либо на дуге BC, либо на дуге DA; в таких случаях мы будем говорить, что часть дуг лежит с одной стороны от пары AB и CD, а часть дуг -- с другой стороны.

Заметим теперь, что для решения достаточно найти пару "противоположных" сторон с одинаковыми суммами дуг по разные стороны от этой пары. (Другими словами, достаточно найти такую пару "противоположных" сторон AB и CD, что дуги BC и DA равны по длине).

Рассмотрим произвольную упорядоченную пару "противоположных" сторон (назовем ее "исходной"). Утверждается, что разность сумм длин дуг по разные стороны от этой пары различается на число, кратное 50. Действительно, из любой другой пары "противоположных" дуг ровно одна лежит по одну сторону от "исходной" пары, и ровно одна -- по другую сторону, а значит, рассматриваемая разность сумм длин дуг равна умноженной на 25 разности количества "больших" и "маленьких" дуг по разные стороны от "исходной" пары сторон. Осталось заметить, что так как по каждую сторону от "исходной" пары лежит 12 дуг, рассматриваемая разность четна.

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

Итак, изначально разность рассматриваемых сумм длин дуг равнялась A = 50k, а через какой-то промежуток времени, изменяясь каждый раз на кратное 50 число, стала равна -A, откуда следует, что в какой-то момент она была равна нулю. Пара "противоположных" сторон, при рассмотрении которой рассматриваемая разность сумм длин дуг стала равна нулю, и есть искомая.

Решение 2. Заметим, что так как "больших" и "маленьких" дуг по 25, среди них найдутся соседние "большая" и "маленькая" (из разных пар "противоположных" дуг). Это означает, что и противоположные им дуги также соседние и одна из них "большая", а другая "маленькая" - откуда следует, что если объединить каждую из двух полученных пар соседних дуг в одну, то получим две "противоположные" дуги с одинаковой длиной.

Проделав такую операцию над всеми парами таких соседних дуг, "склеим" все соседние дуги, полученные ранее объединением "больших" с "маленькими" (тогда и противоположные им дуги будут в сумме иметь равную с новой дугой длину).

Теперь, будем, "приклеивая" к полученным "равным" дугам с одной стороны "большую" дугу , а с другой "маленькую" дугу (тогда к противоположной также "приклеиваем" противоположные им "маленькую" и "большую" дуги, получая новые противоположные дуги с равными длинами) и объединяя соседние "равные" дуги, уменьшать количество равных дуг.

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

Итак, получив в результате 4 дуги, заметим, что 2 из них исходные ("противоположные" с разностью длин 25), так как каждая наша операция "склеивания" дуг использует четное число пар исходных дуг, а всего изначально их было 25, что нечетно, а значит, минимум одна оставалась нетронутой всегда.

Осталось заметить, что из полученных 4 дуг, две являются исходными "противоположными", стягиваемыми сторонами 50-угольника, а две другие имеют равные длины и являются объединениями иходных дуг. Значит, оставшаяся пара исходных "противоположных" дуг стягивается параллельными сторонами 50-угольника, ч.т.д.

Задача 4

Приведем еще несколько решений задачи. Обозначения во всех остальных решениях следующие:

A', B', C' - точки пересечения прямых AP, BP, CP с BC, AC, AB соответственно. a = < ABP = < ACP, b = < CBP = < CAP, c = < BAP предположительно = < BCP

Решение 2 (Подобные треугольники). Треугольники APB' и BPA' подобны, BPC' и CPB' подобны (все по 2 углам) Тогда AP * PA' = CP * PC' и AP * AP' = BP * PB'. Тогда APC' и CPA' подобны по углу и отношению. Тогда < BAP = < BCP, и дальше все просто: сумма углов A и B'BA равна тогда сумме углов C и B'BC, а значит равны углы AB'B и CB'B. Поскольку эти углы смежные, они равны по 90 градусов, то есть BB' -- высота. Аналогично, AA' -- тоже высота, то есть P -- точка пересечения высот ABC.

Решение 3 (Вписаный четырехугольник). < C'PA = < APC = 180` - a - b = 180` - < C'BA' => C'BA'P - вписаный. Тогда < C'A'P = < C'BP = < C'CA => C'A'CA вписаный.
Тогда < C'AA' = < C'CA' (< BAP = < BCP).

Были также различные модификации этих решений, например равенство произведений из решения 1 выводились из степеней точек относительно окружностей описаных около BCB'C' и ABA'B'.

Решение 4 (Перпендикуляры). Опускаем на стороны AB, BC и AC перпендикуляры PD, PE, PF соответственно. Треугольники DBP и FCP подобны пусть с коэффициентом x (DB = x*CF), AFP и BEP с коэффициентом y (BE = y*AF). Тогда AP = PB/y = x/y*PC, PD = x*PF = x/y*PE. По теореме Пифагора AD² = AP² - PD² = (x/y*PC)² - (x/y*PE)² = (x/y*EC)², следовательно AD = x/y*EC. Тогда треугольники APD и CPE подобны по 2 отношениям, откуда < APD = < CPE. Так как < FPA + < APD + < DPB = < EPB +< CPE + < FPC, то точки B, P, F лежат на одной прямой. Аналогично A, P, E и C, P, D на одной.

Решение 5 (Синусы.) S(ABP)/S(ACP) = (1/2*AB*BP*sin(< ABP))/(1/2*AC*PC*sin(< ACP)) = AB*BP/(AC*PC); S(APC) / S(CPB) = AC*AP / (BP*BC).
Тогда S(ABP) / S(CPB) = (AB*BP)/(AC*PC) * (AC*AP)/(BP*BC) = AB*AP / (BC*PC);
Тогда sin(< BAP) = sin(< CPB). А так как углы < BAP и < BCP в сумме меньше 180 градусов, то они равны.

Для доказательства равенства синусов можно было также воспользоваться синусной теоремой Чевы.

Задача 5

В n-угольнике сумма углов равна 180*(n-2) градусов, откуда следует, что n-угольник разбивается на n-2 треугольника n-3 непересекающимися диагоналями.

Так как к каждой диагонали прилегают 2 разноцветных треугольника, то белых сторон не менее n-3, откуда самих треугольников одного (любого) цвета не менее (n-3)/3, (причем их количество целое).

Значит, в случае n=3k черных треугольников не меньше k-1, белых тогда не больше (3k-2)-(k-1)=2k-1, откуда разность не больше k.

Аналогично, в случае n=3k+1 черных треугольников не меньше k, белых тогда не больше (3k-1)-k=2k-1, откуда разность не больше k-1.

Наконец, в случае n=3k+2 черных треугольников не меньше k, белых тогда не больше 3k-k=2k, откуда разность не больше k.

Докажем, что на самом деле r(3k)=k, r(3k+1)=k-1, r(3k+2)=k. Для этого достаточно построить примеры разрезаний и раскраски.

Для n = 3, 4, 5 нужная раскраска легко находится перебором.

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

Нужно приставлять этот пятиугольник к "белой стороне" многоугольника, начав с белого треугольника в случае "3k", четырехугольника в случае "3k+1" и с пустого места в случае "3k+2".

Задача 6

Доказательство: Рассмотрим числа a₁, a₁+a₂, a₁+a₂+a₃, ..., a₁+...+a_n. Их всего n, и если ни одно из них не делится на n, то два каких-то числа из них дают одинаковые остатки от деления на n, скажем a₁+...+a_j и a₁+...+a_i, где j>i. Но тогда разность этих двух чисел делится на n, а она равна a_i+1+...+a_j (сумма нескольких исходных чисел или одно из исходных чисел).

Решение. Докажем утверждение индукцией по n. База индукции: при n=1 в наличии имеются только карточки, на которых написана цифра "1", и каждая карточка уже образует группу с суммой 1! (один факториал), тогда условие задачи выполняется. Пусть теперь задача верна для n, докажем ее для n+1.

Назовем карточкой нового образца (сокращенно КНО) всякую группу исходных карточек, сумма чисел на которых равна n, 2*n, ..., (n-1)*n. Достоинством КНО назовем сумму чисел на карточках, входящих в КНО, деленную на n (достоинство КНО принимает значение от 1 до n-1).

Так, каждая карточка с числом n уже является КНО достоинства 1. Из оставшихся карточек (с числами от 1 до n-1) будем выделять карточки нового образца следующим образом: берем любые n из оставшихся карточек, и по лемме находим из них несколько, сумма чисел на которых делится на n. Они образуют КНО (так как сумма чисел на них делится на n и меньше n², поскольку всего карточек не более n, и на каждой написано число, меньшее n).

В результате мы либо разложим все карточки на карточки нового образца , либо у нас в какой-то момент останется меньше, чем n карточек (и мы не сможем применить лемму). Но так как сумма чисел на всех карточках делится на n (она равна k*n!), и мы каждый раз выделяли КНО, которая состоит из карточек с кратной n суммой чисел, то сумма чисел на оставшихся карточках тоже будет делится на n, и они составят КНО (так как их меньше n).

Итак, мы разложили все карточки на карточки нового образца , достоинство каждой КНО -- от 1 до n-1, и сумма достоинств всех карточки нового образца равна k*(n-1)!. По предположению индукции можно разложить эти карточки нового образца на группы так, что сумма достоинств карточек нового образца в каждой группе будет равна (n-1)!. Но тогда сумма чисел на исходных карточках, составляющих карточки нового образца каждой из групп, будет равна n!, и требуемое в задаче распределение получено.

Задача 7

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

Задача 1

Задача 2

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

Итак, пусть BCDKL -- наш пятиугольник, причем стороны BC и KD параллельны, и стороны CD и BL параллельны. Продолжим стороны DK и BL до пересечения в точке A. Заметим, что ABCD - параллелограмм. Но тогда AL+AK>LK (по неравенству треугольника), откуда AB+AD>BL+LK+KD, а значит BC+CD>BL+LK+KD. Итак, в нашем пятиугольнике сумма длин некоторых двух его сторон (BC и CD) больше суммы длин трех оставшихся его сторон (BL, LK, KD). Но даже если BC и CD -- наибольшие стороны, а BL, LK и KD -- наименьшие, сумма первых двух не превышает 2*120=240 см, а сумма последних трех не меньше 3*80=240 см, то есть BC+CD<=240<=BL+LK+KD -- противоречие.

Задача 3

Задача 4

Задача 5

1) Займемся поиском равных углов. Угол XQB = 180 градусов минус угол BAQ = угол BAR = угол BMR = угол BRZ. (углы опирающиеся на равные дуги равны)

2) Угол AQX = угол ABQ = угол AKQ - как опирающиеся на равные дуги Угол AQX = угол RAM, так как (AM параллельна QX) и (угол RAM = угол RBM).

3) Пусть прямая BM пересекает l₁ в точке O₂, а прямую l₂ в точке O₁. Докажем, что точки O₁ и O₂ совпадают. Из предыдущих пунктов следует, что угол O₂BR = угол O₂QR, то есть O₂RBQ - описанный четырехугольник. Далее, угол O₁QB + угол O₁RB = 180 градусов, то есть уже O₁RBQ - описанный. Но поскольку O₁ и O₂ лежат на прямой l₁, а окружность, описанная около треугольника BQR может пересекать l₁ лишь в одной точке, помимо точки Q, то O₁=O₂=O. Пункт б) полностью доказан.

4) Докажем пункт а). Поскольку QORB - описанный, то угол OBQ = угол ORQ угол QBK + угол KAQ = 180 градусов (противоположные углы в описанном 4-угольнике), следовательно, угол KAQ = угол ARO - накрест лежащие, и прямые KA и OR - параллельны. Пункт а) полностью доказан.

Задача 6

Док-во: Предположим противное, что для некоторого p это не так. То есть существует натуральное k такое, что число p*k не встречается в последовательности, но существует бесконечно много элементов последовательности, кратных p. Тогда после (p*k)-го кратного p элемента стоит число большее чем p*k, а этого быть не может, так как p*k можно было поставить на его место.

Теперь докажем, что в последовательности бесконечно много четных чисел. Предположим, что начиная с какого-то момента все числа в последовательности нечетные. Последовательность, начиная с этого места, назовем "хвостом". Ясно что в "хвосте" найдется пара соседних чисел ..p,q,.. p Теперь докажем, что присутствуют все нечетные числа. Предположим, противное. Пусть число z - наименьшее из не встретившихся нечетных в нашей последовательности. Рассмотрим тот момент, когда все числа до z уже встретились. Найдем первое после этого четное число не взаимно простое с z. Сразу после него должно стоять z, так как оно не взаимно простое и наименьшее. Противоречие.

Задача 7

б) Ответ: 32 испытания.

Решение. Покажем, что 32 испытаний хватит.

Выберем диагональ идущую из правого верхнего в левый нижний угол. Занумеруем узлы этой диагонали натуральными числами от 1 до 8 подряд. Будем тестировать пары (1,5), (2,6), (3,7) и (4,8) - пары на диагонали, а также все пары узлов, симметричные относительно выбранной диагонали.

Пусть все испытания прошли успешно. Докажем, сначала, что тогда ток проходит между любыми двумя узлами выбранной диагонали. Для этого докажем, что узел 1 соединен с узлами 2, ..., 8. Так как между узлами 1 и 5 ток проходит, то существует путь от узла 1 до узла 5, состоящий из соседних узлов решетки, проходящий по целым проводам. Рассмотрим теперь "путь", симметричный этому относительно нашей диагонали. Заметим, что каждый узел второго "пути" связан с симметричным узлом первого пути, а значит все узлы второго пути связаны с узлами первого пути и друг с другом. Но объединение первого и второго путей дает симметричное относительно диагонали "оцепление" узлов 2, 3, 4. Тогда путь, соединяющий, например, узлы 2 и 6, обязательно пересечет это оцепление, (то есть будет содержать в себе один из узлов нашего оцепления). А значит, узлы 1 и 2 связаны. Аналогично, связаны узлы 1 и 3, 1 и 4, а значит и все узлы 1, ..., 8.

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

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