Олимпиада по математике

58

ХI Всесоюзная олимпиада ШКОЛЬНИКОВ

И. Клумова, М. Смолянский

Олимпиада
по математике

В этом году XI Всесоюзная олимпиада школьников была посвящена 60-летию Великого Октября.

Заключительный тур по математике XI Всесоюзной олимпиады проходил в столице Эстони—город Таллине.

В Таллиннике 153 школьника — победители ресурсивикских олимпиад и ребята, занявшие I и II места на предыдущее олимпиаде. Впервые на олимпиаде была представлена команда (3 человек) учеников профессионально-технических училищ, победителей олимпиады ПТУ г. Ленинграда. Хозяева заключительного тура олимпиады — талинцы — также выступили своего команду из 3-х человек.

В современных приняли учащие 42 восемиклассника, 56 девятиклассников и 55 десятиклассников.

Открытие заключительного этапа XI Всесоюзной олимпиады состоялось 14 апреля в актовом зале Таллинского политического института. Председатель Оргкомитета академик АН Эстонской СССР А. К. Хумал поздравил участников олимпиады, с началом составания, пожелал им успехов и защотал приветь и поздравление министра просвещения СССР Прокофьева М. А.

Почти полгода жюри придирчив отбирало задачи для олимпиады из большого списка задач-«кандидатов», представленных математиками из разных городов. Чтобы читатели заметить эти задачи, мы полностью приводим их условия. Большинство из них уже было опубликовано в «Задачнике «Кванта» (см. №№7—9)*.

Как обычно, заключительный этап олимпиады проводился в два тура.

К решению задач первого тура школьники присутствили 15 апреля. На решение задач каждойому классу ответилось по 5 часов.

Ниже мы приводим список задач первого тура.

8 класс

1. На плоскости дана несамопересекающаяся замкнутая ломанная, никакие три вершины которого не лежат на одной прямой. Известно что если прямая проходит через две или более отрезанных точек, то сумма всех чисел, написанных около этих точек, равна нулю. Докажите, что число особенных пар четно. (M457)

2. На плоскости отмечено несколько точек, не лежащих на одной прямой, и около каждой написано число. Известно что если прямая проходит через две или более отрезанных точек, то сумма всех чисел, написанных около этих точек, равна нулю. Докажите, что все числа равны нулю. (M451)

3. Отрезок, соединяющий середины двух AB и AC окружности, описанной около треугольника ABC, пересекает стороны AB и AC в точках K и L. Докажите, что точки A, K, L и центр O описанной окружности треугольника ABC — вершины ромба.

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

*) В скобках после условия мы проводим номер, под которым соответствующая задача помещена в «Задачнике».

59

после этого убирает все белые фишки, имеющие черного соседа. Так они делают до тех пор, пока не остатся все фишки одного цвета.

a) Пусть вначале было 40 фишек. Можно ли слушаться, что после того, как каждый следа два хода, на окружности остатся одна фишка?

6. На окружности сначала было 1000 фишек. Через какое наменьшее число ходов на окружности может остаться одна фишка?

9 класс

1. В окружность вписаны треугольники $T_1$ и $T_2$, причем вершины треугольника $T_2$ являются серединами дуг, на которые окружность разбивает вершины треугольника $T_1$. Докажите, что в шестиугольнике $T_1 \cap T_2$ диагонали, соединяющие противоположные вершины, параллельны сторонам треугольника $T_1$ и пересекаются в одной точке. (M452)

2. Дана бесконечная числа последовательность $a_1, a_2, \ldots, a_n$, ИЗВЕСТНО, что $\lim_{n \to \infty} \left( a_{n+1} - \frac{1}{2} a_n \right) = 0$. Докажите, что $\lim a_n = 0$.

3. См. задачу №1 из 8-го класса.

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

10 класс

1, 2. См. задачи №1 и №2 из девятого класса.

3. В каждом вершине выпускло многогранника $M$ сходится 3 ребра. ИЗВЕСТНО, что каждая его грань является многоугольником, вокруг которого можно описать окружность. Докажите, что вокруг этого многогранника можно описать сферу. (M456)

4. Написан многочлен $x^{10} + x^9 + x^8 + \ldots + x^2 + x + 1$. Двое играют в такую игру. Сначала первый элемент любую из звездочек некоторых элементов любую из оставшихся звездочек, затем снова первый элемент допуну из звездочек числом и так далее (всего 9 ходов). Если у полученного многочлена не будет действительных корней, то выигрывает пер-

60

выйгрок, а если будет хотя бы один корень — выиграет второй. Может ли второй игрок выиграть при любой игре первого? (M458)

5. См. задачу № 1 из 8-го класса.

Самой трудной для школьников восмого класса оказалась задача № 2. После проверки работ выяснили, что ее решили только четые целовека. Трудности вызвала и задача № 4, особенно пункт 6).

У десятиклассников трудной оказалась задача № 4 — ее решили всего лишь три целовека.

