Задача 224. Игра в «Числа»-XXI
Игорь и Маргарита играют в игру. Перед ними лежат карточки с числами от 1 до 10, всего 10 карточек. Они по очереди берут по одной карточке. Начинает Игорь. Игрок побеждает, если после его хода из нескольких карточек, взятых обоими игроками, знаков арифметических действий (+, -, ×, :) а также любого количества скобок можно составить выражение, значение которого равно 15. Кто из игроков может выиграть независимо от действий соперника?
Подсказка 1
Для начала можно попробовать перебрать разные варианты в зависимости от того, какую карточку возьмёт Игорь. Для большинства из них, скорее всего, Маргарита сможет получить 15 следующим ходом. Но нет ли каких-нибудь особенных карт?
Подсказка 2
Верно, Игорь может взять карту, например, с числом 1(так же могут подойти 2 или 4), и тогда понятно, что Маргарита не сможет выиграть сразу. Теперь нужно понять, что будет происходить на следующих ходах. Карт на самом-то деле у нас не так много. Тогда каким проверенным способом можно воспользоваться для решения задачи?
Подсказка 3
Да, можно просто перебрать для каждой взятой карты Маргариты выигрышную стратегию для Игоря. И тогда победа!
Показать ответ и решение
Пусть Игорь первым ходом возьмёт число 1. Тогда понятно, что Маргарита следующим ходом не выиграет. Докажем, что при любом ходе Маргариты Игорь сможет выиграть. Разберём все случаи:
М: 2 И: 5 = (1+2)*5
М: 3 И: 5 = 3*5
М: 4 И: 5 = (4-1)*5
М: 5 И: 10 = 5+10
М: 6 И: 9 = 6+9
М: 7 И: 8 = 7+8
М: 8 И: 7 = 8+7
М: 9 И: 6 = 9+6
М: 10 И: 5 = 10+5
Ответ:
Победит Игорь.
Задача 225. Игра в «Камешки»-XXII
В куче n камней, играют двое. За ход можно взять из кучи количество камней, либо равное простому делителю текущего числа камней в куче, либо равное 1. Выигрывает взявший последний камень. При каких n начинающий может играть так, чтобы всегда выигрывать, как бы ни играл его соперник?
Решение:
Стратегия: каждый раз оставлять в куче кратное 4 число камней: при n=4k+1 надо взять один камень, при n=4k+2 — два камня; при n=4k+3 надо взять p камней, где p — простой делитель числа n вида 4q+4 (такой есть, иначе все простые делители n имеют вид 4m+1, а произведение чисел такого вида тоже имеет такой вид и не равно 4k+3). Противник из кучи с кратным 4 числом камней не может взять число камней, кратное 4 (это будет не простое число), поэтому начинающий и дальше может играть по стратегии.
Ответ:
При n не кратном 4.
Задача 226. Игра в «Заполнение доски»-XIX
Некто придумал новый корабль для морского боя — “боевой бублик”. Этот корабль состоит из всех клеток квадрата 3×3, кроме его центральной клетки. На поле 8×8 разместили один боевой бублик. Какое минимальное число выстрелов нужно сделать, чтобы гарантированно его ранить?
Решение:
Заметим, что если бублик размещен на поле 4×4, то одного выстрела не хватит, чтобы гарантированно его ранить. Действительно, если выстрел произведен в клетку, соседнюю со стороной квадрата, то бублик может быть размещен рядом с противоположной стороной. Если же выстрел произведен в одну из четырех центральных клеток квадрата, то бублик может быть размещен так, что его центр совпадает с клеткой, в которую сделан выстрел. Значит, потребуется сделать не менее двух выстрелов, чтобы гарантированно его ранить.
Разбив поле 8×8 на четыре квадрата 4×4, получим, что для того, чтобы гарантированно ранить бублик, потребуется не менее 8 выстрелов.
Если же сделать 8 выстрелов так, как показано на рисунке, то мы гарантированно раним бублик.
Ответ:
8.
Задача 227. Игра в «Перемещение фишки»-IV
Два игрока играют в следующую игру на доске m×n клеток). У них есть белый и чёрный король соответственно, стоящие в противоположных углах доски. Они передвигают своих королей (по правилам шахмат) поочередно так, чтобы расстояние между центрами клеток, на которых стоят короли, уменьшалось (королям разрешается занимать соседние клетки). Проигрывает тот, кто не может сделать ход. Кто выигрывает при правильной игре?
Решение:
Рассмотрим разность координат королей: обозначим их через x и y. Заметим, что вначале x=m-1, y=n-1. Мы докажем, что в следующих позициях первый проигрывает, а во всех остальных выигрывает: a) x=0 и y нечетно; б) y=0 и x нечетно; в) x≠0, y≠0, x и y оба четны.
Во-первых, очевидно, что игрок не может из одной проигрышной позиции попасть в другую проигрышную позицию. Также необходимо показать, что из любой выигрышной позиции можно попасть в проигрышную. Нам необходимо рассмотреть два случая (без ограничения общности можно считать, что x, y≥0 ):
1) x, y≥1 — легко видеть, что правила позволяют уменьшать x или y на 1 независимо. Также очевидно, что мы можем или обе координаты сделать четными, или одну сделать нулем, а другую — нечетной;
2) x=0 — мы просто уменьшаем y на 1;
3) y=0 — аналогично предыдущему уменьшаем x на 1.
Итак, если первый игрок находится в выигрышной позиции, он и далее всегда может оставаться в выигрышной позиции. Если же он стоит на проигрышной позиции, второй игрок не даст ему занять выигрышную позицию. Так как расстояние между королями уменьшается, игра закончится, и из последней проигрышной позиции не может быть сделано никакого хода.
Ответ:
Второй игрой выигрывает, если m и n оба нечетны. Во всех остальных случаях выигрывает первый.
Задача 228. Игра в «Заполнение доски»-XX
Андрей и Борис играют в игру на доске 8×8, делая ходы по очереди, начинает Борис. Андрей рисует в клетках крестики, а Борис накрывает прямоугольниками 1×2 (доминошками) пары соседних по стороне клеток доски. За свой ход Андрей должен поставить один крестик в любую пустую клетку (т.е. в клетку, в которой ещё не нарисован крестик и которая ещё не покрыта доминошкой). Борис за свой ход должен накрыть доминошкой две соседних клетки (ещё не накрытые другими доминошками), в которых суммарно чётное число крестиков (0 или 2). Проигрывает тот, кто не может сделать ход. Кто из игроков имеет выигрышную стратегию?
Решение:
Приведём выигрышную стратегию за Андрея. Мысленно раскрасим доску шахматным образом и будем ставить крестики только в чёрные клетки. Борис за один свой ход покрывает ровно одну чёрную клетку. Всего черных клеток на доске 32, поэтому Андрей сможет сделать 16 ходов.
Покажем, что Борис не сможет сделать свой 17-й ход. Пока Андрей действует по стратегии, в белых клетках нет крестиков. Под каждой доминошкой Бориса белая клетка будет без крестика, тогда и черная клетка должна быть без крестика. Значит, Борис не сможет накрыть доминошкой ни один крестик.
Тогда за 16 пар ходов все чёрные клетки будут покрыты доминошками или крестиками, но ни в одной белой клетке не будет крестика. Значит, Борис не сможет поставить доминошку, соблюдая правила игры.
Ответ:
Коля.
Задача 229. Игра в «Перемещение фишки»-V
В каждой клетке доски 2×200 лежит по рублёвой монете. Андрей и Борис играют, делая ходы по очереди, начинает Борис. За один ход можно выбрать любую монету и передвинуть её: Андрей двигает монету на соседнюю по диагонали клетку, Борис — на соседнюю по стороне. Если две монеты оказываются в одной клетке, одна из них тут же снимается с доски и достаётся Борису. Борис может остановить игру в любой момент и забрать все полученные деньги. Какой наибольший выигрыш он может получить, как бы ни играл Андрей?
Решение:
Сначала приведём стратегию за Бориса. Пока она не получила больше 299 монет, перед её ходом на доске остаётся хотя бы 101 монета. Разобьем доску на 100 квадратов 2×2. Получается, что какие-то две монеты лежат в одном и том же квадрате 2×2. Если эти две монеты соседние по стороне, то Борис надвигает одну на другую, и получает ещё одну монету. Если они стоят по диагонали, то Борис сдвигает одну из них в столбец к другой (здесь и далее столбец имеет длину 2, строка — длину 200). Теперь, какой бы ход ни сделал Андрей, эти две монетки всё ещё будут соседними по стороне (либо одна будет снята и уйдёт в доход Бориса), значит, своим следующим ходом Борис сможет получить ещё одну монетку. Таким образом, Борис всегда сможет увеличивать свой выигрыш, пока он меньше 300.
Теперь покажем, как играть за Андрея, чтобы Борис не получил больше 300 монет. Пронумеруем столбцы числами от 1 до 200 по порядку, выберем в каждом нечётном столбце по одной монетке и мысленно покрасим их в красный цвет. Андрею достаточно обеспечить, чтобы красные монетки всегда оставались на доске. Для этого, в свою очередь, достаточно, чтобы две красные монеты никогда не попадали в одну клетку, потому что когда в клетку попадают красная и не красная монеты, можно считать, что с доски снимается не красная.
Назовём расположение монет на доске стабильным, если по одной красной монете лежит в столбцах 1, 3, 5, …, 197 а ещё одна располагается в одном из двух последних столбцов 199, 200. Легко видеть, что после любого хода из стабильной позиции две красные монеты не окажутся в одной клетке. Андрей будет играть так, чтобы после каждого её хода получалась стабильная позиция. Если после хода Бориса позиция осталась стабильной, то Андрей двигает сотую красную фишку между двумя последними столбцами, так же Андрей поступит и своим первым ходом. Если же после хода Бориса позиция перестала быть стабильной, то Борис подвинул одну из красных монет из некоторого столбца х в соседний столбец. Тогда Андрей своим ходом вернёт её в столбец х. Таким образом, на доске всегда останется хотя бы 100 монет, и Борис заработает не более трёхсот рублей.
Ответ:
300.
Задача 230. Игра в «Числа»-XXII
Андрей и Борис по очереди выписывают на доску натуральные числа, не превосходящие 2024 (выписывать уже имеющееся число запрещено); начинает Андрей. Если после хода игрока на доске оказываются три числа, образующих арифметическую прогрессию, этот игрок выигрывает. У кого из игроков есть стратегия, позволяющая ему гарантированно выиграть?
Решение:
Рассмотрим момент после третьего хода (когда выписаны три числа). Если к этому моменту никто еще не выиграл, то следующим ходом Борис выигрывает — ему достаточно найти два выписанных числа одной чётности и выписать своим ходом их среднее арифметическое (оно является целым числом).
Кроме того, заметим, что если три целых числа из множества 1, 2, 3, …, 2024 образуют арифметическую прогрессию, то её разность не больше 1012 (иначе разность между наибольшим и наименьшим числами будет не менее 2×1012=2024 что невозможно).
Теперь опишем выигрышную стратегию Бориса.
Пусть первым ходом Андрей выписал число a. Предположим, что a<1009. Тогда Борис выписывает то из чисел 2023 или 2024, чётность которого отлична от чётности числа a (обозначим это число через b). После этого хода выписано два числа разной чётности; значит, они не могут быть первым и третьим членом прогрессии из целых чисел. А поскольку b-a>1012 они также не могут быть соседними членами прогрессии. Тем самым, Андрей не сможет выиграть третьим ходом. Но в этом случае, как мы видели ранее, следующим ходом Борис выиграет.
Если же a>1013, то Борис отвечает, выписывая то из чисел 1 и 2, которое по чётности отличается от a. Дальнейшие рассуждения аналогичны первому случаю.
Ответ:
У Бориса.
Задача 231. Игра десятерых
Десять мудрецов стоят по кругу и по очереди называют числа: 1 или 2. Мудрец после которого сумма всех названных чисел будет больше или равна 20 проигрывает. Кто из мудрецов может играть так, чтобы точно не проиграть, как бы ни играли другие?
Решение:
Сначала покажем, как десятому мудрецу не проиграть. Если перед первым ходом 10-го мудреца хотя бы один из предыдущих мудрецов назвал 1, то 10-й мудрец называет 2. Тогда, во-первых, после его первого хода сумма не станет больше 20, ведь она равна как максимум 9×2+1=19, во-вторых, перед его вторым ходом сумма уже не меньше 19×1+21=21, поэтому кто-то из предыдущих мудрецов уже проиграл. Если же все до 10-го назвали 2, то 10-й мудрец называет 1 и первый мудрец проигрывает.
Теперь докажем, что любой другой мудрец с номером k может проиграть. Пусть мудрецы с первого по k-1 назовут 1. Заметим, что тогда после хода k-го мудреца сумма S не меньше 1 и не превосходит 1×(k-1)+2=k+1≤10. Тогда 9 мудрецов после k-го могут действовать так, чтобы в сумме назвать число 19-S в пределах от 9 до 18, то есть получить перед вторым ходом k-го мудреца в точности 19. Тем самым, следующим ходом этот математик проиграет.
Ответ:
Только десятый.
Задача 232. Игра в «Заполнение доски»-XXI
На клетчатой доске размером 8×8. Андрей закрашивает несколько клеток. Борис выиграет, если сможет накрыть все эти клетки не пересекающимися и не вылезающими за границу квадрата уголками из трёх клеток. Какое наименьшее количество клеток должен закрасить Андрей, чтобы Борис не выиграл?
Решение:
Так как 64 не делится на 3, то всю доску (64 клетки) нельзя покрыть не пересекающимися и не вылезающими за границу квадрата уголками из трёх клеток.
Покажем, что любые 63 покрашенных клеток можно покрыть такими уголками. Разобьём квадрат 8×8 на 16 квадратов размером 2×2, тогда единственная не покрашенная клетка попала в какой-то один из них.
Любые три полностью покрашенных квадрата можно покрыть уголками из трёх клеток:
А в четвёртом квадрате любые три покрашенные клетки всегда можно покрыть одним уголком.
Ответ:
64.
Задача 233. Ладьи на шахматном поле-IV
Случайная ладья бьет только по горизонтали или только по вертикали, при этом направление выбирается случайно только в момент, когда ладья оказывается на доске. Андрей выставляет на шахматную доску по одной ладье, а Борис тут же определяет ее направление и сообщает его Андрею. Докажите, что Андрей может выставить на доску 15 ладей так, чтобы побить ими все клетки доски, как бы Борис ни пытался ему помешать. Ладья бьет клетку, на которой стоит, через другие фигуры ладья не бьет.
Решение:
Покажем, как ставить 15 ладей так, чтобы они побили всю доску. Всего у доски 8 вертикалей и 8 горизонталей, будем называть их линиями. Говорим, что линия побита, если в ней стоит ладья, которая бьет эту линию. Будем ставить ладьи, начиная с верхнего левого угла доски. Ту линию, которая ладья побила, будем отрезать от доски и больше туда не будем ставить ладьи, и повторять операцию, то есть снова ставить ладью в верхний левый угол. Тем самым за один ход сумма размеров доски уменьшается на 1 и так как на отрезанные части мы ладьи не ставим, то они так и останутся побитыми. Последним же ходом мы уменьшим размеры доски хотя бы на 2 значит, выставим не более 15 ладей.