Boggle Numérico Básico
Em este post , que foram introduzidas para o jogo de Numerical Boggle em um$6 \times 6$ conselho, cujas regras são as seguintes
- Cada célula deve conter um único dígito de $0$ para $9$.
- Começando em uma célula, você coleta dígitos à medida que se move para as células vizinhas (em todas as 8 direções). Conforme os dígitos são coletados, eles são concatenados da esquerda para a direita, para formar um único número. Observe que o dígito inicial também é coletado e você pode revisitar as células.
A tarefa então era construir essa grade (de tamanho $6 \times 6$) de modo que o menor número positivo que não pode ser construído seja o maior possível.
Obviamente, este jogo e a otimização subsequente podem ser generalizados para grades quadradas de qualquer tamanho, $n \times n$.
Além disso, não precisamos nos restringir a basear$10$. Dado qualquer número inteiro positivo$b$, podemos decretar que cada célula deve conter um único dígito de $0$ para $b-1$ e colocam a otimização em relação a esta nova base (com exceção do unário que usa apenas $1$)
Motivados por essa generalização, podemos olhar para o problema em bases menores.
Em particular, se olharmos para o caso$n=2$ e $b=2$, nossa tarefa de otimização pode resultar em algo como o seguinte
Acontece que, para esta grade (ou mesmo qualquer $2 \times 2$ grade com dois $0$se dois $1$s) é possível construir cada número binário de acordo com as regras do Numerical Boggle (experimente você mesmo). Diremos que tal grade tem extensão infinita na base$b$.
Além disso, diremos que uma base $b$ admite uma grade de extensão infinita se houver alguma grade quadrada de tamanho finito ($n \times n$) que tem extensão infinita na base $b$. Isso nos leva ao nosso quebra-cabeça.
Qual é a maior base inteira positiva $b$ que admite uma grade quadrada finita de extensão infinita ou faz tal $b$existir? Forneça provas da sua resposta.
Respostas
Aqui está um limite superior para corresponder ao limite inferior da outra resposta que eu pensei que correspondia ao limite inferior, mas não entendi as regras do Boggle:
Em qualquer $k\times k$ placa, o número de comprimento$n$ caminhos crescem aproximadamente $8^n$. Por exemplo, é limitado por$k^2 \cdot 8^n$: temos $k^2$ lugares para começar e, a partir daí, cada etapa vai em um de $8$instruções. (Nem todas as etapas em todas as direções são sempre possíveis, mas este é um limite superior.)
No entanto, o número de $n$- números de dígitos na base $b$ cresce aproximadamente como $b^n$: isto é $(b-1)b^{n-1}$. Então, para$b \ge 9$, o número de caminhos possíveis de comprimento $n$ eventualmente será menor que o número de $n$-números de dígitos, e haverá alguns números que não podemos encontrar. Quanto maior for o tabuleiro, mais tarde essa catástrofe ocorrerá, mas ela ocorrerá eventualmente.
Ainda há uma lacuna para
$5 \le b \le 8$, onde uma solução pode existir, mas não sabemos disso.
Uma vez que nossa grade é finita, e precisamos ser capazes de representar sequências infinitamente longas, parece haver pouco sentido em adicionar qualquer dígito X à grade em algum quadrado que não esteja conectado a todos os dígitos: se algum dia usássemos tal dígito, então na etapa anterior também precisaria haver outro quadrado com X acessível para as sequências que não podem ser feitas através do X mal conectado. Isso parece causar ramificações infinitas (uma vez que temos que acomodar todas as sequências possíveis, podemos assumir que existe um adversário maligno sempre escolhendo o caminho mais irritante para nós), o que não podemos fazer em um campo de jogo finito.
Não tenho certeza se o que foi dito acima é realmente verdade, mas presumindo que seja, vamos tentar construir algumas placas "bem conectadas" onde cada dígito está conectado a todos os dígitos possíveis, fornecendo assim facilmente a "extensão infinita" necessária.
A base 3 parece simples (pad com dígitos aleatórios se você realmente quiser um quadrado):
0 1 1 0
0 2 2 0
ou com o número mínimo possível de dígitos, que cabem dentro do quadrado mínimo possível:
0 0 1 2 1 2
Base-4 é um pouco menos trivial, mas ainda bastante factível:
0 0 1 2 3 1 1 3 2 1 0 0
Base-5 apresenta uma dificuldade:
o dígito mais à esquerda "bem conectado" na linha superior não pode ter 5 vizinhos apenas nos lados direito e inferior:
0 4 1 2 3
Claro que podemos corrigir isso adicionando outro número, mas ainda temos o problema de
não pode haver um dígito que esteja ao mesmo tempo
1. bem conectado (próximo a todos os dígitos possíveis),
2. na linha superior e
3. o dígito mais à esquerda em sua linha.
Supondo que a conjectura do primeiro capítulo vale alguma coisa (não tenho certeza se vale), o máximo que podemos fazer é
base-4, que cabe dentro de uma placa boggle 4x4 padrão.
Uma ligeira melhora na resposta de Misha Lavrov.
O número de caminhos diferentes de comprimento $nk$ que pode ser rastreado em um $n\times n$ grade é no máximo $n^2(8^n-3^n)^k$. Isso ocorre porque cada grupo de$n$ movimentos consecutivos não podem ir todos para cima, então há no máximo $8^n-3^n$ sequências de direções permitidas para cada grupo.
o $k$a raiz disso é $n^{2/k}(8^n-3^n)<8^n$ para $k$ suficientemente grande (em termos de $n$) Assim, você pode fazer estritamente menos do que$8^{nk}$ diferentes números de comprimento $nk$ por algum valor de $k$, então o caso $b=8$ também não é possível.
Infelizmente, não acho que isso possa ser levado mais longe:
um cálculo do verso do envelope sugere que, para grandes o suficiente $n$ realmente há mais do que $7^k$ diferentes caminhos de comprimento $k$ para cada $k$, já que um passeio aleatório tem $8$ escolhas em tudo, mas $k-O(k/n)$ etapas com alta probabilidade, e $8^{1-O(1/n)}>7$ para grande $n$.
Acho que tenho um argumento mais forte que apóia a resposta de Bass.
1. Se um número finito de ilhas de placas Boggle podem gerar em conjunto todas as sequências, pelo menos uma ilha gera uma proporção diferente de zero de todas as sequências.
2. Se uma ilha pode gerar proporção diferente de zero de todas as sequências, ela pode realmente gerar todas as sequências (e, portanto, tem extensão infinita). Fundamentação da petição: se não puder gerar uma certa sequência finita de comprimento$k$, a proporção de sequências geradas para comprimento $\ell+1$ é (aproximadamente) $1-1/2^k$ vezes isso para comprimento $\ell$. Portanto, a proporção para todos$\ell \in [1, \infty)$converge para zero. Contradição.
3. Se uma placa finita com extensão infinita tem uma célula que não gera todas as sequências começando por ela mesma, essa célula pode ser removida sem prejudicar a extensão infinita. Fundamentação da petição: presuma que a conclusão é falsa. Então, alguma sequência é forçada a passar pela célula em questão e, por suposição, podemos construir uma sequência que não pode ser gerada pelo quadro (que é a sequência para forçar para a célula + a sequência que não pode ser gerada a partir da célula) . Contradição.
4. Todas as placas finitas para $b \ge 5$conter pelo menos uma célula que não pode gerar todas as sequências começando por ela mesma. Isso é trivial, conforme observado na resposta de Bass, já que a célula mais à esquerda sempre tem um grau de saída de 4 ou inferior.
5. Combinando 3 e 4, não existe uma placa finita com extensão infinita para $b \ge 5$.
Supondo que não haja nenhuma lacuna lógica nas afirmações acima, a resposta é
A base máxima que permite uma prancha de extensão infinita é 4 , encontrada por Bass.
Acho que os passos 1 e 2 não são realmente necessários para a conclusão (como
uma coleção finita de ilhas ainda é um tabuleiro finito
), mas decidi mantê-los desde OMI são observações interessantes.
Esboço de uma solução (?) Para b = 5. Estou mostrando a imagem inacabada para solicitar algum feedback.
Ideia geral: rodovia com inversões de marcha:
planta codificada por cores. O azul é o fundo. linhas brancas são auxiliares visuais para separar quatro faixas de direção alternada, cada uma com quatro "faixas". Observe que isso está apenas mostrando o layout geral; a solução final pode exigir mais e mais tiras.
Observe que, dentro de uma única faixa, cada quadrado possui todos os vizinhos necessários na mesma faixa.
Portanto, a única maneira de eliminar isso é enviesar o movimento em uma direção. Que é onde as faixas vizinhas entram em jogo. Podemos virar em U e voltar, se necessário.
Então, isso resolve tudo?
Não tenho 100% de certeza. Existem dois problemas: 1. podemos inverter a marcha em muitos, mas não em todos os lugares. 2. nem sempre podemos escolher a faixa para a qual mudar. Portanto, em princípio, podemos acabar na última faixa e ficar sem estrada.
2. provavelmente não é um problema real porque para forçar isso exigiria mais ou menos sempre forçar movimentos diagonais (movimentos ortogonais quase certamente nos dão muito espaço de manobra) e forçar a mudança de faixa nos momentos apropriados. Como provavelmente não podemos deixar de ter algum controle sobre quando fazer a reversão, esse segundo requisito parece muito difícil de aplicar.
Meu pressentimento é que eu também posso ser abordado (simplesmente não posso me incomodar em criticar todos os casos agora. Se alguém mais quiser fazer isso, vá em frente, meu voto positivo será garantido)
Uma coisa a observar é que realmente existem ataques a essa configuração que só podem ser derrotados por um planejamento futuro. Se um adversário pudesse decidir o próximo dígito sem aviso, ele poderia nos matar:
O exemplo é o ataque 2 de cima com a seguinte estratégia detalhada: alternar entre amarelo-> vermelho-> laranja claro-> roxo-> laranja escuro forçando uma volta em U. rapidamente após a inversão de marcha, force uma mudança de faixa repetindo um dígito, apenas espere por uma cor que não deixa escolha. Recomeçar. É claro que, se soubermos com antecedência quando as mudanças de faixa estão programadas, podemos nos adaptar quando exatamente fazer o retorno e derrotar esse ataque.