Заключительный этап конкурса имени А. П. Савина «Математика 6—8»

22

КВАНТ 2007/№2

Заключительный этап конкурса имени А.П.Савина

«Математика 6–8»

База отдыха «Берендеевы поляны» под Судиславлем Костромской области уже стала традиционным местом проведения финальных соревнований конкурса имени А.П.Савина. Летом 2006 года здесь состоялся XII финальный летний турнир математических боев, который в очередной раз побил рекорд по количеству команд-участниц: тридцать шесть. На турнире присутствовали школьники из пятнадцати городов. Приехали отдельные команды из Иванова, Кирова, Костромы, Магнитогорска, Перми, Троицка, Харькова. Ну и, конечно же, больше всего команд представила Москва. Примечательная особенность последних турниров – соревнования стали привлекательными для девятиклассников. В организации турнира, кроме журнала «Квант», приняли участие Московский городской дворец детского (юношеского) творчества (председатель оргкомитета турнира Г.Кондаков), образовательная программа «Большая перемена» (руководитель программы депутат областной думы и председатель Федерации профсоюзов Костромской области М.А.Батин), Департамент общего и профессионального образования администрации Костромской области, Фонд математического образования и просвещения. Спонсорскую помощь командам оказали также некоторые организации на местах. Так, школьники Черноголовки выражают свою благодарность Объединенной профсоюзной организации Научного центра «Черноголовка» РАН (зам. председателя Л.А.Ковалева). Работу методической комиссии возглавил А.Шаповалов. В составе комиссии работали опытные члены жюри, не раз принимавшие участие в подобного рода мероприятиях: А.Акопян, М.Берштейн, А.Блинков (зам. председателя оргкомитета), Ю.Блинков, А.Горская, В.Гуровиц, А.Жуков, Д.Калинин, Т.Караваева, И.Раскина, В.Сендеров, А. Скопенков, А.Спивак, С.Токарев (организатор первых летних турниров), В.Трушков, Б.Френкин, Е.Чернышева, В.Шарич. Руководители команд также принимали активное участие в работе жюри:

помогали судить отдельные бои, организовывать и проводить дополнительные интеллектуальные игры («Математическая регата», «Завалинка»). С лекциями перед школьниками выступили А.Скопенков («Найди количество раскрасок»), Н.Нетрусова («Узлы и косы»), А.Шаповалов («Принцип узких мест»). Турнир проводился по традиционной схеме: командная олимпиада в первый день, по результатам которой команды были ранжированы по лигам, затем ежедневные математические бои, между которыми в один из дней прошла личная устная олимпиада.

Призеры личной олимпиады:

6 класс Кадец Борис – Харьков, УВК 45 «Академическая гимназия», Матвеевский Дмитрий – Харьков, ФМЛ 27 (5 класс), Лисичкин Сергей – Харьков, гимназия 47, Коротов Денис – Москва, школа 936;

7 класс Ивлев Федор – Москва, гимназия 1543, Деревицкий Иван – Магнитогорск, школа 5, Малых Софья – Киров, ФМЛ, Николаев Семен – Москва, школа 1189, Садовников Сергей – Волгореченск, школа 2, Южанин Денис – Киров, ФМЛ, Артемьева Галина – Москва, гимназия 1543, Баева Светлана – Киров, ФМЛ, Голицын Владимир – Харьков, ФМЛ 27, Дудкин Александр – Харьков, ФМЛ 27, Криволапов Владислав – Иваново, лицей 67, Макаров Николай – Москва, школа 179, Ноздрин Михаил – Магнитогорск, школа 5, Панфилов Данила – Москва, ФМШ 2007, Пожарский Богдан – Харьков, ФМЛ 27, Редёга Владимир – Москва, гимназия 1543, Тарасов Артем – Киров, ФМЛ, Троицкий Алексей – Москва, школа 1189;

