Всероссийская математическая олимпиада для учащихся 8 классов

1.  (1 балл)  В трех кучках лежат соответственно 12, 24 и 19 спичек. За ход можно переложить спичку из одной кучки в другую. За какое наименьшее число ходов можно получить три кучки с 8, 21 и 26 спичками?

Менее чем 4 ходами не обойтись: чтобы получить кучку из 8 спичек, придется из любой первоначальной кучки убрать как минимум 4 спички. Четырех ходов достаточно: перекладываем из кучки с 12 спичками по 2 спички в кучки с 19 и 24 спичками.

2. (1 балл) Сколько всего есть четырехзначных чисел, которые делятся на 19 и оканчиваются на 19?

Ответ: 5.

Решение. Пусть   — такое число. Тогда N – 19 тоже кратно 19. Но Поскольку 100 и 19 взаимно просты, то двузначное число делится на 19. А таких всего пять: 19, 38, 57, 76 и 95. Легко убедиться, что все числа 1919, 3819, 5719, 7619 и 9519 нам подходят.

3. У даты 12.04.1961 (то есть 12 апреля 1961 года) сумма цифр равна 24. Найдите ближайшую дату после 01.01.2008, у которой сумма цифр равна: а) (2 балла) 35; б) (2 балла) 7.

Ответ: а) 29.09.2049; б) 03.01.2010.

Решение. а) Наибольшая сумма цифр числа равна 11 для 29-го числа. Наибольшая сумма цифр месяца равна 9 для сентября, то есть для 09. Значит, наибольшая сумма цифр в текущем году будет у даты 29.09.2008. Она равна 30, что меньше 35. Следовательно, надо менять и год. Последняя цифра года не более 9, и если мы сохраняем первые две цифры, то придется цифру десятилетий увеличить до 4.

б) Для 2008 года сумма цифр года уже больше 27, поэтому год придется изменить. Ближайший год в будущем с меньшей суммой цифр — 2010-й. Соответственно, ближайшая подходящая дата 03.01.2010.

4. (3 балла) Среди целых чисел от 8 до 17 включительно зачеркните как можно меньше чисел так, чтобы произведение оставшихся было точным квадратом. В ответе укажите сумму всех вычеркнутых чисел.

Решение. Чтобы произведение было точным квадратом, нужно, чтобы каждый простой множитель входил в него в четной степени. В произведение 8 · 9·...· 17 в нечетной степени входят 2, 7, 11, 13 и 17. Значит, мы обязаны вычеркнуть сомножители 11, 13 и 17. А вот чтобы «убить» лишние простые множители 2 и 7, хватит одного вычеркнутого сомножителя 14. Итого сумма вычеркнутых чисел равна 11 + 13 + 14 + 17 = 55.

5. (3 балла) На гранях кубика расставлены 6 различных чисел от 6 до 11. Кубик бросили два раза. В первый раз сумма чисел на четырех боковых гранях оказалась равна 36, во второй — 33. Какое число написано на грани, противоположной той, где написана цифра 10?

Ответ: 8.

Cумма чисел на всех гранях равна 6 + 7 + 8 + 9 + 10 + 11 = 51. При первом броске сумма на верхней и нижней гранях равна 51 – 36 = 15, при втором — 51 – 33 = 18. Значит, на третьей паре противоположных граней сумма равна 51 – 15 – 18 = 18. Сумму 18 можно получить двумя способами: 11 + 7 или 10 + 8. Значит, на парах граней с суммой 18 напротив 11 находится 7, а напротив 10 — 8.

6. (3 балла)  В конкурсе участвовали 5 человек. На каждый вопрос один из них дал неправильный ответ, остальные — правильный. Число правильных ответов у Пети равно 10 — меньше, чем у любого другого. Число правильных ответов у Васи равно 13 — больше, чем у любого другого. Сколько всего вопросов было в конкурсе?

Ответ: 14.

Решение. Так как на каждый вопрос были даны 4 правильных ответа, общее число правильных ответов делится на 4. Поскольку Петя дал 10 верных ответов, Вася — 13, а остальные трое — от 11 до 12, то общее число правильных ответов не меньше, чем 10 + 13 + 3·11 = 56, и не больше, чем 10 + 13 + 3·12 = 59. Из чисел в этих пределах только 56 кратно 4, поэтому число вопросов равно

7. (5 баллов) Команда из Пети, Васи и одноместного самоката участвует в гонке. Дистанция разделена на участки одинаковой длины, их количество равно 42, в начале каждого — контрольный пункт. Петя пробегает участок за 9 мин, Вася — за 11 мин, а на самокате любой из них проезжает участок за 3 мин. Стартуют они одновременно, а на финише учитывается время того, кто пришел последним. Ребята договорились, что один проезжает первую часть пути на самокате, остаток бегом, а другой — наоборот (самокат можно оставить на любом контрольном пункте). Сколько участков Петя должен проехать на самокате, чтобы команда показала наилучшее время?

