С. А. Генкин, И. В. Итенберг, Д. В. Фомин
ЛЕНИНГРАДСКИЕ МАТЕМАТИЧЕСКИЕ КРУЖКИ
*** 1994 ***
От нас: 500 радиоспектаклей (и учебники)
на SD‑карте 64(128)GB — ГДЕ?..
Baшa помощь проекту:
занести копеечку — КУДА?..
|
СОДЕРЖАНИЕ Предисловие Часть 1 Нулевой цикл 3 Четность 12 Комбинаторика-1 17 Делимость и остатки 26 Принцип Дирихле 39 Графы-1 47 Неравенство треугольника 56 Игры 62 Задачник первого года 72 Часть 2 Индукция 86 Делимость-2 108 Комбинаторика-2 123 Инвариант 140 Графы-2 152 Геометрия 171 Системы счисления 187 Неравенства 196 Задачник второго года 210 Приложение: математические соревнования 228 Ответы, решения, указания 240 Список литературы 264 ФPAГMEHT УЧЕБНИКА (...) не зависит от расстановки плюсов и минусов, а зависит только от количества нечетных чисел в первоначальном наборе. Так как в данном случае их 10 (т.е. четное число), то выигрывает первый игрок. 4. После каждого хода и количество вертикалей, и количество горизонталей, на которые можно поставить ладей, уменьшается на 1. Поэтому игра будет продолжаться ровно 8 ходов. Последний, выигрышный ход будет сделан вторым игроком. 5. Четность числа единиц на доске после каждого хода не меняется. Поскольку сначала единиц было четное число, то после последнего хода на доске не может оставаться одна (нечетное число!) единица. Поэтому выигрывает второй игрок. 6. В процессе игры (сравните с алгоритмом Евклида) обязательно будет выписан наибольший общий делитель исходных чисел. Следовательно, будут выписаны и все числа, кратные ему, не превосходящие большего из исходных чисел. В нашем случае НОД равен 1. Поэтому будут выписаны все числа от 1 до 36. Таким образом игра будет продолжаться 34 хода (два числа были написаны сначала), и выигрывает второй игрок. 7. Эта игра - не совсем шутка. В ней выигрывающий, допустив ошибку, может проиграть. Эта ошибка состоит в том, что он после своего хода оставляет невычеркнутые клетки только в одном столбце или только в одной строке, предоставляя противнику возможность выиграть в один ход. Проигравшим в этой игре является, тем самым, тот, кто сделает этот роковой ход. Заметим, что оставшуюся после вычеркивания горизонтали часть клетчатой доски т х п можно представить себе как доску (m — 1) х п. Аналогично, после вычеркивания вертикали остается доска m х (п — 1). Ситуация, в которой каждый ход является “роковым”, только одна - это доска 2x2. Таким образом, выигрывает игрок, после хода которого она возникла. Однако, как мы видели, при каждом ходе суммарное количество горизонталей и вертикалей на доске уменьшается на 1. Поэтому четность этой суммы в начале игры определяет победителя. В пункте а) выигрывает первый игрок, а в пунктах б) и в) - второй. Заметим, что в пункте б) решающим соображением может быть и симметричная стратегия второго игрока (см. параграф 2). 11. Выигрывает второй. Можно, использовать и центральную, и осевую симметрию. 12. Выигрывает первый. Первый ход в центр доски, а затем - центральная симметрия. 13. В обоих пунктах выигрывает первый игрок, а) Осевая симметрия; б) Центральная симметрия. Решающим соображением является то, что если два симметричных поля не побиты, то поля, с которых оба они бьются, также не побиты. 14. Выигрывает второй. Центральная симметрия. 15. Выигрывает первый. Первым ходом он снимает центральную шашку, а потом играет центрально-симметрично. 16. Выигрывает первый. Первым ходом он уравнивает количество камней в кучках, после чего играет как в задаче 10. 17. Выигрывает первый. Первым ходом он проводит хорду, по обе стороны от которой расположено по 9 вершин. После этого, на каждый ход второго он отвечает аналогичным ходом по другую сторону от этой хорды. 18. В обоих пунктах выигрывает второй игрок. Независимо от хода первого игрока, второй может после своего хода оставить две одинаковые по длине цепочки лепестков. Дальше - симметрия. 19. а) и б) - выигрывает второй. Центральная симметрия, в) Выигрывает первый. Первым ходом он протыкает ряд, состоящий из центральных кубиков четырех слоев 3x3. Дальше - центральная симметрия. 20. В этой игре проигрывает тот, кто отломит кусок ширины 1. Выигрывает первый игрок. Первым ходом он разламывает шоколадку на два куска 5x5. Дальше - симметрия. 21. Выигрывает первый. Первым ходом он ставит крестик в центральную клетку. Затем после каждого хода второго игрока первый ставит крестик в центрально-симметричную клетку. 23. Выигрывает первый игрок. Занумеруем горизонтали и вертикали шахматной доски в естественном порядке. Координаты поля al - (1, 1), поля hS - (8, 8). Выигрышными являются позиции, в которых король стоит на поле с четными координатами. Первый ход - на поле 62. 24. Выигрывает первый игрок. Выигрышными являются позиции с двумя нечетными кучками. Первый ход - съесть кучку из 21 конфеты и разделить кучку из 20 конфет на любые две нечетные кучки. 25. Выигрывает второй игрок. Выигрышными являются позиции, в которых между шашками находится кратное 3 число пустых клеток. 26. Выигрывает первый игрок. Выигрышными являются позиции, при которых в коробке остается 2п — 1 спичка. Первый ход -оставить 255 спичек. 27. Выигрывает первый игрок. Выигрышными являются позиции, при которых в максимальной по количеству камней кучке остается 2п — 1 камень. Первый ход - первую и вторую кучки можно разбивать как угодно, а третью - на кучку из 63 камней и кучку из 7 камней. 28. В этой игре выигрывает тот, кто получит единицу. Побеждает первый. Выигрышными позициями являются нечетные числа. 29. В пункте а) выигрывает второй игрок, в пункте б) - первый. В этой игре выигрышными являются позиции, при которых в каждой кучке нечетное число спичек. 32. Выигрывает второй игрок. Расстановка плюсов и минусов приведена на рис. 123. 33. Переформулируем пункты а) и б) в терминах шахматной доски. Игра а) оказывается тождественной игре из задачи 23. Расстановка плюсов и минусов в пункте б) такая же, как в пункте а) (см. рисунок 45). В обоих пунктах выигрывает первый игрок. 34. Выигрывает первый. Расстановка плюсов и минусов после переформулировки в терминах клетчатой доски показана на рис. 124. |