А девятиклассники решили свои задачи примерно одинаково. Как именно школьники справились с задачими, видно из приведенной таблицы. В ней для каждой класса показано, сколько человек решили ту или иную задачу полностью (оценка «+»), сколько — «почти» полностью, с небольшими недочетами (оценка «±»), сколько — в целом не решивших задачу, но высказавших существные иден по поводу ее решения (оценка «≠»). Вы, конечно, обратили внимание на то, что у десятиклассов число участников в первом и во втором турах не одно и то же. Один из участников — С. Самигулин (из команды РСФСР) ехал в Таллин из Башкирии; он задержался из-за нелетной погоды и опоздал на первый тур. В Таллине пришлось специально для него срокно составить еще один варант задач (утвержденные задачи I типа были уже известны). Во втором.type С. Самигулин решал уже одинаковые со всеми задачи: десятиклассников стало 55, как и должно было бы с самого начала.

16 апреля все школьники приняли участие в коммунистическом субботнике. А жюри олимпiadы в это время проверяло работы.

Продолжение составной просходило 17 апреля. Школьники восмых и девятых классов снова решили по 4 задачи, школьники десятиклассов — три. Вот эти задачи.

8 класс

5. За круглым столом сидят 7 гномов. Перед каждым стонт кружка. В некоторых из этих кружек налито молоко. Один из гномов разливает все свое молоко в кружки остальных поровну. Затем его сосед справа делает то же самое. Затем то же самое делает et следующий сосед справа и так далее. После того как последний, седьмой, гном разил все остальные свое молоко, в каждой кружке оказалось столько же молока, сколько было в ней вначале. Во всех кружках вместе молока 3 литра. Сколько молока было первоначально в каждой кружке? (M454)

6. Будем называть 2n-значное число особым, если оно само является точным квадратом, и числа, образованные его первыми n цифрами и его последними n цифрами, также являются точными квадратами; при этом второе число начинается с цифры 0, но не должно быть равно нулю.

a) Найдите все двухначные и четырехначные особые числа.

6. Возможны ли шестизначные особые числа? (Докажите, что их нет, или приведите пример такого числа.)

7. Дано множество положительных чисел {a₁; a₂; …; aₙ}. Для каждой его подмножества выпишем сумму входящих в него чисел (расматривается суммы из одного, двух, …, n слагаемых). Докажите, что все выписанные числа можно так разить на n групп, чтобы в каждой группе относение наибольшего числа к наиболее шумному не превышению 2. (M453)

8. Имеется тысяча билетов с номерами 000, 001, …, 999 и сто ящиков с номерами 00, 01, …, 99. Билет разрешается опускать в ящик, если номер ящика можно получить из номера этого билета вычеркиванием одной из цифр. Докажите, что a) можно разложить все билеты в 50 ящиков;

6. нельзя разложить все билеты менее чем в 40 ящиков;

b) нельзя разложить все билеты менее чем в 50 ящиков.

9 класс

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

6. Данны натуральные числа x₁, x₂, …, xₙ, y₁, y₂, …, yₙ. Суммы x₁+x₂+…+xₙ и y₁+y₂+…+yₙ равны между собой и меньше mn. Докажите, что в равенстве x₁+x₂+…+xₙ=y₁+y₂+…+yₙ можно вычеркить часть слагаемых так, чтобы снова получилось верное равенство.

7. На плоскости дано 1000 квадратов с стороными, параллельными осем координат. Пусть M — множество центров этих квадратов. Докажите, что можно отметить часть квадратов так, чтобы каждой точка множества M попала не менее чем в один и не более чем в четырехчленных квадратов.

8. На столе стоит чашечные веси и n гриры различных масс. Гриры по очереди ставятся на чашки весов (на каждом шаге со стола берется любая грия и добавляется на ту или ин другую чашку весов).

a) Докажите, что грири можно ставить в таком порядке, чтобы снова появились

61

Левая чашка, затем права, потом снова левая, снова права и так далее.

Этот последовательности результатов взвешивания сопоставим слов из букв L и R: LRLRLR… Здесь буква L обозначает, что перевести левая чашка, а буква R означает, что перевести правая чашка.

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

a) Для каждого числа α найдите все многочлены Q степени не выше трех, коммутирующие с многочленом P (x)=x²−α.

6. Пусть P — многочлен степени 2, k — натуральное число. Докажите, что существует не более одного многочлена степени k, коммутирующего с P.

b) Найдите все многочлены степени 4 и 8, коммутирующие с данным многочленом P степени 2.

г) Многочлены Q и R коммутируют с одним и тем же многочленом P степени 2. Докажите, что они коммутируют между собой.

д) Докажите, что существует бесконечная последовательность многочленов P₂, P₃, P₄, …, Pₙ, …, где Pₙ — многочлен степени k, в котором любые два многочленов коммутируют и многочлен P₂ имеет вид P₂(x)=x²−2.

7. Пусть A — 2n-значное число (первая цифра не нуль). Будем называть число A особым, если оно само является точным квадратом, и числа, образованные его первыми n цифрами и его последними n цифрами, также являются точными квадратами: при этом второе число начинается с цифры 0, но не должно быть равно нуль.

a) Найдите все двух значные и четые значные особые числа.

