Visiter des primes sur une ligne

Question

Récemment, j'ai joué à un grand jeu mobile appelé Dicast: Rules of Chaos et cela m'a inspiré pour créer ce puzzle.

Ce puzzle se déroule sur une droite numérique infinie, où chaque entier est représenté comme une cellule. Vous commencez sur la cellule marquée 0. Vous disposez des dix cartes suivantes:

• Un: vous déplace d'une cellule vers la droite
• Deux: vous déplace de 2 cellules vers la droite
• Trois: vous déplace de 3 cellules vers la droite
• Quatre: vous déplace de 4 cellules vers la droite
• Cinq: vous déplace de 5 cellules vers la droite
• Six: vous déplace de 6 cellules vers la droite
• Moins: vous déplace d'une cellule vers la gauche
• Impair: vous déplace de 1, 3 ou 5 cellules vers la droite. Le nombre est choisi uniformément au hasard
• Pair: vous déplace de 2, 4 ou 6 cellules vers la droite. Le nombre est choisi uniformément au hasard
• Aléatoire: vous déplace de 1, 2, 3, 4, 5 ou 6 cellules vers la droite. Le nombre est choisi uniformément au hasard

Les cartes vous amènent directement à la destination finale, vous ne visitez donc aucune autre cellule entre les deux. Vous pouvez utiliser chaque carte une fois et les jouer dans n'importe quel ordre. Comment pouvez-vous jouer les cartes pour garantir que vous atterrissez sur le plus grand nombre de nombres premiers distincts? En d'autres termes, quel est le plus grand nombre de nombres premiers distincts sur lesquels vous pouvez atterrir, quels que soient les nombres aléatoires choisis? Bonne chance!

Answer 1

Je pense que le mieux que nous puissions obtenir est

6 nombres premiers

au total.

Une stratégie possible

Commencez par essayer de générer autant de nombres premiers que possible en utilisant uniquement les cartes non aléatoires. Puisque tous les nombres premiers sauf 2 sont impairs et que nous commençons à 0 (ce qui est pair), nous ne pouvons dépasser au plus cinq nombres premiers impairs (impair, pair, pair, pair, impair + impair). Mais si nous dépassons 2, nous pouvons tirer le meilleur parti des cartes impaires en procédant de cette façon: impaire, impaire (2), impair, pair, pair, pair , ce qui est en effet possible:$0 \to 3 \to 2 \to 7 \to 11 \to 13 \to 19$, en utilisant des cartes $3, -1, 5, 4, 2, 6$en ordre. Puisque nous avons sept cartes (ce qui donnerait 7 nombres premiers si chaque pas donne un premier) et que la somme de 7 cartes est 20 (composite), 6 nombres premiers sont optimaux à ce stade.

Après avoir marché sur les 6 nombres premiers (où le nombre actuel est 17 ou 19), vous avez quatre cartes: un 1 ou 3, impair, pair et aléatoire. Si votre constante restante est 1, les cartes aléatoires peuvent vous forcer à obtenir soit$6k+2$ ou $6k+3$ de sorte que le résultat ainsi que son $+1$est composite; si vous avez 3, les aléas peuvent vous forcer à un multiple de 3. Par conséquent, vous ne pouvez pas garantir plus de nombres premiers à ce stade, donc le mieux que vous puissiez obtenir est 6 nombres premiers .

Pourquoi les autres stratégies n'iront pas plus loin

Pas un argument rigoureux, mais une raison possible est la suivante:

En utilisant les sept cartes numériques, nous pouvons obtenir au plus 6 nombres premiers car la somme de tous est composite. Si nous insérons l'une des cartes aléatoires entre les deux, il est très probable que le «diable» puisse choisir un nombre dans le pool aléatoire de sorte que le tour soit composé ET que la somme globale reste composite (par conséquent, elle ajoute zéro nombre premier, mais nous essayons) . Les seules exceptions auxquelles je peux penser sont 2 + Odd et 1 + Even, mais 1 n'est pas un premier (perdant un premier sur le chemin) et 2 + Odd perd son utilité maximale si nous en dépassons 3 avant l'Odd (tout comme le 6 -primes solution déjà présentée).

Vérification informatique

J'ai pu vérifier que le résultat optimal est bien

6 nombres premiers , en utilisant un programme Python 3 naïf . La version liée utilise seulement 9 cartes (à l'exclusion de la carte aléatoire), et il a fallu environ 20 minutes pour exécuter le code complet sur ma machine locale.

Si vous supprimez la vérification de l'historique, vous obtenez 7 nombres premiers . (Malheureusement, le programme ne montre pas les mouvements optimaux.) Apparemment, le mouvement optimal utilise à la fois impair et pair; sans l'un ni l'autre, le score optimal est de 6.