Задача 176. Игра в «Числа»-VI
Двое проводят время за игрой: по очереди называют не превосходящие 100 простые числа так, чтобы последняя цифра числа, названного одним игроком, была равна первой цифре числа, которое следующим ходом называет второй (кроме самого первого простого числа, названного в игре). Повторять уже названные ранее числа нельзя. Проигрывает тот, кто не может назвать по этим правилам очередное простое число. Докажите, что один из игроков может действовать так, чтобы гарантированно обеспечить себе выигрыш, и найдите наименьшее возможное количество простых чисел, которые будут использованы обоими игроками в такой игре.
Решение:
Опишем выигрышную стратегию для первого игрока. Сначала первый игрок называет простое число, заканчивающееся на 9 и отличное от 79 (например, 19). Поскольку среди чисел 90, ..., 99 простым является только число 97, следующим ходом второй игрок должен назвать это число. Тогда третьим ходом первый игрок называет 79, и второй проигрывает. За меньшее число ходов первый игрок выиграть не может, так как для любой цифры от 1 до 9 существует простое число из первой сотни, которое начинается с этой цифры.
Ответ:
3
Задача 177. Игра в «Числа»-VII
На доске написаны числа от 1 до 32. Анна и Белла играют в игру, по очереди стирая числа. Первой ходит Белла. Побеждает та девочка, после хода которой произведение оставшихся чисел не будет делиться на 10. Кто из девочек может победить, как бы ни играла ее соперница? Если игра закончилась только тогда, когда чисел не осталось вообще, то побеждает девочка, вычеркнувшая последнее число.
Решение:
Разобьем числа от 1 до 32 на 4 группы: есть три числа, которые делятся на 10; три числа, которые делятся на 5, но не делятся на 10; 13 нечетных чисел, не делящихся на 5 и 13 четных чисел, не делящихся на 5. Будем играть за Анну. Разобьем все числа в группах, кроме одного, на пары. Сами группы также разобьем на пары, 3-3 и 13-13. Если Белла ходит в новую группу, из которой девочки числа еще не стирали, то Анна стирает число из парной группы. Если же Белла ходит в группу, из которой числа уже стирали, то Анна стирает число из той же группы. Заметим, что ни из какой группы Белла не сможет забрать последнее число. Это значит, что если до хода Беллы произведение оставшихся чисел делилось на 10, то и после ее хода оно все еще делится на 10. Поэтому Белла не может победить, значит, побеждает Анна, так как последний ход также делает она.
Ответ:
Анна
Задача 178. Игра в «Заполнение доски»-XI
На шахматную доску размера 8×8 произвольным образом уложены 8 фигурок домино, каждая из которых занимает две соседних по стороне клетки. Разные домино не имеют общих клеток. Докажите. Что на доске всегда найдётся квадрат размера 2 на 2 клетки, ни одна клетка которого не закрыта домино. Верно ли это, если на доске уложены 9 домино?
Решение:
На доске 8×8 квадрат размера 2×2 можно выбрать 49 способами, а каждая фигурка домино имеет хотя бы одну общую клетку максимум с 6 квадратами 2×2. Следовательно, 8 фигурок домино «закрывают» клетки максимум в 48 квадратиках 2×2, поэтому найдется хотя бы один, ни одна клетка которого не закрыта домино.
Пример 9 домино, уложенных так, что в каждом квадрате 2×2 хотя бы одна клетка будет закрыта одним из домино: в шахматной записи домино лежат так –
(b2, b3), (d2, d3), (e4, e5), (e6, e7), (g6, g7), (b5, c5), (b7, c7), (f2, g2), (f4, g4).
Ответ:
Для 9 домино это неверно.
Задача 179. Игра в «Числа»-VIII
На столе лежат карточки, на которых написаны по разу все делители числа 2000 причем на каждой карточке написан один из делителей. Два игрока по очереди берут себе по одной карточке. Проигрывает тот, у кого число на одной из его карточек делится на число на другой из его карточек. Кто выигрывает при правильной игре?
Решение:
Поделим все карточки на пары: d – 2000/d. Все карточки так разобьются, так как 2000 — не квадрат числа. Будем играть за второго и брать каждым ходом парную карточку к карточке первого. Если вдруг у нас оказались два числа x и y такие, что x кратно y, то у нашего соперника уже было два числа 2000/x и 2000/y, причем 2000/y кратно 2000/x, так как 2000/y:2000/x=x/y — целое, так как x кратно y, то есть первый бы уже проиграл. Значит, у нас всегда есть ход, а так как игра конечна, то мы и выиграем.
Ответ:
Второй.
Задача 180. Игра в «Перемещение фишки»
На пятидесятой клетке полосы длиной 100 клеток стоит фишка. Играют двое. Каждый может своим ходом передвинуть фишку на одну или две клетки в ту или иную сторону. Запрещено ставить фишку на те клетки, где она уже побывала. Проигрывает тот, кто не может сделать ход. Кто выиграет при правильной игре — начинающий или его партнер?
Решение:
Первый ход сделаем на одну клетку назад, возможны два варианта, если второй игрок ходит назад, то мы разбиваем первые 48 клеток на пары соседних и будем ходить во вторую клетку пары. Если же второй игрок сходил направо на две клетки, то разбиваем последние 50 клеток на пары соседних и действуем аналогично.
Ответ:
Начинающий
Задача 181. Игра в «Заполнение доски»-XII
На столе стоят в ряд n пустых стаканов. Андрей и Борис по очереди (начиная с Андрея) наливают в них напитки: Андрей — лимонад, Борис — компот. За один ход игрок может заполнить один пустой стакан на свой выбор так, чтобы после его хода не образовалось два соседних стакана с одинаковым напитком. Если в результате действий игроков заполняются все стаканы, то игра заканчивается вничью. В противном случае проигрывает игрок, не имеющий хода. При каких n Борис выиграет вне зависимости от действий Андрея?
Решение.
Занумеруем стаканы слева направо числами от 1 до n. При n=1 и n=2 очевидно, будет ничья. Если n равно 4 или 6, то Андрей первым ходом наливает лимонад в первый стакан. При n=4 Андрей сможет еще заполнить один из двух последних стаканов и, значит, не проиграет. В случае n=6 Андрей вторым ходом заполняет последний стакан (если он пуст), а затем — один из двух средних; если же последний стакан заполнил Борис, то Андрей наливает компот в третий стакан, а затем — в пятый. В любом случае Андрей не проиграет. Рассмотрим теперь n отличное от {1, 2, 4, 6}. Докажем два утверждения.
1) Если Борис своим первым ходом заполняет стакан с номером 1, то далее у него всегда будут ходы. Назовем сегментом набор стаканов, стоящих между двумя последовательными стаканами с лимонадом. По условию каждый сегмент непуст, а любой стакан сегмента либо не заполнен, либо содержит компот. Пусть k≥2. После k-го хода Пети образуется k-1 сегмент. Борис на этот момент заполнил k-1 стакан, в том числе первый, который не входит ни в один сегмент. Тогда найдется такой сегмент, что все входящие в него стаканы пусты. В один из них Борис и может налить компот.
2) Если Борис своим первым ходом заполняет стакан с номером 1, то он не может проиграть. Действительно, в силу 1) Борис всегда будет иметь ход, и, значит, добьется как минимум ничьей. Опишем победную стратегию Борис. Свои м первым ходом Борис всегда наливает компот в крайний стакан (можно считать, что в первый, иначе перенумеруем стаканы в обратном порядке). В силу 2) до статочно показать, что Борис сможет избежать ничьей. Рассмотрим два случая.
a) Когда n нечетно, Борис может играть произвольным образом. Ничья невозможна, поскольку в этом случае последний стакан заполнил бы Андрей, что противоречит 1).
б) Когда n=2m при m≥4, cвоим вторым ходом Борис должен заполнить стакан с четным номером, большим 2. Это возможно, так как имеется не менее трех стаканов с такими номерами и, значит, один из них пуст. Далее Борис может играть произвольным образом. Допустим, что игра завершилась вничью. Тогда m стаканов с лимонадом разместились на позициях 2, 3, ..., 2m. Они должны располагаться на четных местах, поскольку никакие два стакана не стоят рядом. Но это невозможно, так как четных мест всего m и одно из них уже использовал Борис.
Ответ:
при n отличном от {1, 2, 4, 6}.