6. Докажите, что существует хотя бы одно 20-значное особое число.

b) Докажите, что существует не более 10 особых 100-значных чисел.

г) Докажите, что существует хотя бы одно 30-значное особое число. (M460)

8. Марсианский алфавит состоит из 10 букв, и любое трехбуквенное слово образует марсианскую фамилию (то есть на Марсеровно 1000 различных фамилии). По марсианским законом имя марсианна должна состоять из двух букв и получаться из его фамилии вычеркиванем одной буквы.

a) Докажите, что можно составить список из 50 имени так, чтобы марсианн с любой фамилией мог выбрать себе одно из этих имен.

6. Докажите, что нельзя составить такой список менее чем из 40 имен.

b) Докажите, что нельзя составить такой список менее чем из 50 имен.

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

д) Найдите минимальный список имен (двубуквенных), который годился бы, если бы фамилии марсиан составили из k букв. Попробуйте решить эту задачу для k=4, 5, 6 и так далее.

Пожалуйста, второй оказался для восемиклассников более тяжелым (как, впрочем, и для других классов). А особенно сложной — последняя задача № 8 (конечно, если не принять во внимание совсем уже «непосильную» задачу № 7, до которой школьники не дошли, потратив много времени на поиск ответов в других задачах). Последний пункт этой задачи решила всего одна частьница — Гаянэ Шахбозан — ученица физико-mатематической школи № 45 при Ленинградском государственном университете, получившая в результате I премию. Лучшей же работа по итогам двух дней составляет была признана работа ученика той же школи Ильи Захаревича. Вообще надо отметить, что ФМШ при ЛГУ добилась на оптимиде прекрасных результатов: ееоспитники получили 3 первых, 1 вторую и 2 третьих премии; эта школа была нагружена специальным призм «За лучшие результаты».

Вторым днем в десятом классе был исследовательский тур (в прошлом году такой тур был в каждой классе). Десятиклассикам было предложено три сложных задачи, каждая из которых была разбит на несколько пунктов, расположенных в порядке возрастания трудности. Задача № 6 связана с алгеброй, № 8 — арифметической, а задача № 7 — это развитие задачи № 6 для восьмого класса. Листки с условиями задачи, розданные школьником, начиная с словами обращения жорни: «Во второй день оптимизации мы предлаем вам при трудные задачи. Рекомендуем выбрать одну из них и продвинутся в ее решении как можно дальше. Жорни будем значимельно выше оценывать более глубокое исследование одной задачи, чем ответы на лекцию вопросов в нескольких задачи». К сожалению, значительное продвижение в каждой из

62

Восьмиклассики, нагруженные дипломами I степени (слева направо): С. Хлебутин, А. Ляховец, Г. Шахбозян, И. Захаревич.

Девятиклассики, нагруженные дипломами I степени (слева направо): Л. Лисничук, В. Бугаенko, В. Книжник, В. Гальперин, В. Нейман.

Десятиклассики, нагруженные дипломами I степени (слева направо): Д. Флаасс, А. Чурбанов, Г. Рыбников, Л. Гандельман.

предложенных задач ни у одного десятиклассика не оказалось. Так как исследовательский тур проводился в порядке эксперимента, жюри приняло решение считать основными результаты первого дня. Результаты второго дня могли их только уличшить.

В свободное от решения задач время ребята совершили несколько экскурсий по Таллину и его музеям (ведь Таллин — это город-музей средневековья, один из красивейших и интереснейших городов Советского Союза), побивали в laboratorиях самого крупного в Таллине вуза — попыткического института, были в театре оперы и балета «Эстония», встречались с учеными, с талинскими школьниками. 18-го и 19-го апреля для ребят было прочитано несколько интересных лекций: «Геометрия Лобачского и небесная механика» (лектор — профессор МГУ В. А. Алексеев), «Как изменяют расстояния между кривыми» (лектор — доцент МГУ В. А. С кворцов), «Системы счисления» (лектор — профессор И. М. Яглом), «Теорема Абеля-Rуффини» (лектор — кандидат физико-математических наук Д. Б. Фукс), «Теория групп и оптимизации задачи» (лектор — кандидат физико-математических наук А. К. Толпыго). Председатель жюри по 8-му классу кандидат физико-математических наук Н. Н. Константинов провел со школьниками восьмых классов неболько занятий «Matематического кружка». Была организационна встреча жюри с учениками математических школ Таллина.

Пока мы все время говорили только о победительных (ведь все участники Всесоюзной олимпiadы — это победители школьных, областных, и, наконец, ресурсиканских олимпiad). А теперь мы обращаемся к любительям «царицы наук», не попавшим в число победителей. Не огорчайтесь! Недача на олимпiadе — вовсе не показатель несособности к математике. Многие математики не принадлежат к «спортивному» или «олимпидному» типу. Они медленно решают трудные задачи и доказывают сложные теоремы. Важно быть успешным и трудолюбивым человеком, глубоко интересоваться научкой. Научиться математике можно лишь, постоянно решающей, обдумывая всевозможные обобщения, придумывая свои задачи и