Ответ: 18.

Решение. Если Петя проедет 18 участков и пробежит оставшиеся 42 – 18 = 24, он затратит 18·3 + 24·9 = 270 мин. При этом Васе, наоборот, достанется проехать 24 участка, а пробежать 18, на что уйдет 24·3 + 18·11 = 270 мин — то же самое время. Если же Петя проедет меньшее число участков, то его время (и, соответственно, время команды) увеличится. Если Петя проедет большее количество участков, то увеличится время Васи (и время команды).

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

x·3 + (42 – x)·9 = (42 – x)·3 + 11x.

8. (5 баллов)  На каждую клетку шахматной доски положили по несколько монет так, чтобы суммы на каждых двух клетках, имеющих общую сторону, отличались на 1 р. Известно также, что на одной из клеток лежит 6 р., а на другой — 20 р. Найдите наибольшую возможную сумму монет на двух главных диагоналях.

Ответ: 208.

Решение. Назовем переходом перемещение из данной клетки в соседнюю с ней по стороне, а расстоянием между клетками — наименьшее число переходов, за которое можно попасть из одной клетки в другую. Поскольку при переходе число рублей в клетке меняется на 1, разность «стоимостей» двух клеток не больше расстояния между ними. Поэтому расстояние между клетками с 6 р. и 20 р. не меньше 14. Такое возможно только когда эти клетки — противоположные угловые, причем на любом кратчайшем пути из шестирублевой в двадцатирублевую стоимость клетки растет на 1. Тогда числа на любом таком пути определены однозначно. Но кратчайший путь из угла в противоположный угол можно провести через любую клетку доски! Значит, и числа на всей доске определены однозначно (см. рисунок). Отсюда — ответ:

6 + 8 + 10 + 12 + 14 + 16 + 18 + 20 + 8·13 = 208.

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

9. (5 баллов) Высота AH и биссектриса BL остроугольного треугольника ABC пересекаются в точке M. Известно, что BAH = 18°, а BCA = 54°. Найдите ACM.

Ответ: 36°.

Решение Из треугольника AHB:

ABH = 90° – BAH = 72°.

Поэтому в треугольнике ABC:

A = 180° – B – C = 180° – 72° – 54° = 54° = C.

Таким образом, треугольник ABC — равнобедренный, то есть BL — серединный перпендикуляр к отрезку AC. Значит,

и

ACM = CAM = 90° – ACH = 36°.

Ответ. 7.

Решение. Ответ, очевидно, не меняется, если превращать треугольник периметра 1 в треугольник периметра 21. Проделаем с треугольником со сторонами a ≤ b ≤ c две операции. После первой — стороны получившегося треугольника будут не больше b, c, b + c, после второй — не больше c, b + c, b + 2c. Если a + b + c = 1, то (так как c < a + b), то есть после двух операций стороны треугольника, получившегося из треугольника периметра 1, будут меньше соответственно Тогда после трех операций стороны треугольника будут меньше соответственно после четырех — после пяти — после шести — Поскольку шести операций нам не хватит. А семи операций достаточно: мы начинаем с треугольника со сторонами где e = 0,001 (нам удобнее писать длины в виде сумм и разностей), а после i-й операции стороны будут равны трем последовательным членам такого ряда:

Замечание. Внимательный читатель заметил, конечно, что в процессе решения у нас возникли числа Фибоначчи:

f₁ = 1, f₂ = 1, f₃ = 2, f₄ = 3, f₅ = 5,
f₆ = 8, f₇ = 13, f₈ = 21, f₉ = 34, f₁₀ = 55, ...
(вообще, f_i = f_i – 1 + f_i – 2 при i > 2).

Общая задача превращения треугольника периметра P в треугольник периметра Q (где Q < P), равносильна задаче о превращении треугольника периметра 1 в треугольник периметра

Ответ: n операций, где

Оценка получается обобщением проведенного выше доказательства, а пример строится так: выберем положительное и положим стороны i-го треугольника равными g_i – 1, g_i, g_i + 1, где g₀ = 3e,

Региональный этап

Первый день

1. (А. Белов-Канель) Гриб называется плохим, если в нем не менее 10 червей. В лукошке 90 плохих и 10 хороших грибов. Могут ли все грибы стать хорошими после того, как некоторые черви переползут из плохих грибов в хорошие?

Ответ: могут.

Решение. Пусть в каждом плохом грибе ровно 10 червей, а в хорошем червей нет. Далее, пусть из каждого плохого гриба по одному червю переползет в хорошие, по 9 в каждый. В результате в каждом грибе окажется по 9 червей, и все грибы будут хорошими.