8 класс Соболев Евгений – Харьков, гимназия 47, Маянцев Кирилл – Волгореченск, школа 3, Бочкарев Михаил – Пермь, школа 9 им. А.С. Пушкина, Ефремов Дмитрий – Магнитогорск, школа 5, Таранникова Екатерина – Москва, ФМШ 2007, Турбина Наталья – Ангарск, школа 10, Паламарчук Игорь – Москва, лицей «Вторая школа», Акопян Эмма – Москва, гимназия 1543, Соболев Дмитрий – Харьков, гимназия 47, Смирнова Алена – Москва, лицей «Вторая школа», Гавричев Егор – Москва, лицей «Вторая школа»;

9 класс Андреев Михаил – Москва, школа 57, Кисловская Анна – Кострома, лицей 32,

23

К

М

Ш

Подробные итоги турнира представлены на сайте www.lmsh.ru

Некоторые задачи турнира

(цифры в скобках указывают классы, для которых предлагалась соответствующая задача) 1 (6–7). Кеша вырезал из бумаги треугольник АВС с наибольшей стороной АВ и перегнул его по прямой так, что вершина С попала на сторону АВ и образовался четырехугольник. Укажите множество точек на стороне АВ, куда могла попасть вершина С. А.Шаповалов, В.Гуровиц

Ромаскевич Елена – Москва, гимназия 1543, Бакаев Егор – Кострома, лицей 32, Погребнов Алексей – Москва, гимназия 1543, Марченко Евгений – Москва, гимназия 1543.

Команды-призеры 7 класс гимназия 1543, 7 Б кл., Москва (руководитель М.М.Букина), гимназия 1543, 7 А кл., Москва (руководитель Б.П.Гейдман), «Квантик», Москва (руководитель И.А.Николаева), ФМШ 2007, 7 кл., Москва (руководитель В.В.Ховрина), школа 936, Москва (руководитель Т.П.Зорина);

7–8 классы школа 17, Москва (руководитель Д.А.Коробицын), ФМЛ, 7 кл., Киров (руководитель Л.А.Смирнова), «Большая перемена», 7 кл., Кострома (руководитель Д.А.Калинин), школа 5, Магнитогорск (руководители Н.С.Никифорова, А.В.Устинов), «Эврика», 7 кл., Харьков (руководители Е.Л.Аринкина, А.Л.Берштейн );

8 класс, первая лига школа 5, Магнитогорск (руководители А.В.Христева, А.С.Великих), гимназия 1543, 8 А, Москва (руководитель Т.С.Гейдер);

8 класс, высшая лига «Эврика», 8 кл., Харьков (руководитель Е.Л.Аринкина), Московский городской дворец детского (юношеского) творчества (руководитель С.Е.Дубов), школа 82, 8 кл., Черноголовка (руководитель Л.Н.Головко), школа 9 им. А.С.Пушкина, Пермь (руководитель О.Н.Вязьмина), гимназия 1543, 8 Б кл., Москва (руководитель А.В.Спивак);

9 класс гимназия 1543, 9 кл., 9-3, Москва (руководитель А.В.Спивак), гимназия 1543, 9 кл., 9-1, Москва (руководитель И.В.Раскина), гимназия 1543, 9 кл., 9-2, Москва (руководитель А.В.Спивак), «Большая перемена», 9 кл., Кострома (руководитель Д.А.Калинин).

Все победители награждены дипломами и призами, предоставленными журналом «Квант», а также Фондом математического образования и просвещения.

2 (8). Бумажный треугольник со сторонами a, b, c перегнули по прямой так, что вершина, противолежащая стороне c, попала на эту сторону. Известно, что в получившемся четырехугольнике равны два угла, примыкающих к линии сгиба. Найдите длины отрезков, на которые делит сторону c попавшая туда вершина. А.Шаповалов

3 (7–8). На клетчатой бумаге закрасили многоугольник, периметр которого проходит по линиям сетки. Всегда ли можно вырезать по линиям сетки содержащий его прямоугольник того же периметра? В.Сендеров

