Como o título pode sugerir, esse problema é semi-inspirado no educado bot bêbado míope de @NP

Nosso pobre bot é colocado em uma grade cartesiana na origem e, a cada minuto, move 1 unidade em uma das quatro direções (Cima, Baixo, Esquerda, Direita).

Após n minutos, todas as minas latentes na grade são ativadas, matando qualquer bot pobre que possa se encontrar sobre elas. As minas estão localizadas em todas as coordenadas inteiras que satisfazem a equação | y | = | x |.

Desafio

Você receberá n , o número de minutos antes da explosão das minas, como entrada e como saída, você deve encontrar a probabilidade de que o bot esteja morto .

Entrada : um número natural que representa n .

Saída : deixe que a probabilidade de o bot estar morto seja p / q, onde p e q são números inteiros relativamente primos (q não pode ser 0, mas p pode). Saída p.

Regras

• Seu algoritmo não deve ser executado em tempo exponencial ou superior. Idealmente, ele deve ser executado em tempo polinomial ou menos.
• Seu algoritmo deve ser capaz de lidar com entradas n<20 (pode ser ajustado se for muito difícil) em um tempo razoável.
• Este é um desafio do código-golfe .
• A iteração de todas as possibilidades para um dado n definitivamente não será aceita como resposta.

Casos de teste

1->0

2->3

4->39

6->135

8->7735

10->28287

Exemplo de cálculo para n = 6

Temos quatro movimentos possíveis: U, D, R e L. O número total de caminhos que podem ser seguidos é 4 ^ 6 ou 4096. Há 4 casos possíveis que chegam ao longo da linha y = x: x, y = ± 1; x, y = ± 2; x, y = ± 3; ou x = y = 0. Contaremos o número de maneiras de terminar em (1,1), (2,2) e (3,3), multiplicá-las por 4 para dar conta dos outros quadrantes e adicionar isso para o número de maneiras de terminar em (0,0).

Caso 1: O bot termina em (3, 3). Para que o bot acabe aqui, ele deve ter tido três movimentos certos e três movimentos para cima. Em outras palavras, o número total de maneiras de chegar aqui são as maneiras de reorganizar as letras na sequência RRRUUU, que é 6, escolha 3 = 20.

Caso 2: O bot termina em (2,2). Para que o bot acabasse aqui, ele poderia ter 2 jogadas para cima, 3 para a direita e 1 para a esquerda; ou 2 movimentos à direita, 3 movimentos para cima e 1 movimento para baixo. Assim, o número total de maneiras de chegar aqui é a soma das maneiras de reorganizar as letras nas seqüências RRRLUU e UUUDRR, ambas as quais são (6 escolha 1) * (5 escolha 2) = 60, para um total de 120 possibilidades .

Caso 3: O bot termina em (1,1). Para que o bot acabasse aqui, ele poderia ter: 1 movimento à direita, 3 movimentos para cima e 2 movimentos para baixo. Nesse caso, o número de maneiras de reorganizar as letras na sequência RUUUDD é (6, escolha 1) * (5, escolha 2) = 60.

1 movimento para cima, 3 movimentos para a direita e 2 movimentos para a esquerda. Nesse caso, o número de maneiras de reorganizar as letras na sequência URRRLL é (6, escolha 1) * (5, escolha 2) = 60.

2 movimentos à direita, 1 movimento à esquerda, 2 movimentos para cima e 1 movimento para baixo. Nesse caso, o número de maneiras de reorganizar as letras na sequência UUDRRL é (6, escolha 1) * (5, escolha 1) * (4, escolha 2) = 180.

Assim, o número total de maneiras de terminar em (1,1) é 300.

Caso 4: O bot termina em (0,0). Para que o bot acabasse aqui, ele poderia ter:

3 movimentos à direita e 3 movimentos à esquerda. Nesse caso, o número de maneiras de reorganizar as letras na sequência RRRLLL é (6, escolha 3) = 20.

3 movimentos para cima e 3 movimentos para baixo. Nesse caso, o número de maneiras de reorganizar as letras na sequência UUUDDD é (6, escolha 3) = 20.

1 movimento para a direita, 1 movimento para a esquerda, 2 movimentos para cima e 2 movimentos para baixo. Nesse caso, o número de maneiras de reorganizar as letras na sequência RLUUDD é (6, escolha 1) * (5, escolha 1) * (4, escolha 2) = 180.