1. Для полного балла достаточно верного примера, описывать схему переползания червей не обязательно.
2. Если пример описан неявно (например, есть равенства 90·10 + 10·0 = 900 и 9·100 = 900, ставится 5–6 баллов.
3. Если показано, что искомое возможно только в случае, когда червей ровно 900, а дальнейшего продвижения нет, ставится 2 балла.
4. Только ответ «могут» — 0 баллов.

2. (Р. Женодаров) Точка K — середина гипотенузы AB прямоугольного равнобедренного треугольника ABC. Точки L и M выбраны на катетах BC и AC соответственно так, что BL = CM. Докажите, что треугольник LMK также прямоугольный равнобедренный.

Решение. Медиана CK треугольника ABC является также высотой и биссектрисой, так как треугольник равнобедренный. Поэтому

KBC = KCB = KCA = 45°.

Отсюда KC = KB, и значит, треугольники KBL и KCM равны по двум сторонам (KC = KB,
BL = CM) и углу между ними. Поэтому KL = KM, и из равенства BKL = CKM следует:

LKM = LKC + CKM = LKC + BKL = BKC = 90°.

Значит, треугольник LMK — прямоугольный равнобедренный.

1. Если проведено дополнительное построение, например, треугольник достроен до квадрата, и его свойства, не вытекающие прямо из построения, используются без доказательства — не более 3 баллов.
2. Если доказан только один из двух фактов: KL = KM и угол LKM — прямой, — 4 балла.
3. (П. Кожевников) По кругу выписаны числа 1, 2, 3, ..., 10 в некотором порядке. Петя вычислил 10 сумм всех троек соседних чисел и написал на доске наименьшее из вычисленных чисел. Какое наибольшее число могло быть написано на доске?

Ответ: 15.

Решение. Способ I. Вначале докажем, что выписанное число не больше 15. Выделим число 10, а оставшиеся 9 чисел разобьем на три тройки соседних чисел. Сумма чисел в этих трех тройках равна 1 + 2 + 3 + ... + 9 = 45, поэтому хотя бы в одной из рассматриваемых троек сумма чисел не больше, чем 45 : 3 = 15. Пример (не единственный возможный!) расстановки чисел, при котором число, выписанное Петей, равно 15, таков:

1-5-9-2-7-6-8-3-4-10-(1).

Способ II (более популярное у участников). Всего имеется 10 троек соседних чисел, и каждое из выписанных чисел входит ровно в три из них. Поэтому если найти суммы чисел во всех тройках и сложить их, то получится 3∙(1 + 2 + ... + 10) = 165. Следовательно, наименьшая из сумм не превосходит а поскольку она — целое число, то она не больше 16. Допустим, она равна 16. Заметим, что соседние суммы a + b + c и b + c + d различны — иначе a = d. Поэтому суммы, соседние с 16, больше 16. Разобьем 10 наших сумм на пять пар соседних. В каждой паре не больше одной суммы, равной 16, то есть всего таких сумм не больше пяти. Вычтем из каждой суммы 16. Тогда сумма всех десяти сумм уменьшится на 160 и станет равной 5. При этом в нуль обратятся не более пяти сумм, а от остальных останется по крайней мере по единице. Такое возможно в единственном случае: когда осталось ровно 5 нулей и 5 единиц, то есть пять из исходных сумм равнялись 16, а остальные пять равнялись 17. При этом, поскольку равные суммы не могут стоять рядом, суммы 16 и 17 должны чередоваться по кругу. Покажем, что это невозможно. Пусть

a + b + c = 16, b + c + d = 17,
c + d + e  = 16, d + e + f = 16.

Тогда последовательно получаем, что d = a + 1, e = b – 1 и f = a — противоречие. Таким образом, минимальная сумма не больше 15, а пример, когда она равна 15, приведен в первом решении.

1. Есть только верный пример, для которого наименьшее из выписанных чисел равно 15, — 3 балла.
2. Имеется только доказательство того, что наименьшее из выписанных чисел не больше 15, — 4 балла.
3. Доказано только, что минимальная сумма не больше 16 и, возможно, что две одинаковые суммы не могут идти подряд, — 0 баллов.
4. Доказано, что минимальная сумма не больше 16, и показано, что если она равна 16, то суммы 16 и 17 чередуются по кругу, а дальнейшего продвижения нет — 2 балла.
5. Доказано, что минимальная сумма не больше 16, показано, что суммы 16 и 17 чередоваться по кругу не могут, но не показано, что если минимальная сумма равна 16, то суммы 16 и 17 обязательно чередуются по кругу, — 2 балла.
6. Есть целиком оценка (пример) и содержательные продвижения по примеру (оценке) соответственно — 4 балла.

4. (О. Подлипский, Б. Трушин) Имеются чашечные весы и 100 монет, среди которых несколько (больше 0, но меньше 99) фальшивых монет. Все фальшивые весят одинаково, все настоящие тоже весят одинаково, при этом фальшивая монета легче настоящей. Можно делать взвешивание на весах, заплатив перед взвешиванием одну из монет. Докажите, что можно с гарантией обнаружить настоящую монету.

Решение. Способ I. Заплатив монету перед первым взвешиванием, мы имеем 99 монет, среди которых есть хотя бы одна настоящая. Положим на две чаши весов по одной монете. Если одна из них перевешивает, то она настоящая. Если же весы в равновесии, то либо обе взвешиваемые монеты настоящие, либо обе фальшивые. Заплатив одну из них, мы имеем 98 монет, среди которых есть хотя бы одна настоящая. Значит, мы опять либо на следующем шаге обнаружим настоящую монету, либо будем иметь 97 монет, среди которых есть хотя бы одна настоящая. Продолжим так делать и дальше. Если весы в некоторый момент выйдут из равновесия, то мы найдем настоящую монету. Если же все время будут показывать равновесие, то в конце концов, заплатив монету, мы будем иметь две монеты, среди которых есть хотя бы одна настоящая. Положим на две чаши весов по одной монете. Если одна из них перевешивает, то она настоящая. Если же весы в равновесии, то обе оставшиеся монеты настоящие.

Способ II. Сначала покажем, что за два взвешивания можно найти группу из 33 монет, в которой есть настоящая. Разделим монеты на 3 группы A, B, C по 33 монеты и одну в остатке. Заплатив этой монетой, сравним группы A и B (заметим, что хотя бы одна настоящая монета еще осталась). Если весы не остались в равновесии, то на перевесившей чашке есть хотя бы одна настоящая. Если же весы в равновесии, то сравним группы A и C, заплатив монетой из B. Если одна перевесила, то в ней есть настоящая, а если весы в равновесии, то в каждой из групп A, B, C было поровну настоящих монет — значит, хотя бы по одной. Тогда в группах A и C осталось по настоящей монете. Итого, мы нашли группу (назовем ее D) из 33 монет, в которой есть настоящая; кроме этой группы, у нас осталось еще хотя бы 65 монет (пусть они образуют группу E). Теперь сравним одну монету из группы D с каждой из остальных монет этой группы (платя каждый раз монетами из E). Тогда либо какая-то монета перевесит (она и будет настоящей!), либо все монеты будут весить поровну. В последнем случае, так как в D есть настоящая, то все монеты в D будут настоящими. В любом случае, мы нашли хотя бы одну настоящую монету.

Критерии оценки

1. Верный алгоритм без обоснования: в решении никак не используется (хотя, возможно, и сказано), что настоящих монет не меньше двух, — 4 балла.
2. Алгоритм, который не сходится только из-за того, что не наступает случай взвешивания по одной монете разного веса, причем добавление фразы: «если равенство, то обе монеты настоящие», дает полное (при правильном обосновании) решение, — 3 балла.
3. Неверное понимание условия: считается, что можно одной монетой заплатить за все взвешивания, — 0 баллов.
4. Верный алгоритм с обоснованием, но не показано, откуда берутся монеты для уплаты за взвешивания, — в очевидных случаях прощается, в неочевидных — по ситуации.

Второй день

5. (И. Рубанов) На столе лежат 7 карточек с цифрами от 0 до 6. Двое по очереди берут по одной карточке. Выигрывает тот, кто впервые из своих карточек сможет составить натуральное число, делящееся на 17. Кто выиграет при правильной игре — начинающий или его противник?

Ответ: начинающий.

Решение. Обозначим игроков A (начинающий) и B (его противник). Приведем стратегию, позволяющую A гарантированно выиграть. Пусть он возьмет первым ходом цифру 3; тогда B вынужден брать 4 (иначе A вторым ходом ее возьмет и выиграет, составив число 34). Заметим, что тогда вторым своим ходом B не выиграет, ибо единственное двузначное число, содержащее 4 в своей записи и делящееся на 17, — это 34. Далее A возьмет 1, тогда B должен брать 5 (действительно, этим ходом он не выиграет, а следующим ходом A возьмет 5 и составит 51). Тогда следующим ходом A возьмет 6 и выиграет, составив число 136. Существуют и другие выигрышные стратегии для A.

1. Верный алгоритм, но не проверено, что второй не может победить вторым ходом, и нет понимания, что такая проверка необходима, — 5 баллов.
2. Верный алгоритм, но то, что второй не может победить вторым ходом, проверено только для части возможных ответов второго (обычно — только «защитных», например, 0 или 1 при условии, что у первого на руках 3 и 6) — 5 баллов.
3. Верный алгоритм, но то, что второй не может победить вторым ходом, объявлено очевидным, или проверка только декларирована (скажем, без комментариев выписан ряд чисел, делящихся на 17) — 6 баллов.
4. Неверное понимание условия (не те цифры, понимание «составления» как сложения цифр и т.п.) — 0 баллов.

6. (И. Богданов) В трех клетках клетчатого листа записаны числа, а остальные клетки пусты. Разрешается выбрать два числа из разных непустых клеток и записать в пустую клетку их сумму; также можно выбрать числа a, b, c из трех разных непустых клеток и записать в пустую клетку число ab + c². Докажите, что при помощи нескольких таких операций можно записать в одну из клеток квадрат суммы трех исходных чисел (какими бы они ни были).

Решение. Пусть исходные числа — x, y, z. Получим сначала числа x + y, y + z, z + x. Затем из клеток x, y + z, y получим x(y + z) + y²; аналогично получим числа y(z + x) + z² и z(x + y) + x². Сложив их, получаем требуемое:

x(y + z) + y² + y(z + x) + z² +z(x + y) + x² =
= x² +y² +z² + 2xy + 2yz + 2zx = (x + y + z)².

Критерии оценки

1. Только числовой пример — 0 баллов.
2. Задача решена при условии, что два числа из трех можно брать из одной ячейки, причем хотя бы на одном шаге используется одна из трех исходных ячеек, — 1 балл.
3. В алгоритме есть шаги, когда два числа из трех берутся из одной ячейки, исходные ячейки при таких шагах не используются, — оценка не снижается.
4. Алгоритм, работающий только для целых чисел, — 0 баллов.

7. (Н. Агаханов) В выпуклом четырехугольнике ABCD некоторая точка диагонали AC принадлежит серединным перпендикулярам к сторонам AB и CD, а некоторая точка диагонали BD принадлежит серединным перпендикулярам к сторонам AD и BC. Докажите, что ABCD — прямоугольник.

Решение. Пусть M — указанная точка на диагонали AC. Тогда, по свойству серединных перпендикуляров, MA = MB и MC = MD. Поэтому BD ≤ BM + MD = AM + MC = AC. Аналогично рассуждая для другой пары серединных перпендикуляров, получаем, что AC ≤ BD. Значит, BD = AC, неравенства обратились в равенства, поэтому точка M лежит на отрезке BD, то есть является точкой пересечения диагоналей; при этом она должна лежать на серединных перпендикулярах ко всем сторонам четырехугольника ABCD. Значит, его диагонали делятся точкой пересечения пополам (то есть ABCD — параллелограмм) и равны. Значит, ABCD — прямоугольник.

1. Рассматривается только случай, когда все серединные перпендикуляры проходят через точку пересечения диагоналей, — 0 баллов.
2. Доказано только равенство длин диагоналей, — 4 балла.
3. Написано строгое неравенство в обоих случаях, получено противоречие, после чего делается вывод, что тогда точка лежит сразу на двух диагоналях, остальное верно — 6 баллов.

8. (С. Токарев) В футбольном турнире участвовало 8 команд, причем каждая сыграла с каждой ровно по одному разу. Известно, что любые две команды, сыгравшие между собой вничью, набрали в итоге разное число очков. Найдите наибольшее возможное общее число ничьих в этом турнире. (За выигрыш матча команде начисляется 3 очка, за ничью — 1, за поражение — 0.)

Ответ: 22.

Решение. Докажем, что ровно по 6 ничьих может быть не более чем у двух команд. Действительно, любая такая команда имеет либо 6, либо 6 + 3 очка (в зависимости от того, выиграла или проиграла она свой результативный матч). Если таких команд три, то у двух из них поровну очков, значит, между собой они сыграли не вничью; этого не может быть, ибо они обе либо не выигрывали, либо не проигрывали ни одного матча. Также ясно, что максимум одна команда все свои 7 матчей сыграла вничью. Таким образом, сумма количеств ничьих у всех 8 команд не превосходит

7 + 6 + 6 + 5 + 5 + 5 + 5 + 5 = 44,

а поскольку каждый ничейный матч учитывается дважды, то общее число ничьих в турнире не превосходит Оно может равняться 22, как показано на рисунке 4.

1. Только верный ответ — 1 балл.
2. Только верный пример — 3 балла.
3. Только доказательство, что ничьих не более 22, — 4 балла.
4. Доказано, что есть не более двух команд, имеющих по 6 ничьих, других существенных продвижений нет — 2 балла.

Заключительный этап

Первый день

1. (М. Евдокимов, в редакции Л. Самойлова.)  У реки живет племя Мумбо-Юмбо. Однажды со срочным известием в соседнее племя одновременно отправились молодой воин Мумбо и мудрый шаман Юмбо. Мумбо побежал со скоростью 11 км/ч к ближайшему хранилищу плотов и затем поплыл на плоту в соседнее племя. А Юмбо, не торопясь, со скоростью 6 км/ч, пошел к другому хранилищу плотов и поплыл в соседнее племя оттуда. В итоге Юмбо приплыл раньше, чем Мумбо. Река прямолинейна, плоты плывут со скоростью течения. Эта скорость всюду одинакова и выражается целым числом км/ч, не меньшим 6. Каково наибольшее возможное ее значение?

Ответ: 26 км/ч.

Решение. Обозначим место обитания племени Мумбо-Юмбо через O, хранилище, к которому побежал Мумбо, через M, а хранилище, к которому пошел Юмбо, через U. Очевидно, что M находится выше по течению, чем O, а U ниже. Пусть расстояния от O до M и U равны x и y км соответственно (x < y), скорость реки равна v км/ч. На путь от O до U Юмбо затратил ч, а Мумбо —

Ясно, что в соседнее племя Юмбо приплывает раньше Мумбо тогда и только тогда, когда

Так как x < y, из этого неравенства следует, что

Сократив на y и преобразовав, получаем: v < 26,4. Осталось проверить, что скорость реки могла равняться 26 км/ч. Для этого в неравенстве положим v = 26 и равносильно преобразуем его к виду Последнее возможно (например, при y = 1,12 км, x = 1,11 км), что и завершает решение.

1. Только ответ без примера — 0 баллов.
2. Только ответ с примером — 1 балл.
3. Доказано, что никакие случаи расположения хранилищ плотов, кроме одного, невозможны, дальнейшего содержательного продвижения нет — 1 балл; в остальном оценивается только разбор основного случая.
4. Рассматривается только «худший случай» равенства расстояний до двух хранилищ (или одновременного прибытия Мумбо и Юмбо), но обоснования того, что он действительно худший, нет — 3 балла.
5. Оценка v £ 26 км/ч доказана, существование примера на 26 км/ч не обосновано — 6 баллов, если существование примера не вытекает непосредственно из доказательства оценки, 7 баллов, если вытекает.
6. Задача сведена к линейному неравенству для скорости v. Проверено, что это неравенство справедливо при v = 26 и несправедливо при v = 27, но не доказано, что оно несправедливо при v > 27, — 4 балла.

2. (А. Шаповалов) При всяком ли натуральном n, большем 2009, из дробей можно выбрать две пары дробей с одинаковыми суммами?

Ответ: да.

Решение. Каждая из данных дробей имеет вид

где 1≤ a≤n. Стало быть, нам требуется найти такие различные натуральные числа a, b, c и d, не большие 2009, для которых

Убрав минус единицы и поделив затем на n + 1, получим равносильное равенство Осталось подобрать удовлетворяющие ему дроби. Это можно сделать, взяв любое равенство двух сумм различных натуральных слагаемых, НОК которых не больше 2009, и поделив его на этот НОК. Например, равенство 1 + 4 = 2 + 3, поделенное на 12, дает

Критерий оценки

Задача сведена к равенству, не содержащему n, дальнейшего содержательного продвижения нет — 3 балла.

3. (С. Берлов) В треугольнике ABC стороны AB и BC равны. Точка D внутри треугольника такова, что угол ADC вдвое больше угла ABC. Докажите, что удвоенное расстояние от точки B до прямой, делящей пополам углы, смежные с углом ADC, равно AD + DC.

Решение. Пусть l — биссектриса углов, смежных с углом ADC, точка K — проекция B на l, а точки B' и C' симметричны соответственно точкам B и C относительно l (рис. 5). Тогда BB' = 2BK — как раз удвоенное расстояние от B до l. Кроме того, точка D лежит на отрезке AC' (так как прямые DA и DC симметричны относительно l) и

AC' = AD + DC' = AD + DC.

Далее, из той же симметрии получаем:

AC'B' = DC'B' = DCB, BB'C' = B'BC.

Пусть отрезки BB' и AC' пересекаются в точке O. Из прямоугольного треугольника OKD получаем:

Значит,

ABB' = ABC – B'BC = BOC' – OB'C' =OC'B'.

Аналогично,

BAO = BOC' – ABO = ABC – ABO = B'BC = BB'C'.

Таким образом, треугольники ABO и B'C'O равны по стороне и двум прилежащим углам. Отсюда

BB' = BO + OB' = C'O + OA = AC' = AD + DC,

что и требовалось.

4. (Н. Гравин) В стране Леонардии все дороги — с односторонним движением. Каждая дорога соединяет два города и не проходит через другие города. Департамент статистики вычислил для каждого города суммарное число жителей в городах, откуда в него ведут дороги, и суммарное число жителей в городах, куда ведут дороги из него. Докажите, что хотя бы для одного города первое число оказалось не меньше второго.

Решение. Способ I. Построим граф, вершины которого соответствуют жителям страны, причем две вершины соединены направленным ребром в том и только том случае, когда их города соединены дорогой (направление на ребре будет такое же, как на дороге между городами). Для каждой вершины v этого графа обозначим через f(v) количество ребер, входящих в v, минус количество ребер, выходящих из v. Сумма f(v) по всем вершинам графа равна 0, так как каждое ребро вносит в нее одну +1 и одну –1. Значит, найдется такая вершина u, что f(u) ³ 0. Остается отметить, что f(u) в точности равно разности первого и второго чисел для города, в котором живет u.

Способ II. Пусть n(A) — число жителей города A, а f(A) — суммарное население городов, дороги из которых входят в A, минус суммарное население городов, в которые выходят дороги из A. Если утверждение задачи неверно, то f(A) < 0 для каждого города A. Тогда сумма S чисел n(A)f(A) по всем городам страны отрицательна. С другой стороны, рассмотрим любую дорогу из A в B.
В число n(B)f(B) эта дорога «вносит вклад» +n(B)n(A), а в число n(A)f(A) — «вклад» –n(A)+n(B). Рассмотрев все дороги, получим, что S = 0. Противоречие.

Замечание. Отметим, что во втором решении мы использовали лишь тот факт, что «количество жителей города» положительно. Чтобы оно было целым, не требуется.

Решение опирается на неверное утверждение о равенстве сумм входящих и исходящих степеней в исходном графе — 0 баллов.

Второй день

5. (Р. Женодаров) Можно ли вместо звездочек вставить в некотором порядке в выражение

НОК(*; *; *) – НОК(*; *; *) = 2009

шесть последовательных натуральных чисел так, чтобы равенство стало верным?

Решение. Наименьшее общее кратное (НОК) нескольких чисел делится на каждое из них и, следовательно, на каждый их делитель. Значит, если среди чисел, от которых находят НОК, есть четное, то НОК тоже будет четным. Разность двух четных чисел — число четное, а 2009 — нечетное. Значит, если такие шесть последовательных натуральных чисел существует, то все четные числа среди них должны быть в одном НОК. Среди шести последовательных натуральных чисел — три четных и три нечетных, значит, один НОК будет находится от трех последовательных четных чисел, а другой — от трех последовательных нечетных чисел. Но среди трех последовательных как четных так и нечетных чисел есть кратное трем. Но тогда оба НОК кратны трем и их разность делится на 3. Но 2009 на 3 не делится. Значит, таких шести последовательных натуральных чисел не существует.

1. Показано, что все четные числа — в одном НОК, дальнейшего продвижения нет — 2 балла.
2. Показано, что оба числа, кратные 3, находятся в одном НОК, дальнейшего продвижения нет — 2 балла.

6. (С. Берлов) В выпуклом четырехугольнике ABCD выполнены соотношения AB = BD; ABD = DBC. На диагонали BD нашлась точка K такая, что BK = BC. Докажите, что KAD = KCD.

Решение. Отложим на стороне AB отрезок BE = BC. Равнобедренные треугольники EBK и KBC равны по двум сторонам и углу между ними. Поэтому EK = KC, а

AEK = 180° – BEK = 80° – BKC = CKD.

Кроме того,

KD = BD – BK = BA – BE = EA.

Следовательно, треугольники AEK и DKC равны. Далее, поскольку оба треугольника BEK и BAD — равнобедренные,

Поэтому AD  EK, откуда

KAD = EKA = KCD.

7. (И. Рубанов, А. Шаповалов) На столе лежит 10 кучек с 1, 2, 3, 4, 5, 6, 7, 8, 9 и 10 орехами. Двое играющих берут по очереди по одному ореху. Игра заканчивается, когда на столе останется 3 ореха. Если это три кучки по одному ореху, выигрывает тот, кто ходил вторым, иначе — его соперник. Кто из игроков может выиграть, как бы ни играл соперник?

Решение. Способ I. Назовем кучки из одного ореха «единицами», а из двух — «двойками». Первый должен придерживаться следующих правил: 1) если на доске есть «единицы» — убрать одну из них; 2) не брать из «двоек». В остальном ходы первого могут быть любыми. Заметим, что число орехов в начале игры нечетно, значит, оно нечетно и перед любым ходом первого. Поэтому перед его ходом на доске всегда будет хотя бы одна нечетная кучка, то есть первый всегда сможет сделать ход, не нарушая описанных правил. Теперь заметим, после первого хода первого на доске нет «единиц». После хода второго может появиться не более одной новой «единицы», которую первый заберет. Значит, и после следующих ходов первого «единиц» на доске не будет, а после любого хода второго на доске будет не больше одной «единицы». В частности, так будет и в конце игры, то есть первый выиграет.

