МАТЕМАТИЧЕСКИЕ ЗАДАЧИ С РЕШЕНИЕМ. Часть 11
Математические задачи с решениями: расчетные, головоломные и на стратегии математических игр. Источники разнообразные, только решения таких задач не является объектом авторского права.
На столе лежит
(a) 100 спичек;
(b) 101 спичка.
Андрей и Борис играют в следующую игру, делая ходы по очереди. Начинает Андрей. За один ход можно взять 1, 2, 3 или 4 спички со стола. Выигрывает игрок, взявший последнюю спичку. Кто из игроков может выиграть, как бы ни играл соперник?
Решение:
Используем стратегию дополнения: после каждого нашего хода будем пытаться оставить число спичек, кратное 5. Действительно, если в данный момент число спичек делится на 5, то соперник никак не сможет оставить количество, кратное 5. Если же спичек не кратно 5, то мы можем взять остаток от деления на 5. Ясно, что после хода соперника 0 спичек остаться не может. Значит, если спичек изначально кратно 5, то победит Борис, а иначе — Андрей.
Ответ: a) Борис б) Андрей
Есть куча из n спичек. Разрешается брать от 1 до 10 спичек, выигрывает взявший последнюю спичку. При каких n выигрывает начинающий?
Решение 1:
Проанализируем выигрышные и проигрышные позиции. Понятно, что все числа от 1 до 10 — выигрышные.
Число 11 — проигрышное, так как из нее можно попасть только в выигрышные позиции 1–10. Позиции 12–21 — выигрышные, ведь из них можно попасть в 11. Число 22 — проигрышное, и так далее.
Легко видеть, что все позиции, кратные 11, являются проигрышными, а остальные — выигрышными.
Тогда, в силу симметричности позиции перед ходом Бориса, число Андрея отличается от чисел в своей строке и своем столбце. Осталось лишь отметить, что игра конечна, а раз у Андрея всегда есть ход, то он не проиграет, а значит, победит.
Еще раз хочется обратить внимание на то, как мы определяем, является ли позиция выигрышной или проигрышной: для того, чтобы позиция была выигрышной, достаточно ОДНОГО хода, ведущего в проигрышную позиция, а вот чтобы позиция была проигрышной, ВСЕ ходы должны вести в выигрышные. И во время решения мы ровно это и определяем.
Другой подход — дополнение хода соперника до определенного значения.
Решение 2:
При количестве спичек, кратном 11, будем играть за второго игрока, дополняя количество спичек, взятых на предыдущем ходу первым игроком, до 11. Другими словами, если первый игрок только что взял x спичек, то мы берем 11-x. Сразу отметим, что количество спичек, которое мы должны брать в ответ на ход первого, также от 1 до 10, то есть с этим проблем не возникает. Кроме того, после нашего хода количество спичек после пары ходов — соперника и нашего — кратно 11, поэтому последнюю спичку заберет именно второй игрок.
При количестве спичек, не кратном 11, играем за первого игрока. Первым ходом берем столько спичек, чтобы количество оставшихся спичек было кратно 11, а дальше повторяем предыдущую стратегию.
Ответ: При n, не кратных 11.
Есть 101 клетка. Двое поочередно слева направо вписывают в эти клеточки по одной из цифр от 0 до 9. Если после заполнения всех клеток сумма всех записанных цифр будет делиться на 11, то выиграет игрок, ходивший первым, а если не будет делиться на 11 — то вторым. Какой из игроков выиграет при правильной своей игре и любой игре соперника? Ответ обосновать.
Решение:
Заметим, что первый игрок всегда может дописывать к предыдущему числу второго такое, что их сумма равна девяти. Тогда в парах (2,3), … (100,101) сумма будет равна девяти, откуда вся сумма в клетках 2,3…101 равна 50×9=450 (остаток от деления на 11= -1). Выберем цифру в первой клетке, равной 1 и вся сумма будет кратна 11 при любой игре второго.
Ответ: Первый.
Андрей и Борис играют в игру на клетчатой доске 18×18. За один ход Андрей закрашивает одну клетку, а Борис — сразу две. Начинает Андрей. Проигрывает тот игрок, после хода которого какие-то шесть отмеченных клеток будут расположены в ряд по вертикали или горизонтали. Кто из игроков имеет выигрышную стратегию?
Решение:
Разобьем все клетки на тройки следующим образом: в каждой строке разбиваем их на тройки с номерами х, х+6, х+12. Играем за Бориса. Если Андрей ходит в некоторую тройку, то мы закрашиваем оставшиеся две клетки этой тройки.
Покажем, что тогда Борис никогда не проиграет. Пусть он не может сходить в соответствующую тройку. Тогда возможны два случая. Если после его хода образовывается вертикальный прямоугольник в одном из столбцов, то к этому момент уже был бы прямоугольник в столбце, в который Андрей сделал последний ход, то есть такое невозможно. Если же будет образовываться горизонтальный прямоугольник, то все его клетки будут из разных троек, но тогда клетка, в которую до этого сходил Андрей, также будет лежать в горизонтальном прямоугольнике, состоящем из клеток тех же троек.
Ответ: Борис.
Дан куб, каждая грань которого — это клетчатое поле размером 2015 на 2015 клеток. В центре одной из граней стоит пешка. Андрей и Борис передвигают пешку по клеткам куба. Андрей может ходить только на соседнюю по стороне клетку (разрешается переходить на другую грань, если клетки соседние по стороне), а Борис может поставить пешку в любую клетку. Пешка красит за собой клетки. На закрашенную клетку пешку двигать нельзя. Изначальная клетка (центр грани) закрашена. Андрей ходит первым. Проигрывает тот, кто не может сделать ход. Кто выиграет при правильной игре обоих?
Решение:
Приведём выигрышную стратегию для Андрея. Число клеток на поверхности чётно (равно 2015×2015×6). Разобьём всю поверхность куба на доминошки; доминошки не пересекаются и покрывают весь куб. Легко видеть, что такие примеры есть. В начале хода Андрея пешка стоит в какой-то доминошке. Андрей ходит во вторую клетку доминошки. Если Андрей до этого действовал в соответствии с этой стратегией, то вторая клетка доминошки не закрашена, и сделать в неё ход можно. Очевидно, что последний ход сделает Андрей — хотя бы потому, что он всегда может сделать ход.
Есть 3 кучи: 100, 101 и 2020 камней. Андрей и Борис играют в игру, по очереди удаляя по одному камню из двух разных куч. Игрок, который не может сделать ход, проигрывает. Начинает Андрей. У кого из игроков есть выигрышная стратегия?
Решение:
Первым ходов возьмем по 1 камню из куч 101 и 2020. Далее просто повторяем ходы Бориса. Заметим, что за каждую пару ходов, вес большой кучи уменьшается не более чем на 2, в то же время суммарный вес двух маленьких куч уменьшается хотя бы на 2. Тогда понятно, что мы всегда сможем сделать ход, так как в маленьких кучах, в которые сходил Борис, будет нечетное число камней, а в большой куче будет больше камней, чем в двух других кучках в сумме. Поэтому рано или поздно мы придем в ситуацию, когда обе маленькие кучки станут нулями. Тогда в этот момент Борис не сможет сделать ход.
Ответ: У Андрея.
На клетчатой плоскости нарисован прямоугольник 3×2021 все клетки которого покрашены в синий цвет. Андрей и Борис по очереди перекрашивают в красный цвет две необязательно соседние синие клетки, расположенные либо в одной строке, либо в одном столбце. Начинает Андрей. Игрок, который не может сделать ход, проигрывает. Кто из игроков может обеспечить себе выигрыш вне зависимости от игры соперника?
Решение:
Пронумеруем клетки в каждом столбце сверху вниз числами 1, 2, 3. Играем за первого игрока. Сначала перекрасим две клетки 1, 3 в произвольном столбце. Каждый ход будем делать по следующему правилу. Если второй игрок ходит в клетки с номерами 1,i в некотором столбце, то мы ходим в клетки с номерами 1, j для любого j в некотором другом столбце. Иначе после хода второго проверяем, есть ли столбцы, в которых перекрашены клетки 2, 3, а клетка 1 — пустая. В таких столбцах выбираем клетки с номерами 1. Мы выберем не больше 2 клеток, так как свои ходом второй игрок может создать не более двух таких столбцов. Далее, если мы выбрали меньше 2 клеток, то до 2 клеток дополним любыми синими клетками с номерами 1 и перекрасим их. Делам так, пока можем.
Предположим, что мы не можем сделать очередной ход по нашему правилу. Заметим, что до предыдущего хода второго игрока не меньше половины перекрашенных клеток имели номер 1. Тогда всего покрашено не более 2×2021+2 клетки. То есть игра еще не закончена, поскольку есть строка, в которой не перекрашены хотя бы 2 клетки. С другой стороны, до последнего хода второго игрока количество не перекрашенных клеток в первой строке было четно. Если мы не можем сделать ход 1, j то это значит, что до этого второй игрок сделал ход 1, i. Тогда столбцов с перекрашенными клетками 2, 3 не образовалось. То есть в первой строке осталась синяя клетка, ее можно перекрасить вместе с другой клеткой из ее столбца — противоречие. Если же мы не можем перекрасить две синие клетки из первой строки, то это означает, что первая строка полностью закрашена.
Далее будем ходить произвольно. Предположим, что в некоторый момент мы не можем сделать ход. Тогда в каждой строке осталось не более одной синей клетки, но при этом первая строка заполнена. Количество синих клеток всегда остается нечетным, причем в данный момент их не больше 2. Тогда ровно 1 клетка не перекрашена. А значит, всего было совершено ходов (2021×3-1)/2=3031, то есть последний ход сделали мы — противоречие.
Ответ: Андрей.
Андрей и Борис по очереди заполняют клетки квадратной таблицы 6×6 целыми числами. Каждым ходом игроки ставят одно число в любую из пустых клеток. Первым ходит Андрей. Когда вся таблица заполнится, они подсчитывают суммы чисел, стоящих в строках и в столбцах — всего 12 сумм. Если хотя бы 6 из них окажутся одинаковыми, то выиграет Борис, иначе — Андрей. Может ли Борис всегда выигрывать?
Решение:
Разобьем доску на вертикальные доминошки. Будем на месте Бориса на очередном шаге в ту же доминошку, куда только что ходил Андрей, ставить число, противоположное числу Андрея. Тогда по окончании игры сумма в каждой доминошке будет равна 0, поэтому и в каждом столбике сумма будет равна 0, то есть хотя бы 6 сумм будут равны 0.
Ответ: Да, может.
Два игрока, Андрей и Борис, имея каждый по 74 камешка, решили сыграть в такую игру: они по очереди будут выкладывать на стол камешки, за один ход — одну, две или три, а выиграет тот, кто положит на стол сотый по счёту камешек. Начинает Андрей. Кто может выиграть в такой игре, независимо от того, как будет действовать соперник?
Решение:
Если бы количество камней было неограниченным, то Борис мог бы просто дополнять ходы Андрея до четырёх и победить после своего 25-го хода. Однако заметим, что если Андрей будет всегда выкладывать по одному камешку, то Борису придётся выкладывать по три, а значит ему не хватит камней. Таким образом понимаем, что Борису необходимо сэкономить камешки. Если первым ходом Андрей положит два или три камешка, то Борис положит два или один и далее ему хватит камешков для победы.
Пусть Андрей положил первым ходом один камешек, тогда Борис в ответ положит также один. Далее возможны три варианта развития событий:
1) Если Андрей снова положил один камешек, то Борис также кладёт один, а далее дополняет до четырёх.
2) Если вторым ходом Андрей положит два камешка, то всего на столе будет четыре. Далее Борис положит один. Андрей не должен допустить, чтобы после хода Бориса количество камней делилось на 4, поэтому он будет выкладывать три Камешка. Далее всегда Борис будет выкладывать один камешек, вынуждая Андрея выкладывать три, но Андрей не сможет выложить сотый, так как ему не хватит камешков.
3) Если вторым ходом Андрей выложит три камешка, то Борис также ответит тремя, а далее будет дополнять.
Ответ: Борис.
Борис ставит короля на шахматную доску 8×8 после чего они с Андреем начинают играть в следующую игру. Каждый игрок своим ходом должен передвинуть короля по правилам шахмат (на соседнюю по стороне или диагонали клетку). Нельзя наступать на те клетки, в которых король бывал ранее. Начинает Андрей, ходы делают по очереди, проигрывает тот, кто не может сделать ход. Кто из игроков может победить, как бы ни играл соперник?
Решение:
Разобьем клетки доски на пары-доминошки следующим образом:
Пусть Андрей своим ходом переставляет короля из текущей клетки в парную ей. Заметим, что Андрей всегда сможет так сходить, потому что после его хода во всех доминошках король побывал или на обеих клетках, или ни на одной. Тогда Борис может переставить короля только в доминошку, где обе клетки не посещены. В итоге, Андрей сделает последний ход и победит в игре.
Ответ: Андрей.
На столе лежит 2025 камней. Андрей и Борис играют в игру по следующим правилам. Ходят по очереди, начинает Андрей. За один ход можно взять со стола 1 или 2 камня, но один и тот же игрок два раза подряд не может брать 2 камня. Проигрывает не имеющий хода. Кто из игроков сможет обеспечить себе победу вне зависимости от игры противника?
Решение:
Опишем выигрышную стратегию Андрея. Первым ходом он возьмет 1 камень. Это не наложит ограничений на его второй ход, поэтому он сможет дополнить ход Бориса так, чтобы после этого осталось 2021 камней.
Дальше Андрей будет действовать так, чтобы за две пары ходов было взято ровно 5 камней. Борис своими двумя ходами сможет в сумме взять 2 или 3 камня, поэтому Андрей сначала возьмет 1 камень (это не наложит ограничений на его второй ход), а потом, когда уже будет знать, что сделал Вася, дополнит его ход до 5 в сумме. При разборе каждой пятерки камней последний ход остается за Андреем. Поэтому, в частности, он возьмет последний камень и выиграет.
Ответ: Андрей.
На доске написаны числа 1, 2, …, 100. За ход можно стереть 4 числа, сумма которых делится на 101. Андрей и Борис ходят по очереди, первый ходит Андрей. Проигрывает тот, кто не может сделать хода. Кто из игроков может выиграть, как бы ни играл соперник?
Решение:
Андрей разбивает все числа на 50 пар с суммой 101. Первым ходом он берет любые две пары целиком. Остается 48 пар. Вообще, после хода Андрея будут оставаться только целые пары, причем их количество кратно 4. Борис может взять либо две целые пары, либо одну целую пару и два числа из разных пар, либо по числу из 4 пар. В ответ Андрей берет все числа из начатых пар и столько же целых пар, сколько Борис. В результате пары ходов Бориса и Андрея они возьмут вместе ровно 4 пары, то есть 404 в сумме. Поскольку 404 и сумма Бориса кратны 101, то и сумма Андрея тоже, а число оставшихся пар уменьшилось на 4. Поэтому последний ход сделает Андрей и выиграет.
Ответ: Андрей.
На столе лежат N кучек по одному ореху в каждой (N>2). Двое ходят по очереди. За ход нужно выбрать две кучки, где числа орехов взаимно просты, и объединить эти кучки в одну. Выиграет тот, кто сделает последний ход. Для каждого N выясните, кто из играющих может всегда выигрывать, как бы ни играл его противник.
Решение:
Для выигрыша ему достаточно до самого конца объединять имеющиеся кучки так, чтобы была одна большая кучка и несколько кучек по одному ореху. При такой стратегии сохраняется инвариант — нечетность максимальной кучки после хода второго. В случае нечётного N второй придерживается такой стратегии до конца, а в случае чётного — до позиции из четырёх кучек N-3,1,1 и 1 после чего на любой ход первого: N-2,1,1 или N-3,2,1 — отвечает ходом N-2,2.
Ответ: Всегда выигрывает второй.
Андрей и Борис играют в игру. Они по очереди (начинает Андрей) выписывают по одной цифре, пока не получится шестизначное число. При этом первая выписанная цифра ненулевая и все выписанные цифры различны. Андрей выигрывает, если полученное шестизначное число делится хотя бы на одно из чисел: 2, 3 или 5. Если этого не случается, то выигрывает Борис. Кто выигрывает при правильной игре?
Решение:
Пусть a1b1a2b2a3b3 - итоговое шестизначное число. Пусть также A=0, 2, 4, 5, 6, 8 и B=1, 3, 7, 9. Заметим, что если Борис своим третьим ходом поставит цифру из множества A, Андрей выиграет, поскольку полученное число будет делиться на 2. Значит, b3 принадлежит множеству B.
Пусть Андрей первым ходом выберет цифру a1=3, а вторым ходом - цифру a2=9. Если Борис на первом или втором ходу выберет цифру из множества B, то своим третьим ходом Андрей заберет последнюю оставшуюся цифру из множества B, и Борис вынужден будет взять свою цифру b3 из A, что приведет к его проигрышу. Значит, Борис вынужден взять первые две свои цифры b1 и b2 взяты из множества A. Заметим, что Борис вынужден будет на последнем ходе выбрать либо цифру 1 , либо цифру 7 , которые дают одинаковый остаток 1 при делении на 3. Поэтому Андрею достаточно подобрать цифру a3 так, чтобы сумма цифр a1+b1+a2+b2+a3 давала бы остаток 2 при делении на 3. Поскольку a1=3 и a2=9 не влияют на остаток этой суммы, все зависит от остатка суммы b1+b2. Покажем, как действовать Андрею в каждом из случаев.
Если b1+b2 делится на 3, то Андрей выберет цифру a3 из набора (2,5,8): поскольку до этого момента эти цифры мог выбирать только Борис, как минимум одна из этих трех цифр останется не выбранной.
Если b1+b2 дает остаток 1 при делении на 3, Андрей выберет цифру a3=1. Как мы помним, Борис не мог ее выбрать на первых двух ходах.
Наконец, если b1+b2 дает остаток 2 при делении на 3, Андрей выберет цифру a3 из набора (0, 6). Борис не мог выбрать обе эти цифры, поскольку тогда b1+b2=6, а мы предположили, что b1+b2 дает остаток 2 при делении на 3 .
Таким образом, Андрей выиграет.
Ответ: Андрей.
Двое по очереди ставят крестики и нолики в клетки доски 9×9. Начинающий ставит крестики, его соперник — нолики. В конце подсчитывается, сколько имеется строчек и столбцов, в которых крестиков больше, чем ноликов — это очки, набранные первым игроком. Количество строчек и столбцов, где ноликов больше — очки второго. Тот из игроков, кто наберет больше очков, побеждает. Кто может победить, как бы ни играл соперник?
Решение:
Приведем выигрышную стратегию за первого игрока. Первым ходом он ставит крестик в центральную клетку. Затем после каждого хода второго игрока первый ставит крестик в центрально-симметричную клетку (аналогичный ход, симметричный ходу второго относительно центральной клетки). У первого всегда есть такой ход (центрально-симметричная клетка свободна после хода второго), так как всегда после хода первого доска симметрична сама себе относительно центральной клетки.
В конце получим также доску, симметричную самой себе относительно центральной клетки. То есть число столбцов, где крестиков больше, на 1 (центральный столбец) больше, чем столбцов, где ноликов больше. Аналогично строк, где больше крестиков, на 1 больше. Значит, первый победил.
Ответ: Первый.
На столе лежат 9 карточек с номерами от 1 до 9, каждый номер встречается по разу. Двое по очереди забирают себе по карточке со стола. Если в какой-то момент один из игроков собрал 3 карточки с суммой 15, то он победил. Иначе объявляется ничья. Есть ли у какого-нибудь из игроков выигрышная стратегия?
Решение:
Разместим все карточки в квадрате 3×3 как показано на рисунке (составляем так называемый магический квадрат). Заметим, что игрок выиграл тогда и только тогда, когда он первый забирает себе целый столбец, целую строку либо целую диагональ (сумма чисел на вертикалях, горизонталях и диагоналях магического квадрата постоянна, в нашем случае — 15). Будем отмечать карточки, которые забирает 1-ый игрок крестиками, а карточки второго — ноликами. Наша игра свелась в игру в крестики-нолики. Но, как известно, при правильной игре в крестики-нолики, ни у кого нет выигрышной стратегии.
Ответ: Ни у кого.
Два игрока по очереди выкладывают монеты в ряд. За один ход можно положить две или три монеты. Выигрывает тот, кто выложит 16 монету. Определите, какой игрок (первый или второй) обладает стратегией, которая позволит ему выиграть вне зависимости от ходов другого игрока. Опишите эту стратегию.
Решение:
Пусть первый игрок своим первым ходом положит 2 монеты, а следующими ходами класть столько монет, чтобы сумма его монет и монет, положенных перед этим вторым игроком была равна 5. В этом случае после третьего хода первого игрока в ряду будут лежать 12 монет. Далее, как бы не сходил второй игрок своим третьим ходом и как бы после этого не сходил первый игрок 16 монета будет положена первым игроком.
Ответ: Первый игрок.
По кругу расположены 16 луночек, одна из которых отмечена. Андрей и Борис играют в следующую игру. В начале игры Борис кладет шарик в одну из луночек. Далее за каждый ход Андрей называет натуральные число k (числа k могут отличаться на разных ходах), а Борис перемещает шарик из луночки, в которой он находится, на k луночек по часовой либо против часовой стрелки на свой выбор. Сможет ли Андрей играть так, чтобы через несколько ходов шарик гарантированно попал в отмеченную луночку?
Решение:
Приведём стратегию. Занумеруем луночки по часовой стрелке числами от 0 до n-1 так, что номер 0 имеет отмеченная луночка. Если шарик находится в луночке номер s он называет число s. Если Борис сдвинет шарик против часовой стрелки, то он немедленно попадет в отмеченную луночку. Значит, он вынужден сдвинуть шарик по часовой стрелке, то есть в луночку номер t, где t=2s (mod 16). Так как t-2s делится на 16, то t - четно. Таким образом, после первого шага шарик обязательно находится в луночке с четным номером. Аналогично, на следующем шаге номер луночки будет обязательно делиться на 4 и так далее. Поэтому не позже чем на 4-м шаге номер луночки будет делиться на 16, а такая луночка только одна — отмеченная.
Ответ: Да, сможет.
На столе есть две кучки камней, в которых соответственно 100 и 101 камень. Двое играют в игру, делая ходы по очереди. За ход разрешается взять кучку, убрать из неё какое-то количество камней (хотя бы один) и разбить оставшиеся в этой кучке камни на две непустые кучки. Проигрывает тот, кто не может сделать ход. Кто выиграет при правильной игре: тот, кто делает первый ход, или его соперник?
Решение:
Пусть первого игрока зовут Андреем, а второго — Борисом. Первым ходом Андрей уберет из кучки 101 один камень, а оставшиеся разделит на кучки из 1 (про которую можно забыть) и 99 камней. Теперь докажем более общий факт: если на столе лежат кучки из 2k и 2k-1 камней, то проигрывает тот, чья очередь ходить.
Пусть соперник Андрея Борис сделал ответный ход в кучку 2k-1 или разделил кучку 2k на две, взяв из нее больше одного камня. У него получились кучки из a и b камней, где a+b<2k-2. Тогда Андрей следующим ходом создает две такие же кучки, получает позицию a, a, b, b и выигрывает, делая ходы, симметричные ходам первого.
Пусть Борис возьмет один камень из кучки 2k и разделит ее на кучки из a и b камней. Тогда числа a и b будут разной четности. Пусть a четно. Тогда Андрей из кучки в 2k-1 камней получит кучки из a-1 и b камней (что возможно, так как a>2 после чего мысленно разделяет игру на две: одну на паре равных кучек b,b где он побеждает, делая ходы, симметричные ходам первого, и вторую — на паре кучек a, a-1 где он снова применяет стратегию, описанную выше.
Таким образом, у второго всегда есть возможность сделать ход, и он побеждает в силу того, что всего в игре можно сделать не больше 200 ходов.
Ответ: Тот, кто делает первый ход.
Андрей и Борис играют в игру. У них есть карточки с цифрами от 1 до 8. Они по очереди берут по одной карточке, создавая себе по четырёхзначному числу: вначале они берут разряды тысяч, потом сотен, потом десятков, потом единиц (именно в таком порядке). Начинает Андрей. Если сумма получившихся чисел не делится на 6, то побеждает Андрей, а если делится — то Борис. Кто выигрывает при правильной игре?
Решение:
Если Андрей берет нечетную цифру, то мы берем нечетную, если Андрей берет четную цифру, то мы берем четную. Тогда заметим, что последние взятые цифры будут одной четности, откуда сумма двух чисел будет делиться на 2. Также она будет делиться на 3, так сумма цифр двух чисел равна 36 — делится на 3 (сумма цифр числа дает тот же остаток при делении на 3, что и само число). Поэтому сумма поделится на 6. А значит Борис выиграет.
Ответ: Борис.