4 (7–9). Художник-абстракционист хочет раскрасить клетки доски 8 ѣ 8 в m > 1 цветов так, чтобы выполнялось условие: если одинаково окрашенные клетки A и B граничат с клеткой C, то с C граничат еще две клетки, окрашенные одинаково, причем в цвет, отличный от цветов A и B. (Граничащими называем клетки, имеющие общую сторону.) При каких m он сможет это сделать? Е.Барабанов, И.Акулич

5 (7–8). На числовой прямой отмечены все целые точки. Точки x и y соединяются дугой, если |x – y| простое число. В какое наименьшее количество цветов можно покрасить все целые точки, чтобы любые две соединенные точки были разного цвета? В.Гуровиц

6 (7–8). Найдите все тройки простых чисел, удовлетворяющие равенству

$x^{3} + y^{3} = 2 z^{3}$.

В.Сендеров

7 (7–9). В однокруговом футбольном турнире участвовало 20 команд. Оказалось, что если какие-то две команды сыграли между собой вничью, то хотя бы одна из них завершила вничью не больше трех игр. Каково наибольшее возможное число ничьих в таком турнире? И.Акулич

8 (8). Некоторые из сторон и диагоналей выпуклого n угольника (n > 3), никакие три диагонали которого не пересекаются в одной точке, покрасили в красный или синий цвет. Известно, что синие отрезки не пересекаются и между любыми вершинами есть единственный синий путь. То же верно для красных отрезков.

26

КВАНТ 2007/№2

сумма равна нулю, и ответ на вопросы а), б) отрицательный. Более того, из проведенного рассуждения следует, что ответ на вопрос в) положительный. Напротив, в пункте г) ответ отрицательный: если один игрок проиграл все встречи, а остальные сыграли между собой вничью, то коэффициент последнего игрока отрицателен, а все остальные равны нулю.

Проигравший вылетает

Как известно, круговые турниры – не единственная существующая форма соревнований. В противоположность им, при кубковой (олимпийской) системе проигравший «вылетает», и ничьи невозможны. В таких соревнованиях роль случайности гораздо выше, но зато борьба протекает острее. Если круговому турниру отвечает полный граф (вершины – игроки, ребра – поединки, любые две вершины соединены ребром), то граф олимпийского турнира представляет собой бинарное дерево (циклов нет, и на пути, ведущем от висячей вершины к корню, в каждую промежуточную вершину входят два ребра и выходит одно). Задача 27. Турнир по боксу проходил по олимпийской системе (в каждом круге проигравшие выбывают, отдыхающих нет). Сколько боксеров участвовало в турнире, если по окончании турнира выяснилось, что 32 человека выиграли боев больше, чем проиграли? Решение. При олимпийской системе большинство боев выиграно у тех и только тех боксеров, которые вышли хотя бы в третий тур. Участники третьего тура составляют четверть от общего числа участников. Следовательно, в турнире участвовало 128 боксеров. Интересно сравнить результаты возможных турниров с одними и теми же участниками, но проводимых по разным системам. Приведем две задачи на эту тему (автор К.Фельдман, см. статью Б.Френкина «Жеребьевка для чемпиона» в «Кванте» № 5 за 2000 год). Чтобы выделить то, что зависит от формы проведения, а не от игроков, примем «предположение о стабильной игре»: в каждой паре игроков победитель всегда один и тот же. Ничьи в круговом турнире между такими игроками исключены, поскольку их не бывает в кубковом турнире. Однако мы допускаем, что один игрок выигрывает у другого, другой – у третьего, а при этом третий выигрывает у первого. Задача 28. Прошел чемпионат по круговой системе с участием $2^{N}$ игроков. Теперь тем же спортсменам предстоит разыграть кубок. Выполнено предположение о стабильной игре. Докажите, что существует жеребьевка розыгрыша кубка, при которой чемпион кругового турнира выйдет в финал. Решение. Занумеруем игроков следующим образом. В начало списка поставим тех, кто победил чемпиона, т.е. «опасных». Далее – проигравших ему, т.е.«неопасных». Последний номер дадим чемпиону. В каждом туре розыгрыша кубка составим пары по порядку номеров. Чемпион выступил не хуже «среднестатистического» участника, который выиграл столько же, сколько и проиграл. Значит, число «опасных» не больше числа «неопасных». Все «опасные» попадут в первую половину списка, тогда как чемпион – во вторую. Поэтому чемпион не встретится с «опасным» игроком раньше финала, что и требовалось. Задача 29. В условиях предыдущей задачи докажите, что существует жеребьевка, при которой чемпион кругового турнира получит кубок. Решение. Каждый из «опасных» (выигрывающих у чемпиона) проиграл в чемпионате кому-то из «неопасных» (иначе он бы выиграл больше матчей, чем чемпион, что невозможно). Составим первую пару розыгрыша кубка из «опасного» и такого «неопасного», которому он проиграл.