Способ II. Пусть первый каждым ходом берет орех из самой маленькой кучки. Тогда после 21-го хода первого исчезнут не менее 6 кучек. Итак, после ответного хода второго останется 13 орехов и не более 4 кучек. Если кучек ровно 4, то в наименьшей не больше 3 орехов. Поэтому, в любом случае, еще через 3 хода первого и второго останется 7 орехов и не более 3 кучек. Если кучек ровно 3, то в наименьшей не более 2 орехов. Значит, еще через 2 хода останется 3 ореха и не более 2 кучек, то есть выиграет первый игрок.

1. Верная стратегия с удалением «единиц» и неудалением «двоек» без обоснования — 3 балла.
2. Только идея уменьшения минимального числа — 1 балл.
3. Стратегия с уменьшением числа кучек, если показано, что первый может убрать первые шесть (или пять) кучек, а дальнейшие действия первого только описаны, их возможность не обоснована, — 1 балл.
4. Стратегия с уменьшением числа нечетных кучек, если тот факт, что перед последним ходом второго нечетных кучек не останется, никак не обоснован, — 4 балла.
5. Стратегия «первый всегда берет из нечетной кучки» без уточнения, что если есть 1, то она немедленно уничтожается, — 0 баллов (поскольку такая стратегия может привести и к поражению).

