Двое проводят время за игрой: по очереди называют не превосходящие 100 простые числа так, чтобы последняя цифра числа, названного одним игроком, была равна первой цифре числа, которое следующим ходом называет второй (кроме самого первого простого числа, названного в игре). Повторять уже названные ранее числа нельзя. Проигрывает тот, кто не может назвать по этим правилам очередное простое число. Докажите, что один из игроков может действовать так, чтобы гарантированно обеспечить себе выигрыш, и найдите наименьшее возможное число простых чисел, которые будут использованы обоими игроками в такой игре.
Answers & Comments
Оценка:
Докажем, что первый игрок победит при любых действиях второго. Пусть в самом начале игры первый игрок назвал число 2. Если у первого есть для такого случая выигрышная стратегия, он будет играть по ней и победит. Предположим, что у второго есть выигрышная стратегия в таком случае. Тогда вместо этого хода первый игрок назовёт число, которое бы назвал для победы второй игрок (и в дальнейшем будет действовать по стратегии второго игрока). Логично, что в таком случае первый игрок победит, так как не существует простого числа кроме числа 2, которое бы оканчивалось на 2, значит, число 2 в таком случае не будет названо вообще.
Существует хотя бы по одному двузначному простому числу, начинающемуся на каждую из цифр от 1 до 9, цифра десятков которого не равна цифре единиц. Значит, хотя бы один ход второй игрок сделать точно сможет, назвав одно из этих чисел. Тогда потребуется не менее трёх чисел, чтобы первый победил.
Пример:
97 - единственное простое число, начинающееся на цифру 9. В самом начале игры первый называет число 19. Теперь второй обязан назвать число 97, чтобы не проиграть. Тогда первый назовёт 79. Второй обязан назвать какое-то простое число, начинающееся на 9, но 97 уже названо, а повторяться нельзя.
Ответ: 3 числа.