Следующие пары составляем таким же образом, пока это возможно. Допустим, остались «опасные», которых нельзя включить в такие пары (они проиграли в чемпионате тем «неопасным», которые уже вошли в предыдущие пары). Тогда пусть эти «опасные» играют между собой. Если один из них останется без пары, то поступим следующим образом. Общее число «опасных» не больше числа «неопасных» (поскольку чемпион выступил не хуже «среднестатистического» игрока, который выиграл и проиграл поровну). В составленных парах не больше «неопасных» игроков, чем «опасных», и еще один «опасный» остался без пары. Значит, кто-то из «неопасных» не был еще включен в пару – пусть с ним и играет оставшийся «опасный». Остальные игроки объединяются в пары произвольно. Чемпион выйдет в следующий тур, поскольку играет с «неопасным». Если в остальных турах пары строятся по тому же правилу, то чемпион получит кубок. Это заведомо возможно, если в каждом туре «опасные» составляют менее половины участников. Допустим, что вплоть до некоторого тура мы обеспечили выполнение этого условия. Покажем, что и в следующем туре можно этого добиться. Поскольку в следующий тур выходит половина участников предыдущего, то достаточно показать, что отсеивается не меньше половины «опасных». Но в матчах между ними выбывает каждый второй участник. Только один «опасный» может выиграть у «неопасного». Поэтому достаточно, чтобы в том же туре хотя бы один «опасный» проиграл «неопасному». Как мы видели, в первом туре это выполнено. В последующие туры выходили только такие «опасные», которые проигрывают кому-то из «неопасных», также вышедших в этот тур. И первая же пара составлялась из «опасного» и такого «неопасного», которому он проигрывает. Наше утверждение доказано. В заключение этого параграфа приведем задачу, в которой рассматривается еще одна форма соревнований – игра на вылет. Несмотря на простоту формулировки и решения, задача оказалась трудной для участников отбора на Российскую олимпиаду 1998 года. Задача 30. Группа школьников играет в пинг-понг на вылет. Они установили очередь, вначале играют первый и второй, а в дальнейшем каждый очередной участник играет с победителем предыдущей пары. На следующий день те же школьники снова играют на вылет, но очередь идет в обратную сторону – от последнего к первому. Докажите, что найдутся два школьника, которые играли между собой и в первый день, и во второй. Решение. Соперник последнего игрока в первый день играет со всеми, кто стоит позже него в очереди. С одним из них он играет свою первую партию во второй день.

Еще несколько задач

В приведенных ниже задачах, как правило, требуется выяснить, можно ли выбрать из данного турнира подмножество игроков, обладающее некоторым свойством. Часть этих задач не решены. Задача 31. а) Докажите, что в турнире без ничьих из n участников можно занумеровать их так, что 1-й выиграл у 2-го, 2-й у 3-го,…, (n – 1)-й у n-го и 1-й у n-го. б) Докажите, что в турнире без ничьих либо существует цикл, включающий всех участников, либо можно разбить участников на две группы так, что любой игрок из первой группы победил любого из второй. Задача 32. В круговом турнире с $2^{N}$ участниками не было ничьих. Докажите, что существует цепочка из N + 1 участника, каждый из которых победил всех последующих.