И. О. Соловьева. Практикум по решению олимпиадных задач по матем. Практикум по решению олимпиадных задач по математике
 Скачать 1.1 Mb.
|
|
7. Принцип крайнего При решении многих задач ключевой идеей оказывается рас- смотрение некоторого объекта, обладающего какими-либо крайни- ми или экстремальными свойствами: наибольшего или наименьше- го числа, самой верхней или нижней точки, ближайшей точки, уг- ловой точки, предельного случая и т.д. Этот метод решения задач называется принципом (правилом) крайнего. Задача 111. По кругу записано 100 чисел, каждое из которых равно среднему арифметическому своих соседей. Докажите, что все 100 чисел равны. Решение. Рассмотрим наибольшее из записанных чисел (или одно из них, если таких чисел несколько). Из того, что оно не меньше своих соседей и равно их среднему арифметическому, сле- дует, что оно равно своим соседям. Проводя аналогичные рассуж- дения далее, получаем, что все числа равны. ■ Примечание. Аналогично можно было рассуждать, рассматри- вая сначала не самое большое, а самое маленькое число. 31 Задача 112. Семь грибников собрали вместе 100 грибов, при- чем никакие двое не собрали одинакового числа грибов. Докажите, что есть трое грибников, собравших вместе не менее 50 грибов. Решение. Расположим грибников по убыванию количества со- бранных каждым из них грибов и рассмотрим трех первых грибни- ков. Если третий собрал 16 грибов, то вместе три грибника собрали грибов не меньше, чем 16 + 17 + 18 = 51, тогда требуемое доказано. Если третий нашел не больше 15 грибов, то оставшиеся четыре грибника собрали вместе не более 14 + 13 + 12 + 11 = 50 грибов. Отсюда заключаем, что первые трое собрали вместе не менее 50 грибов. ■ Задачи. 113. Докажите, что у любого выпуклого многогранника есть две грани с одинаковым числом сторон. 114. В системе Зеленой Собаки 2011 планет. На каждой из этих планет сидит астроном и смотрит в телескоп на ближайшую плане- ту. Докажите, что если попарные расстояния между планетами раз- личны, то найдется планета, на которую никто не смотрит. 115. На плоскости расположено несколько точек, все попарные расстояния между которыми различны. Каждую из этих точек со- единяют с ближайшей. Может ли при этом получиться замкнутая ломаная? 116. В течение рабочего дня каждый депутат посетил заседа- ние парламента. Все депутаты приходили и уходили в разное вре- мя, но никто из них уходя больше не возвращался. Оказалось, что любые два депутата встретились на заседании. Докажите, что был момент, когда все депутаты присутствовали. 117. На каждой клетке шахматной доски поставлено число так, что каждое из чисел равно среднему арифметическому всех своих соседей. Докажите, что все расставленные числа равны между со- бой. 118. На плоскости даны n точек и отмечены середины всех от- резков с концами в этих точках. Докажите, что различных отме- ченных точек не меньше, чем 3 2 n 119. 2010 прямых общего положения (никакие две не парал- лельны, никакие три не проходят через одну точку) разбивают плоскость на части. Докажите, что к любой прямой примыкает тре- угольник разбиения. 32 120. Про 21 число известно, что сумма любых пяти из них по- ложительна. Докажите, что сумма всех чисел положительна. 121. а) Дано шесть натуральных чисел. Все они различны и дают в сумме 22. Найдите эти числа и докажите, что других нет. б) Тот же вопрос про 100 чисел, дающих в сумме 5051. 122. По окружности расположены 6 чисел, при этом каждое число равно модулю разности двух следующих за ним по часовой стрелке. Сумма всех чисел равна единице. Найдите эти числа. 123. Покажите, как любой четырехугольник разрезать на три трапеции (параллелограмм тоже можно считать трапецией). 124. Петя купил "Конструктор", в котором было 100 палочек разной длины. В инструкции к "Конструктору" написано, что из любых трёх палочек "Конструктора" можно составить треугольник. Петя решил проверить это утверждение, составляя из палочек тре- угольники. Палочки лежат в конструкторе по возрастанию длин. Какое наименьшее число проверок (в самом плохом случае) надо сделать Пете, чтобы доказать или опровергнуть утверждение ин- струкции? 8. Игровые задачи Под математической игрой обычно понимают игру двух со- перников, обладающую следующими свойствами. Игроки выпол- няют некоторые действия (ходы) по очереди по определенным пра- вилам. В каждый момент игры состояние характеризуется позици- ей, которая может изменяться только в зависимости от ходов игро- ков. Объявляется также, по каким правилам определяется выиг- равший или проигравший игрок (некоторые игры допускают ни- чью). Добиться выигрыша и есть цель каждого игрока. Примерами математических игр могут служить шахматы, шашки, крестики-нолики. В них результат игры определяется толь- ко действиями соперников. Игры в кости, домино, большинство карточных игр математическими не являются, т.к. в них результат игры зависит не только от действий игроков, но и от случая (рас- клада и т.п.). Если один из игроков может выполнять ходы так, что обеспе- чит себе выигрыш независимо от действий соперника, то говорят, что у него есть выигрышная стратегия. В любой математической 33 игре существует либо выигрышная стратегия для одного из игро- ков, либо ничейные стратегии для обоих (если игра допускает ни- чью). Например, игра крестики-нолики на доске 3 3 является иг- рой с ничейной стратегией для обоих игроков. К какому из пере- численных случаев относятся шахматы и шашки неизвестно. Хотя выигрышные или ничейные стратегии в этих играх существуют, они пока не найдены. В олимпиадных игровых задачах, как правило, требуется опре- делить, кто из игроков (начинающий игру или его противник) име- ет выигрышную стратегию, указать эту стратегию (т.е. инструкцию или алгоритм действий) и обосновать, что она действительно га- рантирует игроку выигрыш независимо от действий соперника. Для поиска выигрышной стратегии могут использоваться разные идеи: поиск стратегии с конца, симметрия, передача хода и другие. 8.1. Поиск стратегии с конца В этом разделе рассматриваются задачи, в которых выигрыш- ная стратегия ищется «с конца» игры. Для этого нужно определить, какой ход является выигрышным, а какой проигрышным. Ход называется выигрышным, если игрок, делающий его, гарантиро- ванно обеспечивает себе выигрыш. Если же после хода игрока у соперника есть возможность выиграть (сделать выигрышные хо- ды), то такой ход называется проигрышным. Задача 125. Играют двое. Первый называет любое число от 1 до 10. Затем они поочередно прибавляют к последнему названному числу число от 1 до 10 и называют сумму. Выигрывает тот, кто назовет 20. Кто из игроков может обеспечить себе выигрыш? Решение. Рассуждаем с конца. Последним ходом будет названо число 20. Если игрок называет какое-либо число от 10 до 19, то его соперник может выиграть, назвав сразу число 20, следовательно, это проигрышные ходы. Если игрок назовет число 9, то любой ход соперника является проигрышным (он может называть только чис- ла от 10 до 19), следовательно, «ход на 9» является выигрышным. Значит, выигрывает игрок, который может назвать число 9. Эта возможность есть у первого игрока при первом же ходе. ■ Таким образом, принцип решения игровых задач методом рас- 34 суждения «с конца» состоит в следующем: нужно определить вы- игрышные и проигрышные ходы. Ход является выигрышным, если после него любой ход соперника является проигрышным. Ход яв- ляется проигрышным, если после него у соперника есть хотя бы один выигрышный ход. Задача 126. Условие задачи то же, что в задаче 125, но выиг- рывает игрок, назвавший число 100. У кого из игроков есть выиг- рышная стратегия? Решение. Проигрышными являются ходы от 90 до 99 (после них соперник сразу назовет 100), 89 – выигрышный ход (после него можно сделать только проигрышные ходы от 90 до 99), проигрыш- ные – от 79 до 89, а выигрышный – 78 и т.д. Перечислим остальные выигрышные ходы: 67, 56, 45, 34, 23, 12, 1. Следовательно, выиг- рывает первый игрок, который первым ходом называет число 1, а в каждый следующий его ход он должен прибавить число, которое в сумме с числом, прибавленным соперником, составляет 11. ■ Задача 127. «Поставь на ноль». Имеется клетчатая полоска, клетки которой пронумерованы, начиная с нуля (рис. 12). Фишка стоит на поле 25. Двое игроков по- очередно передвигают фишку на 1, 2, 3 или 4 клетки влево. Проигрыва- ет тот, кто не может сделать очеред- ной ход. Кто выигрывает при правильной игре? (Игра называется правильной, если игрок, имеющий выигрышную стратегию, дей- ствует по этой стратегии). Решение. Рассуждаем с нуля (здесь заканчивается игра). Оче- видно, что ход на 0 является выигрышным, на 1, 2, 3 и 4 – проиг- рышные (с них за один ход можно попасть на 0), на 5 – выигрыш- ный (с 5 любой ход ведет к проигрышу) и т.д. Выигрышными бу- дут все клетки с номерами, кратными 5 (рис. 13). Таким образом, первый ход первого игрока будет проигрыш- ным (он не может поставить фишку на число, кратное пяти). Выиг- Рис. 13 0 1 2 3 4 6 в п п п п п в п … п в 1 п п п … 24 5 9 7 10 8 23 25 Рис. 12 0 1 2 3 25 24 35 рывает второй, он должен ставить фишку на числа, кратные пяти. ■ Примечание. Можно заметить, что в результате получилась се- рия (в, п, п, п, п), которая повторяется. В аналогичных задачах (см. задачу 129) нужно найти такую повторяющуюся серию. При этом нужно иметь ввиду, что такая серия может идти не с самого начала (точнее, не с самого конца) игры. Задачи. 128. Играют двое. Первый называет любое число от 1 до 10. Затем они поочередно прибавляют к последнему названному числу число от 1 до 10 и называют сумму. Проигрывает тот, кто назовет трехзначное число. Кто выигрывает при правильной игре? 129. Условие то же, что в задаче 127, но передвигать фишку можно а) на 1, 2 или 4 клетки; б) на 1, 3 или 4 клетки; в) на 1, 2 или 6 клеток; г) на 2 или 5 клеток; д) на 2, 4 или 7 клеток? 130. Имеется кучка из 25 камней. Игроки по очереди берут из этой кучки 1, 2 или 3 камня. Проигрывает тот, кто не может сде- лать очередного хода. Примечание. Очевидно, что эта игра изоморфна 1 игре «Поставь на ноль», в которой фишку можно передвигать на 1, 2 или 3 клетки. Поэтому решив одну задачу, можно указать решение и другой. 131. В куче 25 камней. Игроки по очереди могут взять из кучи 2 камня, 4 камня или 7 камней. Проигрывает тот, кто не может сде- лать очередного хода. Кто победит при правильной игре? 132. В куче лежат 50 камней. Двое поочередно добавляют в нее любое количество камней от 1 до 10. Выигрывает тот, кто первым сумеет довести количество камней до двухсот. Кто выигрывает? 133. «Одинокий ферзь». На шахматной доске на поле f8 стоит ферзь. Игроки по очереди передвигают его на любое количество клеток влево, вниз или по диагонали влево вниз. Выигрывает тот, кто поставит ферзя на поле а1. Кто выиграет при правильной игре? Сформулируйте игру о камнях, изоморфную игре «Одинокий ферзь». 134. Волк и Заяц играют в следующую игру. На доске написа- но некоторое натуральное число. Ход состоит в том, чтобы вычесть 1 Игры называют изоморфными, если они «одинаково устроены», т.е. между их условиями существует взаимно однозначное соответствие. 36 из числа какую-нибудь его ненулевую цифру и написать на месте старого числа получившееся число. Выигрывает тот, кто получит ноль. Начинает игру Волк. Какое число первоначально должно быть написано, чтобы Заяц имел выигрышную стратегию? 8.2. Симметрия В некоторых игровых задачах наличие удачного хода может обеспечиваться симметрией. Задача 135. Двое по очереди кладут пятаки на круглый стол так, чтобы они не накладывались друг на друга. Проигрывает тот, кто не может сделать очередного хода. Кто выигрывает при пра- вильной игре? Решение. Выигрывает первый: сначала он должен положить пятак так, чтобы центры пятака и стола совпали. После этого на каждый ход второго игрока начинающий должен отвечать симмет- рично относительно центра стола. После каждого хода первого иг- рока расположение монет на столе будет симметричным относи- тельно центра. В этом случае симметричные точки одновременно либо заняты монетами, либо не заняты. Поэтому если есть возмож- ность сделать ход второму игроку, то есть возможность сделать симметричный ход и первому игроку. Поскольку игра не может продолжаться бесконечно, проиграет второй. ■ В игровых задачах на использование симметрии нужно стре- миться создавать симметричную ситуацию, чтобы иметь возмож- ность делать ответные ходы, симметричные ходам противника. Выбирая стратегию, основанную на симметрии, важно помнить, что очередному симметричному ходу может помешать только что сделанный ход противника. Рассмотрим пример. Задача 136. Игроки по очереди закрашивают клетки квадрата 10 10 , причем за один ход можно закрасить одну из трех фигур, изображенных на рис. 14, дважды закрашивать клетку нельзя. Выигры- вает тот, кто закрашивает последнюю клетку. Кто имеет выигрышную стратегию? Решение. Выигрывает второй. Выигрышная стратегия: после каждого хода первого игрока второй должен закрашивать клетки, Рис. 14 37 расположенные симметрично относительно центра квадрата клет- кам, закрашенным только что первым игроком. После каждого хо- да второго игрока картина на доске будет симметричной относи- тельно центра. В этом случае симметричные клетки одновременно либо закрашены, либо не закрашены. Поэтому если есть возмож- ность сделать ход первому игроку, то есть возможность сделать симметричный ход и второму игроку. ■ Примечание. Если воспользоваться осевой симметрией, то по- сле некоторых ходов первого игрока будет невозможно закрасить симметричные клетки (некоторые из них могут быть только закра- шены первым игроком). Симметрия в игровых задачах не обязательно имеет геометри- ческий смысл. Задача 137. Имеются две кучки камней – по 7 в каждой. За ход разрешается взять любое количество камней, но только из одной кучки. Проигрывает тот, кому нечего брать. Кто выиграет при пра- вильной игре? Решение. Выигрывает второй при помощи симметричной стра- тегии: каждым своим ходом нужно брать столько же камней, сколько предыдущим ходом взял первый игрок, но только из дру- гой кучки. Таким образом, у второго игрока всегда есть ответный ход. ■ Задачи. 138. На доске размером 7 7 двое по очереди закрашивают по одной клетке так, чтобы закрашенные клетки не имели общих то- чек. Проигрывает тот, кто не может сделать ход. Кто выиграет при правильной игре? 139. На окружности даны n 2 точек. Двое по очереди проводят хорды с концами в этих точках так, чтобы хорды не пересекались (хорды могут иметь общие концы). Проигрывает тот, кто не смо- жет провести хорду. Кто победит при правильной игре? 140. Имеются три одинаковые кучки камней. Двое играющих берут по очереди любое количество камней из любой кучи, но только из одной. Выигрывает взявший последние камни. Кто выиг- рает при правильной игре? 141. Имеются две кучки камней: в одной – 30, в другой – 20. За ход разрешается брать любое количество камней, но только из од- 38 ной кучки. Проигрывает тот, кому нечего брать. Кто может обеспе- чить себе победу? 142. Есть клетчатый прямоугольник 10 3 клеток. Двое играют в следующую игру. Ходят по очереди. За один ход можно закра- сить квадрат 1 1 , 2 2 или 3 3 клетки. Красить уже покрашен- ные клетки нельзя. Проигрывает тот, кто не может сделать ход. Кто выигрывает при правильной игре? 143. В строчку написано несколько минусов. Два игрока по очереди переправляют один или два соседних минуса на плюс. Вы- игрывает переправивший последний минус. Кто выиграет при пра- вильной игре? 144. а) Соты имеют форму квадрата 9 9 (рис. 15). Все квад- ратики, кроме центрального (С), заполнены медом. В центре – де- готь. За один ход разрешается раз- ломить соты вдоль любой верти- кальной или горизонтальной линии и съесть ту часть, где нет дегтя. Проигрывает тот, кому остался только деготь. Кто выиграет при правильной игре? б) Задача та же, но деготь нахо- дится не в центре, а в клетке А. в) Деготь находится в клетке В. 145. Двое по очереди ставят слонов (цвет значения не имеет) на клетки шахматной доски. Нельзя ставить фигуру под бой ранее поставленной (не важно, самим иг- роком или его противником) фигуры. Кто не может сделать ход, проигрывает. Кто победит при правильной игре? 146. Двое по очереди обрывают лепестки у ромашки. За один раз можно оборвать один или два соседних (рядом растущих) ле- пестка. Выигрывает тот, кто сделает последний ход. Кто выиграет при правильной игре? 147. Двое заполняют по очереди таблицу 3 3 произвольными действительными числами. Затем первый находит сумму чисел первой и третьей строк, а второй – сумму чисел первого и третьего столбцов. Выигрывает тот, у кого сумма больше. Кто может обес- Рис. 15 С А В 39 печить себе победу? 148. Дана клетчатая доска 10 10 . За ход разрешается покрыть любые две соседние клетки доминошкой (прямоугольником 2 1 ) так, чтобы доминошки не перекрывались. Проигрывает тот, кто не может сделать ход. У кого из игроков есть выигрышная стратегия? 149. В каждой клетке доски 11 11 стоит шашка. За ход разре- шается снять с доски любое количество подряд идущих шашек ли- бо из одного вертикального, либо из одного горизонтального ряда. Выигрывает снявший последнюю шашку. Кто выигрывает при пра- вильной игре? 150. Двое по очереди разламывают шоколадку 10 5 . За ход разрешается сделать прямолинейный разлом любого из имеющихся кусков вдоль углубления. Выигрывает тот, кто отломит дольку 1 1 . Кто выигрывает при правильной игре? 151. Двое играют на доске 9 9 . Начинающий ставит крести- ки, его соперник – нолики (по одному за ход). В конце подсчитыва- ется, сколько имеется строчек и столбцов, в которых крестиков больше, чем ноликов, – это очки, набранные первым игроком. Ко- личество строчек и столбцов, в которых ноликов больше – очки второго. Тот из игроков, кто наберет больше очков, побеждает. У кого из игроков есть выигрышная стратегия? |