Посещение простых чисел на линии

Question

Недавно я играл в отличную мобильную игру под названием Dicast: Rules of Chaos, и она вдохновила меня на создание этой головоломки.

Эта головоломка продолжается на бесконечной числовой строке, где каждое целое число представлено в виде ячейки. Вы начинаете с ячейки, отмеченной 0. У вас есть следующие десять карт:

• Один: перемещает вас на 1 ячейку вправо
• Два: перемещает вас на 2 клетки вправо
• Три: перемещает вас на 3 клетки вправо
• Четыре: перемещает вас на 4 клетки вправо
• Пятый: перемещает вас на 5 клеток вправо
• Шесть: перемещает вас на 6 клеток вправо
• Минус: перемещает вас на 1 ячейку влево
• Нечетный: перемещает вас на 1, 3 или 5 клеток вправо. Номер выбирается равномерно случайным образом
• Четный: перемещает вас на 2, 4 или 6 клеток вправо. Номер выбирается равномерно случайным образом
• Случайно: перемещает вас на 1, 2, 3, 4, 5 или 6 клеток вправо. Номер выбирается равномерно случайным образом

Карты приведут вас прямо к конечному пункту назначения, поэтому вы не посетите другие ячейки между ними. Вы можете использовать каждую карту один раз и разыгрывать их в любом порядке. Как вы можете разыграть карты, чтобы гарантировать, что вы попадете на большее количество различных простых чисел? Другими словами, на какое наибольшее количество различных простых чисел вы можете попасть, независимо от того, какие случайные числа выбраны? Удачи!

Answer 1

Я думаю, лучшее, что мы можем получить, это

6 простых чисел

в целом.

Одна возможная стратегия

Начните с попытки сгенерировать как можно больше простых чисел, используя только неслучайные карты. Поскольку все простые числа, кроме 2, нечетные, и мы начинаем с 0 (который является четным), мы можем перешагнуть не более пяти нечетных простых чисел (нечетных, четных, четных, четных, нечетных + нечетных). Но если мы перешагнем через 2, мы сможем наилучшим образом использовать нечетные карты, пройдя следующим образом: нечетное, нечетное (2), нечетное, четное, четное, четное , что действительно возможно:$0 \to 3 \to 2 \to 7 \to 11 \to 13 \to 19$, используя карты $3, -1, 5, 4, 2, 6$с целью. Поскольку у нас есть семь карт (что даст 7 простых чисел, если каждый шаг дает простое число), а сумма 7 карт равна 20 (составные), 6 простых чисел являются оптимальными на данный момент.

После нажатия на 6 простых чисел (где текущее число 17 или 19) у вас есть четыре карты: 1 или 3, нечетные, четные и случайные. Если ваша оставшаяся константа равна 1, случайные карты могут заставить вас получить либо$6k+2$ или $6k+3$ так что результат, а также его $+1$составной; если у вас есть 3, случайные числа могут заставить вас кратно 3. Таким образом, вы не можете гарантировать больше простых чисел на этом этапе, поэтому лучшее, что вы можете получить, - это 6 простых чисел .

Почему другие стратегии не продвинутся дальше

Не строгий аргумент, но возможная причина такова:

Используя семь карточек с числами, мы можем получить не более 6 простых чисел, потому что сумма всех их составная. Если мы вставим любую из случайных карт между ними, очень вероятно, что «дьявол» сможет выбрать число из случайного пула, так что ход будет составным, И общая сумма останется составной (поэтому он добавляет ноль простых чисел, как бы мы ни старались) . Единственные исключения, о которых я могу думать, - это 2 + Нечетный и 1 + Четный, но 1 не является простым числом (теряя простое число), а 2 + Нечетный теряет максимальную полезность, если мы перешагнули через 3 перед Нечетным (точно так же, как 6 -primes решение уже представлено).

Компьютерная проверка

Я мог убедиться, что оптимальный результат действительно

6 простых чисел , используя простую программу Python 3 . В связанной версии используется только 9 карточек (исключая случайную карточку), и для запуска полного кода на моем локальном компьютере потребовалось ~ 20 минут.

Если убрать проверку истории, получится 7 простых чисел . (К сожалению, программа не показывает оптимальные ходы.) Очевидно, оптимальный ход использует как четные, так и нечетные ходы; без них оптимальная оценка - 6.