8. (И. Богданов) На бесконечной ленте выписаны в ряд числа. Первой идет единица, а каждое следующее число получается из предыдущего прибавлением к нему наименьшей ненулевой цифры его десятичной записи. Сколько знаков в десятичной записи числа, стоящего в этом ряду на 9<·1000¹⁰⁰⁰-м месте?

Ответ: 3001.

Решение. Поскольку каждое число ряда, начиная со второго, больше предыдущего хотя бы на единицу, 9·1000¹⁰⁰⁰-е его число больше 9·1000¹⁰⁰⁰, то есть в нем как минимум 3001 цифра. Обозначим n-е число ряда через a_n, и пусть k — наименьший номер, такой, что в числе a_k 3002 цифры. Если мы докажем, что k > 9·1000¹⁰⁰⁰, то получим, что в 9·1000¹⁰⁰⁰-м числе ряда не более 3001 цифры, то есть в нем ровно 3001 цифра.

Рассмотрим числа от 0 до 10³⁰⁰¹ – 1, не имеющие единиц в десятичной записи. Дополнив каждое слева нулями до 3001 знака, мы получим все последовательности длины 3001 из цифр, отличных от единицы. Таких последовательностей 9³⁰⁰¹. Значит, и среди чисел a₁, ..., a_k – 1 не более 9³⁰⁰¹ чисел, не имеющих единицы в десятичной записи (так как все они не превосходят 10³⁰⁰¹ – 1).

