Visitando primos em uma linha

Question

Recentemente, tenho jogado um ótimo jogo para celular chamado Dicast: Rules of Chaos e ele me inspirou a fazer este quebra-cabeça.

Este quebra-cabeça continua em uma linha numérica infinita, onde cada número inteiro é representado como uma célula. Você começa na célula marcada com 0. Você tem as seguintes dez cartas disponíveis:

• Um: move você 1 célula para a direita
• Dois: move você 2 células para a direita
• Três: move você 3 células para a direita
• Quatro: move você 4 células para a direita
• Cinco: move você 5 células para a direita
• Seis: move você 6 células para a direita
• Menos: move você 1 célula para a esquerda
• Ímpar: move você 1, 3 ou 5 células para a direita. O número é escolhido uniformemente ao acaso
• Uniforme: move você 2, 4 ou 6 células para a direita. O número é escolhido uniformemente ao acaso
• Aleatório: move você 1, 2, 3, 4, 5 ou 6 células para a direita. O número é escolhido uniformemente ao acaso

Os cartões levam você direto para o destino final, para que você não visite nenhuma outra célula entre eles. Você pode usar cada carta uma vez e jogá-las em qualquer ordem. Como você pode jogar as cartas para garantir que chegará ao maior número possível de primos distintos? Em outras palavras, qual é o maior número de primos distintos em que você pode pousar, não importa quais números aleatórios sejam escolhidos? Boa sorte!

Answer 1

Acho que o melhor que podemos conseguir é

6 primos

no total.

Uma estratégia possível

Comece tentando gerar o maior número possível de números primos usando apenas os cartões não aleatórios. Como todos os primos, exceto 2, são ímpares e começamos em 0 (que é par), só podemos ultrapassar no máximo cinco primos ímpares (ímpar, par, par, par, ímpar + ímpar). Mas se passarmos de 2, podemos fazer o melhor uso de cartas ímpares desta forma: ímpar, ímpar (2), ímpar, par, par, par , o que é realmente possível:$0 \to 3 \to 2 \to 7 \to 11 \to 13 \to 19$, usando cartões $3, -1, 5, 4, 2, 6$em ordem. Como temos sete cartas (o que daria 7 primos se cada passo der um primo) e a soma de 7 cartas é 20 (composto), 6 primos é o ideal neste ponto.

Após pisar nos 6 primos (onde o número atual é 17 ou 19), você tem quatro cartas: 1 ou 3, Ímpar, Par e Aleatório. Se sua constante restante for 1, as cartas aleatórias podem forçá-lo a obter qualquer$6k+2$ ou $6k+3$ de modo que o resultado, bem como seu $+1$é composto; se você tiver 3, os randoms podem forçá-lo a um múltiplo de 3. Portanto, você não pode garantir mais nenhum primo neste ponto, então o melhor que você pode obter é 6 primos .

Por que outras estratégias não vão além

Não é um argumento rigoroso, mas uma possível razão é esta:

Usando as sete cartas numéricas, podemos obter no máximo 6 primos porque a soma de todos eles é composta. Se inserirmos qualquer uma das cartas aleatórias no meio, é muito provável que o "diabo" possa escolher um número do conjunto aleatório de modo que a vez seja composta E a soma total permaneça composta (portanto, adiciona zero primos da maneira que tentarmos) . As únicas exceções que consigo pensar são 2 + Ímpares e 1 + Par, mas 1 não é primo (perdendo um primo no caminho) e 2 + Ímpar perde utilidade máxima se ultrapassarmos 3 antes do Ímpar (assim como o 6 -primes solução já apresentada).

Verificação de computador

Pude verificar se o resultado ideal é de fato

6 primos , usando um programa Python 3 ingênuo . A versão vinculada usa apenas 9 cartões (excluindo o cartão Random) e levou cerca de 20 minutos para executar o código completo em minha máquina local.

Se você remover a verificação do histórico, terá 7 primos . (Infelizmente, o programa não mostra os movimentos ideais.) Aparentemente, o movimento ideal faz uso de Ímpar e Par; sem nenhum deles, a pontuação ideal é 6.