МАТЕМАТИЧЕСКИЕ ЗАДАЧИ С РЕШЕНИЕМ. Часть 7
Математические задачи с решениями: расчетные, головоломные и на стратегии математических игр. Источники разнообразные, только решения таких задач не является объектом авторского права.
Круглое поле разделено на 21 сектор. В каждом секторе лежит по фишке. Андрей и Борис играют в следующую игру. За один ход можно взять либо одну фишку, либо две фишки из двух соседних секторов. Начинает Андрей, проигрывает тот, кто не может сделать ход. Кто из игроков может победить, как бы ни играл соперник?
Решение:
Борис.
Приведем стратегию за Бориса, позволяющую ему победить. Первым ходом Андрей может забрать одну или две соседних фишки. Разберем эти два случая отдельно и приведем для каждого из них ответный ход Бориса.
Пусть Андрей первым ходом взял одну фишку. Рассмотрим два соседних сектора, противоположных тому, откуда Андрей взял фишку, и возьмем по фишке оттуда.
Если же Андрей первым ходом взял две фишки, рассмотрим один сектор, противоположной паре соседних секторов, откуда взял яблоки Андрей, и возьмем одну фишку оттуда.
Заметим, что в обоих случаях мы получили картинку, на которой есть два отдельных ряда по 9 фишек в каждом. Значит, сейчас Борис может воспользоваться симметричной стратегией и победить.
На столе лежат
(a) две кучи по 20 камней;
(b) одна куча из 20 камней, другая куча из 30 камней.
Двое игроков играют в следующую игру, делая ходы по очереди. За один ход можно взять любое количество камней, но только из одной кучи.
Выигрывает игрок, взявший последний камень. Кто из игроков может выигрывать при правильной игре: начинающий или его соперник?
Решение:
Используем симметричную стратегию: будем поддерживать в кучках равное количество камней. Пусть в первой кучке х камней, а во второй — y, причём x>y. Тогда возьмём из первой (x-y). Теперь в кучках поровну камней. Соперник обязан взять хотя бы один, что нарушит равенство количеств. Ясно, что после хода соперника в обеих кучках не может остаться по 0 камней. Значит, если изначально в кучках поровну камней, то победит второй, иначе — первый.
Ответ: а) Соперник b) Начинающий.
Имеются две кучки монет: в первой — 102 монеты, во второй — 99 монет. Андрей и Борис играют в такую игру. За один ход игрок из любой кучки берёт 2 монеты, а затем добавляет 1 монету в другую кучку. Проигрывает тот игрок, который не может сделать ход. Андрей и Борис ходят по очереди. Начинает Андрей. Кто выигрывает при правильной игре?
Решение:
Первым ходом Андрей возьмёт 2 монеты из первой кучи и положит одну во вторую. Тогда после этого хода в кучках будет по 100 монет. Далее Андрей будет действовать симметрично. Заметим, что после каждого хода Андрей в кучках будет равное количество монет, причём количество монет всегда будет уменьшаться на 1. Если после хода Андрея в каждой куче более 1 монеты, то у Андрея будет следующий ход. Тогда игра закончится, когда в кучках будет ровно по 1 камню, причём ход будет за Борисом. Значит, Андрей выиграет.
Ответ: Андрей
В двух кучах лежит по 20 камней. Двое игроков, Андрей и Борис, по очереди берут любое количество камней, но только из одной кучи. Начинает Андрей. Выигрывает тот, кто берет последний камень. Кто из игроков может выиграть, как бы ни играл соперник?
Решение:
Приведем стратегию за Бориса, позволяющую ему победить. Будем играть за Бориса симметрично, то есть брать то же количество камней, что и Андрей, но из другой кучи. Покажем, почему у Бориса всегда есть ход согласно этой стратегии.
Заметим, что после хода Бориса, если он смог сходить, в кучках находится поровну камней, то есть картинка симметрична. Значит, сколько бы камней ни взял Андрей из одной кучи, Борис всегда сможет взять столько же из другой.
Итак, мы доказали, что у Бориса всегда есть ход согласно стратегии. Значит, Борис не может проиграть. Но игра когда-то закончится (например, не позже, чем через 40 ходов, ведь камней в сумме всего 40, а каждым ходом берется хотя бы один камень). Поэтому кто-то все-таки проиграет. Это точно не Борис, поэтому проиграет Андрей.
Ответ: Борис.
В двух кучах лежат камни: в одной 20 камней, в другой 30. Двое игроков, Андрей и Борис, по очереди берут любое количество камней, но только из одной кучи. Начинает Андрей. Выигрывает тот, кто берет последний камень. Кто из игроков может выиграть, как бы ни играл соперник?
Решение:
Приведем стратегию за Андрея, позволяющую ему победить. Первым ходом возьмем 10 камней из кучи, в которой было 30 камней. Дальше будем играть за Андрея симметрично, то есть брать то же количество камней, что и Борис, но из другой кучи, как это делал Борис в предыдущей задаче.
На самом деле мы получили в точности предыдущую задачу, в которой Андрей и Борис поменялись местами. Поэтому, раз в той игре выигрышная стратегия была у Бориса, то теперь она есть у Андрея. Значит, Андрей может выиграть, как бы ни играл Борис.
Ответ: Андрей.
Перед Андреем и Борисом лежат 2020 кучек по одному камушку. За один ход разрешается объединить две кучи с одинаковым числом камней в одну. Проигрывает тот, кто не может сделать ход. Кто выигрывает при правильной игре, если начинает Андрей?
Решение:
Заметим, что все кучки в любой момент времени содержат количество камешков равное некоторой степени двойки, так как каждая кучка получается несколькими объединениями (умножениями на два) кучек из 1 камня. Посмотрим на ситуацию, когда кто-то из игроков проигрывает, то есть когда нельзя уже сделать ход. В этот момент 2020 разбилось на несколько различных слагаемых — степеней двоек. Из двоичной системы счисления мы знаем, что любое число единственным образом представляется в виде суммы степеней двоек. Для 2020 это разложение — 1024+512+256+128+64+32+4. То есть в конце всегда остаются эти 7 кучек. Теперь заметим, что за каждый ход количество кучек уменьшается на 1 (две кучки объединяются в одну), то есть из 2020 получится 7 ровно через 2020-7=2013 ходов. Тогда последний ход сделает именно первый, он и победит.
Ответ: Андрей.
Андрей и Борис играют в игру, по очереди зачеркивая клетки доски 3×101. Исходно на доске зачеркнута только центральная клетка. За один ход игрок должен выбрать диагональ (в диагонали может быть 1, 2 или 3 клетки) и зачеркнуть в ней все еще не зачеркнутые клетки. Каждым ходом должна быть зачеркнута хотя бы одна новая клетка. Проигрывает тот, кто не может сделать ход. Начинает Андрей. Кто из игроков может выиграть вне зависимости от ходов противника?
Решение:
Приведем одну из возможных стратегий за Бориса. Покрасим клетки доски в шахматном порядке так, чтобы угловые клетки были черными. В нечетных столбцах крайние клетки будут черными, а в четных белыми. Центральная клетка находится в 51-м столбце, поэтому она сама будет белой.
Каждая диагональ либо полностью черная, либо полностью белая. Обе стратегии будут симметричными, но разными для разных цветов. Для клеток белого цвета будем ходить симметрично относительно центрального столбца (осевая симметрия). Для черных клеток будем ходить симметрично относительно центральной клетки (центральная симметрия).
Докажем, что Борис всегда сможет сделать ход согласно стратегии. Для этого нужно убедиться, что своим ходом он будет зачеркивать хотя бы одну новую клетку. Для черных клеток две диагонали - выбранная Андреем и центрально-симметричная ей, выбранная Борисом не имеют общих клеток. При этом Андрей смог сделать ход, значит, на выбранной им диагонали была незачеркнутая клетка. Так как до хода Андрея ситуация для черных клеток была центрально-симметричной, на диагонали Бориса перед ходом Андрея тоже была незачеркнутая клетка. Андрей не мог ее зачеркнуть, значит, Борис своим ходом зачеркнет хотя бы одну новую клетку.
Для белых клеток ситуация несколько иная: две диагонали, проходящие через центральную клетку, симметричны относительно центрального столбца, но других симметричных белых диагоналей на доске нет. Опять же, перед ходом Андрея ситуация на белых клетках осе-симметрична, то есть и на диагонали, выбираемой сейчас Андреем, и на диагонали, выбранной по стратегии Бориса, есть незачеркнутые клетки. Но единственная общая клетка, которую могут иметь осе-симметричные белые диагонали, зачеркнута с самого начала, поэтому Андрей не может своим ходом зачеркнуть незачеркнутую клетку с диагонали Бориса. Таким образом, Борис своим ходом зачеркнет хотя бы одну новую клетку.
Итак, мы доказали, что у Бориса всегда есть ход согласно стратегии. Так как ходов конечно (игра закончится не позже, чем через 303 хода, когда точно будут зачеркнуты все клетки), Борис победит.
Ответ: Борис.
В ряд выложены 2020 шариков. Андрей и Борис играют в игру, делая ходы по очереди, начинает Андрей. За каждый ход разрешается покрасить один из еще не покрашенных шариков в один из трёх цветов: красный, жёлтый или зелёный (в начале игры все шарики не покрашены). После того, как все шарики покрашены, победа присуждается Андрею, если в ряду найдутся три подряд идущих шарика трёх разных цветов; иначе победа присуждается Борису. Кто из игроков имеет выигрышную стратегию?
Решение:
Для победы Борису достаточно добиться того, чтобы у каждого шарика был соседний того же цвета. Для этого поделим шарики на пары — (1,2), (3,4), …(2019, 2020). Андрей начинает и красит какой-то шарик из пары, после чего Борису нужно покрасить второй шарик из пары в тот же цвет, что всегда можно сделать, действуя по такой стратегии.
Ответ: Борис.
Двое игроков, Андрей и Борис, по очереди ставят шахматные ладьи на клетки доски 11×11, начинает Андрей. Запрещено ставить ладью, если ее бьет одна из ранее поставленных. Проигрывает тот, кто не может сделать ход. Кто из игроков может выиграть, как бы ни играл соперник?
Решение:
Приведем за Андрея стратегию, позволяющую ему победить. Первым ходом поставим ладью в центральную клетку доски, а дальше будем ходить симметрично относительно этой клетки. Покажем, почему у Андрея всегда есть ход согласно этой стратегии.
Пусть до некоторого момента Андрей мог ходить симметрично. Тогда перед ходом Бориса картинка была симметрична относительно центральной клетки. Если Андрей смог поставить ладью, то это значит, что и симметричная клетка до хода Бориса была свободна и непобита ладьей. Осталось заметить, что ладья не может бить ладью, симметричную себе относительно центра, если она не стоит в центральном столбце или центральной строке.
Значит, Андрей сможет всегда сходить согласно своей стратегии.
Заметим при этом, что игра закончится не позже, чем через 121 ход, то есть когда все клетки будут заняты. Это значит, что кто-то все-таки проиграет. Мы доказали, что это не Андрей, значит, проиграет Борис.
Обратите еще раз внимание на последний абзац. На самом деле мы чаще всего доказываем, что согласно стратегии у игрока, за которого мы играем, всегда будет ход. Это означает, что он не проиграет. Чтобы доказать, что он все-таки выиграет, нужно еще объяснять, почему игра закончится.
Ответ: Андрей.
У Андрея и Бориса есть длинная шоколадка 15×100. Они по очереди выедают из неё квадратные куски любого размера (куски можно выедать только по линиям сетки). Начинает Борис. Проигрывает тот, кто не может сделать ход. Кто выигрывает при правильной игре?
Решение:
Пусть первым ходом Борис выедает квадрат 14×14 посередине шоколадки, чтобы вертикальная ось симметрии квадрата и ось симметрии прямоугольника совпадали. После этого хода ось симметрии прямоугольника делит остаток шоколадки на две одинаковые части. При этом никакой последующий ход не может пересечь ось симметрии, потому что куски должны быть квадратными.
Теперь на каждый ход Андрея Борис отвечает симметричным ходом. В итоге, Борис сделает последний ход в игре и победит.
Ответ: Борис.
Числа от 1 до 20 выписаны в строчку. Двое игроков играют в следующую игру. Они по очереди расставляют между ними плюсы и минусы. После того, как все места заполнены, подсчитывается результат. Если он четен, то выигрывает первый игрок, если нечетен, то второй. Кто может выиграть, как бы ни играл другой?
Решение:
Это игра-шутка. Чётность результата не зависит от расстановки плюсов и минусов, а зависит только от количества нечётных чисел в первоначальном наборе. Так как в данном случае их 10 (то есть чётное число), то выигрывает первый игрок.
Ответ: Первый.
На доске написаны числа 35 и 36. За ход разрешается дописать еще одно натуральное число — разность любых двух имеющихся на доске чисел, если она еще не встречалась. Проигрывает тот, кто не может сделать ход. Кто выигрывает при правильной игре: начинающий игру или его партнер?
Решение:
В процессе игры на доске может появиться любое число от 1 до 34 с помощью единицы, которая появляется после первого хода. Так как 34 четное, то выпишет последнее число именно второй, он и победит.
Ответ: Второй.
Вначале на доске написано число 1000000. Андрей за ход должен уменьшить его, разделив нацело на нечетное число от 2 до 100, Борис — на четное от 2 до 10. Проигрывает тот, кто не сможет ходить. Кто из них выиграет при правильной игре?
Решение:
Заметим, что 1000000=2^6×5^6, то есть Андрей может делить только на 5 или 5^2, а Борис — только на 2, 2^2, 2^3 или 2×5. То есть Андрей проигрывает, когда заканчиваются все 6 пятерок, а Борис — когда заканчиваются все 6 двоек. Причем Андрей может забирать только свои пятерки, а
Борис может забирать как двойки, так и пятерки. Значит, Борис может быстрее приблизить Андрея к проигрышу, когда будет забирать его пятерки. Действительно, если каждым ходом Борис будет делить число на 10 (пока делится, то есть пока еще есть пятерки), то не более, чем через 3 хода Андрея и 3 хода Бориса пятерок не останется (но двоек будет хотя бы 3, так как забирает их только Борис), значит, Андрей не сможет походить, а Борис выиграет.
Ответ: Борис.
Двое играют в следующую игру. Каждый игрок по очереди вычеркивает 9 чисел (по своему выбору) из последовательности 1, 2, …, 100, 101. После одиннадцати таких вычеркиваний останутся 2 числа. Первому игроку присуждается столько очков, какова разница между этими оставшимися числами.
Докажите, что первый игрок всегда сможет набрать по крайней мере 55 очков, как бы ни играл второй.
Решение:
Пусть первым ходом первый вычеркнет 9 чисел от 47 до 55. Тогда остальные числа разбиваются на пары с разностью 55: 1-56, 2-57, …, 46-101.
После каждого хода второго игрока, первый может вычеркнуть числа таким образом, чтобы в каждой паре было вычеркнуто либо оба числа, либо ни одного (довычеркивает числа из неполных пар — их нечетное количество, не больше 9 и вычеркивает еще несколько пар полностью). Таким образом, в конце останется пара чисел, разность которых равна 55.
На столе лежат 18 карточек, пронумерованных числами от 1 до 18. Андрей и Борис по очереди берут по одной карточке, пока не заберут все. Начинает Андрей. Борис будет счастлив, если в конце сумма чисел на его карточках окажется составным числом. Может ли Андрей помешать Борису быть счастливым?
Решение:
Будем играть за Бориса. Всегда будем брать число, дающее тот же остаток при делении на 3 что и число, взятое Андреем на предыдущем шаге. Каждый остаток при делении на 3 встречается ровно 6 раз, поэтому мы всегда сможем сделать ход. Заметим, что сумма всех чисел от 1 до 18 делится на 3, а две полученных суммы дают одинаковый остаток при делении на 3 поэтому на самом деле они обе делятся на 3. Значит, наша сумма будет составным числом.
Ответ: Не может.
На шахматной доске 8 × 8 клеток расставлено 8 ладей так, что ни одна из них не бьёт другую. Пробегая мимо доски Витя заметил три ладьи, стоящие на белых полях. Докажите, что есть еще по крайней мере одна ладья, тоже стоящая на белом поле.
Решение:
Пронумеруем горизонтали и вертикали числами от 1 до 8 снизу вверх и слева направо. Заметим, что сумма индексов любой черной клетки четна, а любой белой — нечетна. На всех горизонталях и всех вертикалях стоит ровно по одной ладье. Поэтому сумма всех индексов клеток, на которых стоят ладьи должна быть четной (точнее, она равна 8×9=72. Если бы на доске стояло только три ладьи на белых клетках, а остальные на черных, это бы означало, что сумма индексов всех клеток, на которых расположились ладьи, оказалась нечетной, что противоречит выше сказанному. Значит, есть еще как минимум одна ладья на белой клетке.
На шахматной доске 8 на 8 некоторым образом расставлены 8 ладей, ни одна из которых не бьёт другую. Доказать, что каждую из них можно сдвинуть одновременно в одну из соседних с ней по диагонали клеток таким образом, что и после сдвига ни одна из них не будет бить другую.
Напомним, что шахматная ладья бьёт все клетки горизонтали и вертикали, в которой она стоит, а клетка, соседняя с данной по диагонали — это клетка, имеющая с ней общую вершину, но не сторону. При перемещении ладья может встать на клетку, в которой ранее стояла другая ладья.
Решение:
Разделим доску 8 на 8 на 16 квадратиков 2 на 2 клетки и передвинем каждую попавшую в некоторый квадратик ладью в соседнюю с ней по диагонали клетку этого же квадратика. В частности, если таких ладьи в некотором квадратике окажется две, они поменяются местами. При этом номера вертикалей и горизонталей, в которые сдвигаются ладьи взаимно однозначно определяются номерами вертикалей и горизонталей, в которых ладьи стояли до сдвига. Следовательно, после перестановки две ладьи не могут попасть в одну вертикаль (горизонталь), так как для этого они до неё должны стоять в одной вертикали (горизонтали).
На всех клетках одной диагонали доски 6×6 стоят шашки. Двое играют в следующую игру. За один ход можно сдвинуть шашку на одну клетку вниз. Если при этом шашка падает с доски, игрок ее забирает себе. Выигрывает тот, кто заберет больше шашек. Если игроки набрали поровну — объявляется ничья. Может ли кто-то из игроков победить при правильной игре, и если да, то кто: начинающий или его соперник?
Решение:
Давайте подумаем, в какой момент игрок может своим ходом забрать шашку? Самую нижнюю шашку может забрать любой игрок (если первый не заберет ее первым ходом), а остальные только тогда, когда соперник передвинул ее с предпоследней горизонтали на последнюю. Посчитаем, сколько ходов нужно каждой шашке (кроме самой нужней), чтобы оказаться на предпоследней горизонтали. Самой верхней нужно 4 хода, следующей — 3, дальше — 2 и 1. То есть всего 10 ходов до такой “решающей горизонтали”.
Попробуем поиграть за первого игрока. Первым ходом заберем самую нижнюю шашку. Каждым своим ходом будем забирать шашку, если это возможно, или использовать один из 10 выше посчитанных ходов (именно до предпоследней горизонтали). Если забыть про первый ход первого, то в дальнейшей игре мы будем ходить вторыми. То есть, если соперник не опускает шашки ниже предпоследней диагонали, то эти 10 “безопасных” ходов закончим именно мы. Сопернику придется сдвигать фишки на последнюю горизонталь, откуда мы сразу будем их забирать, то есть обязательно победим. Если же второй опустит какую-то шашку раньше истечения всех 10 “безопасных” ходов, то мы просто заберем ее следующим ходом, и четность оставшихся “безопасных” ходов не изменится (то есть их закончим всегда именно мы). Тем самым мы даже не оставляем возможность второму игроку забрать хотя бы одну фишку (опускает все фишки на нижнюю горизонталь только второй).
По факту стратегия первого выглядит следующим образом: как только можно забрать фишку — забирает, передвигать фишку на нижнюю горизонталь нельзя. Такая стратегия работает именно в силу четности (четности количества “безопасных” ходов), что мы и объяснили выше.
Ответ:Первый.
В каждой клетке доски 2017 × 2017 лежит фишка. За одну операцию можно снять с доски фишку, у которой ненулевое четное число соседей (соседними считаются фишки, расположенные в клетках, примыкающих друг к другу по стороне или углу). Какое наименьшее количество фишек можно оставить на доске с помощью таких операций?
Решение:
Если на доске стоят всего две фишки, то у каждой из них не более одного соседа, и по условию их снять нельзя. Поэтому останется не менее двух фишек. Покажем, как оставить на доске ровно две фишки. Для этого приведем алгоритм, который позволяет очистить от фишек две соседние строки (или два соседних столбца) на доске m × n. Пусть для определенности мы ходим очистить верхние две строки. Занумеруем клетки числами от 1 до n. Сначала снимем фишку с 2-й клетки второй строки (это можно сделать, ибо у нее 8 соседей), далее снимем угловую фишку (у нее теперь 2 соседа), затем 3-ю фишку с первой строки (у нее 4 соседа), далее 2-ю фишку первой строки (у нее 2 соседа) и 1-ю фишку второй строки (у нее также 2 соседа). Далее последовательно двигаясь слева направо будем снимать с доски все фишки первой строки (у каждой из них в момент снятия будет 4 соседа, кроме крайней, у которой будет 2 соседа), а затем аналогично снимать фишки второй строки. Так мы очистим две крайних строки. Применим последовательно эти действия поочередно для строк и столбцов до тех пор, пока не останутся лишь фишки в квадрате 3 × 3. C ними разобраться совсем легко: снимаем центральную, затем в любом порядке 4 угловых, затем оставшуюся верхнюю и, наконец, оставшуюся нижнюю.
Ответ: 2.
В каждой клетке доски 2021×2021 стоит шашка. Двое по очереди снимают с доски любое количество подряд идущих шашек либо из одного вертикального, либо из одного горизонтального ряда. Выигрывает снявший последнюю шашку. Кто выиграет при правильной игре?
Решение:
Предъявим выигрышную стратегию за первого игрока. Первым ходом он снимает центральную шашку. После этого, на каждый ход второго он отвечает симметрично — делает симметричный относительно центральной клетки ход. Таким образом после хода первого игрока доска будет симметрична сама себе относительно центральной клетки.
Ход согласно такой стратегии всегда возможен: раз мы ходили симметрично до этого, то до хода соперника позиция была симметрична. Его ход никак не может помешать такому же ходу симметричному относительно центральной клетки (так как никак не затрагивает центральную клетку), а значит раз он смог снять шашки, то и мы сможем.
Получается, что у нас всегда есть ответный ход согласно стратегии. При этом игра, очевидно, когда-то закончится. А раз первый игрок не проиграет, то не сможет сходить и, соответственно, проиграет, второй игрок.
Ответ: Выигрывает первый игрок.