1 movimento para cima, 1 movimento para baixo, 2 movimentos para a direita e 2 movimentos para a esquerda. Nesse caso, o número de maneiras de reorganizar as letras na sequência RRLLUD é (6, escolha 1) * (5, escolha 1) * (4, escolha 2) = 180.

Assim, o número total de maneiras de terminar em (0,0) é 400.

Adicionando esses casos, obtemos o número total de maneiras de terminar em | y | = | x | é 4 (20 + 120 + 300) + 400 = 2160. Assim, nossa probabilidade é 2160/4096. Quando essa fração é totalmente reduzida, é 135/256, então nossa resposta é 135 .

Python 2 , 65 bytes

def p(n):b=2**n;r=b*b-((~b)**n/b**(n/2)%-b)**2;print~n%2*r/(r&-r)

Experimente online!

A probabilidade de o bot estar morto pode ser expressa como:

$$f(n) = 2s-s^2\text{, where } s=\frac{1}{2^n}\binom{n}{n/2}$$

e o binômio é entendido como quando não é inteiro.$0$$n/2$

Podemos raciocinar assim. Qual é a probabilidade de o bot pousar na linha ? Isso acontece se o número total de movimentos para cima e para a esquerda for igual ao número total de movimentos para baixo e para a direita. É a mesma probabilidade de que, digamos, você jogue uma moeda vezes e obtenha o máximo de coroas que as cabeças. Você deve escolher flips para ser o cabeçalho de flips, o que pode ser feito de , de sequências possíveis no geral, fornecendo probabilidade$y=x$$n$$n/2$$n$$\binom{n}{n/2}$$2^n$

A probabilidade de aterrar na linha também é . Portanto, a probabilidade de aterrissagem em qualquer das linhas é a soma destes ou , exceto que estamos contando duas vezes a probabilidade de aterrissagem de nas duas linhas e devemos subtraí-la para compensar.$y=-x$$s$$2s$$x=y=0$

Acontece que a probabilidade de aterrissar em é apenas , o produto da probabilidade de aterrissar em cada linha. Podemos argumentar que os eventos são independentes da seguinte forma: se escolhermos uma sequência aleatória de números iguais de "Cima ou Esquerda" e "Baixo ou Direita" para pousar em e da mesma forma com "Cima ou Direita" e "Baixo ou Esquerda "para , podemos combiná-los exclusivamente em uma sequência de Cima, Baixo, Esquerda, Direita, fazendo a interseção dos pares de direções em cada posição.$x=y=0$$s^2$$x=y$$x=-y$

Portanto, a probabilidade de aterrar em ou é .$x=y$$x=-y$$2s-s^2$

O código calcula o binomial usando esta expressão como na base . Para extrair o numerador da fração de probabilidade, observamos que o denominador é uma potência de 2, portanto usamos a expressão para dividir a potência máxima de 2 , expressa como o truque de bits clássico .$\binom{n}{n/2}$(b+1)**n/b**(n/2)%bb=2**nr/(r&-r)rr&-r

A solução é resolvida escrevendo como para que seja referenciado apenas uma vez e trabalhando sem as frações de para permanecer dentro dos números inteiros. A computação é de tempo polinomial em mesmo com a maneira divertida de calcular binômios.$2s-s^2$$1-(1-s)^2$$s$$1/2^n$$n$

Depois de escrever a prova da probabilidade do bot morrer, encontrei uma maneira possivelmente mais limpa de provar e apresentá-lo.

Vamos faixa de manter os valores de e após cada movimento do bot. Cada uma das quatro direcções, para cima, para baixo, para a esquerda e para a direita, quer aumenta ou diminui cada de e , com as quatro direcções correspondentes aos quatro combinações.$a=x+y$$b=x-y$$a$$b$

Assim, um movimento aleatório é equivalente a adicionar aleatoriamente de e independentemente a . Isso é equivalente a fazer caminhadas aleatórias separadas em e .a ± 1 b a $\pm 1$$a$$\pm 1$$b$$a$$b$

Agora, o robô termina na linha ou exatamente quando ou . Portanto, a probabilidade de terminar com é e da mesma forma para . Uma vez que as esferas são independentes, a probabilidade de que e é , de modo que a probabilidade de que pelo menos um é zero é o complemento de .x = - y a = 0 b = 0 a = 0 s = $x=y$$x=-y$$a=0$$b=0$$a=0$ b=0a≠0b≠0(1-s)21-(1-s)$s=\frac{1}{2^n}\binom{n}{n/2}$$b=0$$a\neq 0$$b\neq 0$$(1-s)^2$$1-(1-s)^2$