Легко ли решать олимпиадные задачи?
Ю.О. Пукас
МОУ «Гимназия г. Троицка» Московской обл.
Осенью 2007 года корреспондент Троицкого телевидения беседовал с Федором Ивлевым, выигравшем в том году Всероссийскую математическую олимпиаду. Корреспонденты – они как дети, их интересуют совершенно неожиданные вещи. Был задан вопрос: «Легко ли решать олимпиадные задачи?», на что Федор ответил, что главное – это уловить идею задачи, ее тему. Очень ценный совет профессионала, попробуем им воспользоваться, решая следующие задачи:
1. У правильного 5000-угольника покрашена 2001 вершина. Докажите, что можно выбрать три покрашенные вершины, которые являются вершинами равнобедренного треугольника. (Московская область, 2001, районный этап, 10-11 классы.)
2. На стороне BC треугольника АВС взята такая точка К, что ВК:КС = 1:3, а на отрезках АК, АС, и КС – такие точки L, M и N соответственно, что LM | | AB, LN | | AC и MN | | AK. Найти отношение площадей треугольников LMN и ABC. (Мехмат МГУ, март 2003.)
3. На плоскости даны n векторов, длина каждого не превосходит 1. Докажите, что можно выбрать a и повернуть все векторы на угол a (некоторые – по часовой стрелке, а некоторые – против) так, чтобы длина суммы векторов нового набора не превосходила 1. (Московская областная, 2008, первый тур, 11 класс.)
4. Может ли ладья обойти все клетки шахматной доски 10х10, побывав на каждой клетке ровно по разу, чередуя ходы длиной в одну и в две клетки? (Считается, что, делая ход в две клетки, ладья не проходит по промежуточной клетке.) (Московская областная, 2008, второй тур, 10-11 классы.)
5. Можно ли покрыть шахматную доску 10х10 прямоугольными плитками размером 4х1? (Заочный конкурс Шестого турнира Архимеда, 1997.)
Среди этих задач есть и очень известные, над другими вы успеете немного подумать, прежде чем я доберусь до них в нашем разговоре. Сделайте это. Почувствуйте «сопротивление материала».
Не знаю, о какой конкретной задаче подумал Федор, отвечая на вопрос корреспондента, я же, слушая его ответ, и с ним в принципе соглашаясь, вспомнил о задаче 1. В свое время, решая ее, я не сразу догадался, что она на принцип Дирихле. Похоже, что и во время самой олимпиады 2001-го года мало кто из участников уловил эту идею. Во всяком случае, Н.Х. Агаханов и О.К. Подлипский в своих книгах помечают эту задачу звездочкой, как особо трудную. Но как только тема раскрыта, трудность исчезает. Вместо правильного 5000-угольника рассматриваем тысячу правильных пятиугольников, в одном из которых будет не менее трех покрашенных вершин, а в правильном пятиугольнике любые три вершины являются вершинами равнобедренного треугольника. Что и требовалось доказать.
Задача 2 малоизвестна. Она предлагалась в марте 2003 года на тестировании мехмата МГУ. Школьники, успешно его преодолевшие, допускались на письменный экзамен. В этой задаче главное – это выяснить, где расположена точка L. Поняв, что точка L лежит на медиане треугольника АВС, мы обязательно доведем решение до численного ответа (3:25).
Далеко не всегда после раскрытия идеи все складывается так же просто и гладко, как в предыдущих примерах. При решении некоторых задач главные трудности возникают в тот момент, когда идея раскрыта (или ясна с самого начала), а вот что делать дальше?
Здесь я собирался в качестве примера не очень простой реализации очевидной идеи показать свое решение задачи 3, начав со слов: «Понятно, что эту задачу надо решать методом математической индукции»… Однако, набирая текст, обнаружил ошибку в своем доказательстве. Подправить то решение не удалось, но я даже рад этому, так как совершенно неожиданно нашел другой путь, с индукцией никак не связанный. Авторское решение надеюсь когда-нибудь увидеть в следующем издании прекрасной книги Н.Х. Агаханова и О.К. Подлипского «Математические олимпиады Московской области», а сейчас покажу свое.
Условие задачи предписывает повернуть соответствующим образом все векторы на выбранный угол a, а затем найти сумму нового набора. Заметим, что тот же самый результат получится, если мы сначала найдем отдельно суммы тех векторов, которые будут повернуты по часовой стрелке, и тех, которые будут повернуты в противоположном направлении, а затем, после соответствующего поворота уже этих двух векторов на тот же самый угол a, найдем их сумму.
Покажем теперь, что если на плоскости даны n векторов (длина каждого не превосходит 1), то их можно разделить на две группы так, что их суммы будут отличаться по длине не более чем на 1, а такие два вектора соответствующим поворотом всегда можно сделать противоположно направленными, достигая требуемого в задаче результата.
Разделение на две группы будем осуществлять следующим образом. Включим в первую группу все векторы и найдем длину их суммы S1 = S0, при этом вторая группа пока пуста и S2 = 0. Если S1 не превосходит 1, результат достигнут, угол поворота a = 0. В противном случае (тогда
S1 > S2) начинаем по одному переводить векторы из первой группы во вторую. На каждом таком шаге S1 и S2 будут изменяться не более чем на 1, а так как после n шагов уже S1 < S2 (S1 = 0, S2 = S0), то неизбежно на каком-то шаге хотя бы раз возникала ситуация, когда длины S1 и S2 различались не более чем на 1. Что и требовалось доказать.
Не исключено, что на выбор мною в задаче с векторами ошибочного пути, связанного с методом индукции, повлияло то, что буквально за один день до областной олимпиады, на которой эта задача встретилась, я показывал ученикам известную задачу, в которой n разбойников делят добычу, а там без индукции никак не обойтись.
В последние годы победители математической олимпиады Московской области по 11-ым классам определяются по результатам только второго тура, на котором участникам предлагается решить пять задач. В этом году призеров было очень много – 36, хотя, на мой взгляд, лишь 12 участников (среди них семеро из московских школ: по одному представителю от лицея «Вторая школа» и гимназии № 1543, и пятеро из моего родного СУНЦа) показали приемлемый результат. А задачи вроде бы не такие и сложные, четвертая в нашем списке – последняя в том варианте (под последним номером она и в варианте 10-го класса), именно ей и будет теперь уделено основное внимание в нашем разговоре. Ее решили шесть учеников 11-го класса и три ученика из
10-го (двое из СУНЦа).
Скорее всего, мое осознанное знакомство с задачами такого типа (на раскраску) началось со статьи П.В. Чулкова в газете «Математика» (№ 22/97), в которой подводились итоги Заочного конкурса Шестого турнира Архимеда. Участниками того конкурса для решения задачи 5 из нашего списка было предложено восемь различных раскрасок шахматной доски 10х10. Мне запомнились и сама та задача, и первая из рассмотренных в той статье раскрасок (рис. 1). Если раскрасить доску в 4 цвета так, как показано на этом рисунке, то каждый прямоугольник 4х1 будет закрывать по одной клетке каждого цвета. Поэтому, если бы мы смогли покрыть нашу доску 25-ю прямоугольниками 4х1, то на доске должно было бы быть по 25 клеток каждого цвета, однако клеток 2-го цвета 26 (клеток 4-го цвета 24, остальных двух по 25). Противоречие. (Такое же решение задачи 5 приведено и в уже упоминавшейся книге «Математические олимпиады Московской области» в разделе «Классические задачи олимпиадной математики».)
Рис. 1
Поначалу казалось, что такая раскраска поможет решить и задачу 4. Действительно, если начинать ходом на две клетки, то получается такое же противоречие, как в задаче 4, так как цепочки из ста ходов (первым ходом мы ставим ладью на любое поле) разделяются на 25 групп по четыре, в результате которых ладья побывает на полях всех четырех цветов. Например:
(1 = 3 – 2 = 4) – (3 = 1 – 4 = 2) – … , или (1 = 3 – 4 = 2) – (1 = 3 – 2 = 4) …, здесь знаком «=» обозначен ход ладьей на две клетки, а знаком «–» – на одну. Но если начинать с короткого хода, то как доказать невозможность скажем такой цепочки:
2 – (1 = 3 – 2 = 4) – ( … ) – … – ( … ) – 3 = 1 – 2?
Здесь клеток 2-го цвета 26, а 4-го цвета – 24. Где противоречие?
Время шло, но ничего у меня не получалось. Возможно, что эту задачу кто-то без труда решит методом Пойа, рассмотрев вспомогательную задачу для меньшей доски, скажем, 2х2, а на ней так легко получить противоречие, ведь ход ладьей на две клетки здесь в принципе неосуществим. Но я этим методом не владею, а в трудных ситуациях больше полагаюсь на озарение свыше. Мартин Гарднер в книге «Есть идея!» цитирует своего коллегу Морриса Клайна, сказавшего в 1955 году: «Творческий процесс нельзя по желанию довести до наивысшей точки… Он проистекает особенно успешно, когда разум предается праздности и воображение свободно расправляет крылья». Так и в этом случае, готовое решение неожиданно возникло в голове в тот момент, когда со словами «довольно, хватит мучиться» я решительно вставал
из-за стола. Десятых долей секунды хватило свободному подсознанию, чтобы завершить работу.
Если раскрасить доску так, как показано на рисунке 2 (и такая раскраска есть в статье Павла Викторовича, но это я обнаружу, уже решив задачу), то клеток каждого цвета будет по 25 (нечетное число!). Делая длинный ход, мы оказываемся на поле того же цвета, что и исходное поле, затем переходим на соседнюю клетку другого цвета, сохраняя уже этот цвет при следующем длинном ходе… Поэтому, если первый ход делается на две клетки, то все цвета должны быть представлены четным количеством клеток. А если же мы начинаем с короткого хода, то кроме, возможно, первой и сотой клеток, остальные должны будут идти парами одного цвета, что неосуществимо.
Рис. 2
Мне кажется, что участники олимпиады просто не добрались до этой задачи, пытаясь решить ту, которая шла в варианте под вторым номером, однако это удалось сделать лишь девятерым. Вот эта задача:
6. Для натурального n обозначим через f (n) количество его натуральных делителей, десятичная запись которых оканчивается на 1 или на 9, а через g (n) – количество его натуральных делителей, десятичная запись которых оканчивается на 3 или на 7. Найдите все n, для которых g (n) не больше, чем f (n).
Я эту задачу еще не решал, так как, раздобыв вариант, после первой сразу перепрыгнул на третью, условие которой напоминало несколько известных мне задач, а затем занялся шахматной доской 10х10. Будем считать, что это наше с вами домашнее задание.