Question

Двое проводят время за игрой: по очереди называют не превосходящие 100 простые числа так, чтобы последняя цифра числа, названного одним игроком, была равна первой цифре числа, которое следующим ходом называет второй (кроме самого первого простого числа, названного в игре). Повторять уже названные ранее числа нельзя. Проигрывает тот, кто не может назвать по этим правилам очередное простое число. Докажите, что один из игроков может действовать так, чтобы гарантированно обеспечить себе выигрыш, и найдите наименьшее возможное число простых чисел, которые будут использованы обоими игроками в такой игре.

Answer 1

Оценка:

Докажем, что первый игрок победит при любых действиях второго. Пусть в самом начале игры первый игрок назвал число 2. Если у первого есть для такого случая выигрышная стратегия, он будет играть по ней и победит. Предположим, что у второго есть выигрышная стратегия в таком случае. Тогда вместо этого хода первый игрок назовёт число, которое бы назвал для победы второй игрок (и в дальнейшем будет действовать по стратегии второго игрока). Логично, что в таком случае первый игрок победит, так как не существует простого числа кроме числа 2, которое бы оканчивалось на 2, значит, число 2 в таком случае не будет названо вообще.

Существует хотя бы по одному двузначному простому числу, начинающемуся на каждую из цифр от 1 до 9, цифра десятков которого не равна цифре единиц. Значит, хотя бы один ход второй игрок сделать точно сможет, назвав одно из этих чисел. Тогда потребуется не менее трёх чисел, чтобы первый победил.

Пример:

97 - единственное простое число, начинающееся на цифру 9. В самом начале игры первый называет число 19. Теперь второй обязан назвать число 97, чтобы не проиграть. Тогда первый назовёт 79. Второй обязан назвать какое-то простое число, начинающееся на 9, но 97 уже названо, а повторяться нельзя.

Ответ: 3 числа.

Answer 2

Для решения этой задачи рассмотрим несколько свойств простых чисел.

1. Простые числа, кроме числа 2, всегда являются нечётными. Поэтому все простые числа, кроме 2, заканчиваются на 1, 3, 7 или 9.

2. Нет простых чисел, заканчивающихся на 5, кроме самого числа 5.

3. Если простое число заканчивается на 1, то следующее простое число, заканчивающееся на 1, будет больше предыдущего числа.

Используя эти свойства, мы можем понять, как один из игроков может гарантировать себе выигрыш.

Рассмотрим возможные варианты начального числа, которое будет названо первым игроком:

1. Если первое число равно 2, то второй игрок должен назвать число, заканчивающееся на 2. Такого простого числа нет, поэтому первый игрок побеждает.

2. Если первое число равно 5, то второй игрок должен назвать число, заканчивающееся на 5. Такого простого числа, кроме самого числа 5, нет, поэтому первый игрок побеждает.

3. Если первое число равно 3 или 7, то второй игрок должен назвать число, заканчивающееся на 3 или 7 соответственно. Первый игрок может назвать число, заканчивающееся на 1, и таким образом гарантировать себе победу. После этого второй игрок не сможет найти простое число, которое начинается с 1, так как таких чисел не существует.

Таким образом, первый игрок всегда может гарантировать себе победу, если он начинает игру с числа 3 или 7.

Наименьшее возможное число простых чисел, которые будут использованы обоими игроками в такой игре, это 2, 5 и 11. Первый игрок начинает с числа 3, затем второй игрок называет 11, и после этого первый игрок не может назвать простое число, удовлетворяющее правилам игры.