Visitando numeri primi su una linea

Question

Recentemente ho giocato a un fantastico gioco per cellulare chiamato Dicast: Rules of Chaos e mi ha ispirato a realizzare questo puzzle.

Questo puzzle procede su una linea di numeri infiniti, dove ogni numero intero è rappresentato come una cella. Inizi dalla cella contrassegnata con 0. Hai a disposizione le seguenti dieci carte:

• Uno: ti sposta di 1 cella a destra
• Due: ti sposta di 2 celle a destra
• Tre: ti sposta di 3 celle a destra
• Quattro: ti sposta di 4 celle a destra
• Cinque: ti sposta di 5 celle a destra
• Sei: ti sposta di 6 celle a destra
• Meno: ti sposta di 1 cella a sinistra
• Dispari: ti sposta di 1, 3 o 5 celle a destra. Il numero viene scelto in modo uniforme a caso
• Pari: ti sposta di 2, 4 o 6 celle a destra. Il numero viene scelto in modo uniforme a caso
• Casuale: ti sposta di 1, 2, 3, 4, 5 o 6 celle a destra. Il numero viene scelto in modo uniforme a caso

Le carte ti portano direttamente alla destinazione finale, quindi non visiti altre celle nel mezzo. Puoi usare ogni carta una volta e giocarle in qualsiasi ordine. Come puoi giocare le carte per assicurarti di atterrare sul maggior numero di primi distinti? In altre parole, qual è il maggior numero di numeri primi distinti su cui puoi atterrare, indipendentemente da quali numeri casuali vengono scelti? In bocca al lupo!

Answer 1

Penso che il meglio che possiamo ottenere sia

6 numeri primi

in totale.

Una possibile strategia

Inizia cercando di generare il maggior numero possibile di numeri primi utilizzando solo le carte non casuali. Poiché tutti i numeri primi tranne 2 sono dispari e iniziamo da 0 (che è pari), possiamo solo spostarci al massimo su cinque numeri primi dispari (dispari, pari, pari, pari, dispari + dispari). Ma se superiamo 2, possiamo fare il miglior uso delle carte dispari procedendo in questo modo: dispari, dispari (2), dispari, pari, pari, pari , il che è effettivamente possibile:$0 \to 3 \to 2 \to 7 \to 11 \to 13 \to 19$, utilizzando le carte $3, -1, 5, 4, 2, 6$In ordine. Poiché abbiamo sette carte (che darebbero 7 numeri primi se ogni singolo passo dà un numero primo) e la somma di 7 carte è 20 (composita), 6 numeri primi sono ottimali a questo punto.

Dopo aver calpestato i 6 numeri primi (dove il numero corrente è 17 o 19), hai quattro carte: 1 o 3, Dispari, Pari e Casuale. Se la tua costante rimanente è 1, le carte casuali possono costringerti a ottenere entrambe$6k+2$ o $6k+3$ in modo che il risultato così come il suo $+1$è composto; se ne hai 3, i random possono costringerti a un multiplo di 3. Pertanto, non puoi garantire altri numeri primi a questo punto, quindi il massimo che puoi ottenere è 6 numeri primi .

Perché altre strategie non andranno oltre

Non è un argomento rigoroso, ma una possibile ragione è questa:

Utilizzando le sette carte numeriche, possiamo ottenere al massimo 6 numeri primi perché la somma di tutti è composta. Se inseriamo una qualsiasi delle carte casuali nel mezzo, è molto probabile che il "diavolo" possa scegliere un numero dal pool casuale in modo che il turno sia composto E la somma complessiva rimanga composta (quindi aggiunge zero numeri primi comunque proviamo) . Le uniche eccezioni a cui riesco a pensare sono 2 + Dispari e 1 + Pari, ma 1 non è un numero primo (perdendo un numero primo nel modo in cui) e 2 + Dispari perde la massima utilità se superiamo 3 prima del Dispari (proprio come il 6 -primes soluzione già presentata).

Verifica del computer

Ho potuto verificare che il risultato ottimale è effettivamente

6 numeri primi , usando un ingenuo programma Python 3 . La versione collegata utilizza solo 9 carte (esclusa la scheda Random) e ci sono voluti circa 20 minuti per eseguire il codice completo sulla mia macchina locale.

Se rimuovi il controllo della cronologia, ottieni 7 numeri primi . (Sfortunatamente il programma non mostra le mosse ottimali.) Apparentemente la mossa ottimale utilizza sia Pari che Dispari; senza nessuno dei due il punteggio ottimale è 6.