Рассмотрим теперь процесс получения числа a_k из a₁. На каждом из k – 1 шагов прибавляется число от 1 до 9, причем количество шагов, на которых прибавляется не единица, не превосходит 9³⁰⁰¹. Значит,

10³⁰⁰¹ – 1 ≤  a_k – a₁ ≤  9·9³⁰⁰¹ + 1·(k – 1 – 9³⁰⁰¹) = k – 1 + 8·9³⁰⁰¹,

откуда

k ³ 10³⁰⁰¹ – 8·9³⁰⁰¹.

Осталось показать, что

10³⁰⁰¹ – 8·9³⁰⁰¹ > 9·10³⁰⁰⁰.

Для этого достаточно доказать, что

9³⁰⁰² < 10³⁰⁰⁰.

Заметим, что

9⁷ = 4 782 969 < 5·10⁶,

откуда

9²⁸ < 5⁴·10²⁴ < 10²⁷ и 9⁵⁶ < 10⁵⁴.

Поэтому

9³⁰⁰² = 9⁵⁶·9²⁹⁴⁶ < 10⁵⁴·10²⁹⁴⁶ = 10³⁰⁰⁰.

1. Верный ответ без всякого обоснования — 0 баллов.
2. Доказано только, что знаков не менее 3001 — 1балл.
3. Задача сведена к верному числовому неравенству, которое не доказано, — 4 балла.

¹ Положение и другую информацию об олимпиаде можно найти в интернете на сайте олимпиады http://www.matol.ru/
² Результаты этих соревнований шли их участникам и в зачет соответствующего тура олимпиады им. Эйлера.

Рубанов И.