Jak sama nazwa może sugerować, problem ten jest pół-zainspirowany uprzejmy pobliżu widzących Pijany Bot przez @NP

Nasz biedny bot jest umieszczany na kartezjańskiej siatce u źródła, a po każdej minucie przesuwa 1 jednostkę w jednym z czterech kierunków (w górę, w dół, w lewo, w prawo).

Po n minutach wszystkie utajone miny na siatce aktywują się, zabijając każdego biednego bota, który mógłby się nad nimi znaleźć. Kopalnie znajdują się przy wszystkich współrzędnych całkowitych spełniających równanie | y | = | x |.

Wyzwanie

Otrzymasz n , liczbę minut przed wybuchem min, jako dane wejściowe, a jako dane wyjściowe musisz znaleźć prawdopodobieństwo, że bot nie żyje .

Dane wejściowe : liczba naturalna reprezentująca n .

Wyjście : Niech prawdopodobieństwo, że bot nie żyje, wynosi p / q, gdzie p i q są względnie pierwszymi liczbami całkowitymi (q nie może być 0, ale p może). Wyjście p.

Zasady

• Twój algorytm nie może działać w wykładniczym lub wyższym czasie. Idealnie powinien działać w czasie wielomianowym lub krótszym.
• Twój algorytm musi być w stanie obsłużyć dane wejściowe n<20 (można je zmienić, jeśli są zbyt trudne) w rozsądnym czasie.
• To wyzwanie dla golfa .
• Iteracja wszystkich możliwości dla danego n zdecydowanie nie zostanie zaakceptowana jako odpowiedź.

Przypadki testowe

1->0

2->3

4->39

6->135

8->7735

10->28287

Przykładowe obliczenia dla n = 6

Mamy 4 możliwe ruchy: U, D, R i L. Całkowita liczba ścieżek, które można wybrać, to 4 ^ 6 lub 4096. Istnieją 4 możliwe przypadki, które lądują wzdłuż linii y = x: x, y = ± 1; x, y = ± 2; x, y = ± 3; lub x = y = 0. Policzymy liczbę sposobów, aby skończyć na (1,1), (2,2) i (3,3), pomnóż je przez 4, aby uwzględnić pozostałe kwadranty i dodaj to liczba sposobów, aby skończyć na (0,0).

Przypadek 1: Bot kończy się na (3, 3). Aby bot się tu znalazł, musiał mieć 3 ruchy w prawo i 3 ruchy w górę. Innymi słowy, łączna liczba sposobów na dotarcie tutaj to sposoby zmiany kolejności liter w sekwencji RRRUUU, czyli 6 wybierz 3 = 20.

Przypadek 2: Bot kończy się na (2,2). Aby bot mógł się tutaj znaleźć, mógł mieć 2 ruchy w górę, 3 ruchy w prawo i 1 ruch w lewo; lub 2 ruchy w prawo, 3 ruchy w górę i 1 ruch w dół. Tak więc łączna liczba sposobów na dotarcie tutaj to suma sposobów zmiany kolejności liter w sekwencjach RRRLUU i UUUDRR, z których oba to (6 wybierz 1) * (5 wybierz 2) = 60, w sumie 120 możliwości .

Przypadek 3: Bot kończy się na (1,1). Aby bot mógł się tutaj znaleźć, mógł mieć: 1 ruch w prawo, 3 ruchy w górę i 2 ruchy w dół. W takim przypadku liczba sposobów zmiany kolejności liter w sekwencji RUUUDD wynosi (6 wybierz 1) * (5 wybierz 2) = 60.

1 ruch w górę, 3 ruchy w prawo i 2 ruchy w lewo. W takim przypadku liczba sposobów zmiany kolejności liter w sekwencji URRRLL wynosi (6 wybierz 1) * (5 wybierz 2) = 60.

2 ruchy w prawo, 1 ruch w lewo, 2 ruchy w górę i 1 ruch w dół. W takim przypadku liczba sposobów zmiany kolejności liter w sekwencji UUDRRL wynosi (6 wybierz 1) * (5 wybierz 1) * (4 wybierz 2) = 180.

Zatem łączna liczba sposobów, aby skończyć na (1,1) wynosi 300.

Przypadek 4: Bot kończy się na (0,0). Aby bot się tutaj znalazł, mógł mieć:

3 ruchy w prawo i 3 ruchy w lewo. W takim przypadku liczba sposobów zmiany kolejności liter w sekwencji RRRLLL wynosi (6 wybierz 3) = 20.

3 ruchy w górę i 3 ruchy w dół. W takim przypadku liczba sposobów zmiany kolejności liter w sekwencji UUUDDD wynosi (6 wybierz 3) = 20.

1 ruch w prawo, 1 ruch w lewo, 2 ruchy w górę i 2 ruchy w dół. W takim przypadku liczba sposobów zmiany kolejności liter w sekwencji RLUUDD wynosi (6 wybierz 1) * (5 wybierz 1) * (4 wybierz 2) = 180.

1 ruch w górę, 1 ruch w dół, 2 ruchy w prawo i 2 ruchy w lewo. W takim przypadku liczba sposobów zmiany kolejności liter w sekwencji RRLLUD wynosi (6 wybierz 1) * (5 wybierz 1) * (4 wybierz 2) = 180.

Zatem łączna liczba sposobów, aby skończyć na (0,0) wynosi 400.

Łącząc te przypadki razem, otrzymujemy całkowitą liczbę sposobów, aby skończyć na | y | = | x | wynosi 4 (20 + 120 + 300) + 400 = 2160. Zatem nasze prawdopodobieństwo wynosi 2160/4096. Gdy ta frakcja zostanie w pełni zmniejszona, wynosi 135/256, więc nasza odpowiedź to 135 .

Python 2 , 65 bajtów

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

Wypróbuj online!

Prawdopodobieństwo śmierci bota można wyrazić jako:

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

a dwumianowy jest rozumiany jako równy gdy nie jest całe.$0$$n/2$

Możemy tak rozumować. Jakie jest prawdopodobieństwo, że bot wyląduje na linii ? Dzieje się tak, jeśli całkowita liczba ruchów w górę i w lewo jest równa łącznej liczbie ruchów w dół i w prawo. Jest to takie samo prawdopodobieństwo, że powiedzmy, że rzucisz monetą razy i dostaniesz tyle ogonów, ile głów. Musisz wybrać rzutów, aby być głowami rzutów, co można zrobić na sposobów, z możliwych sekwencji ogólnie, co daje prawdopodobieństwo$y=x$$n$$n/2$$n$$\binom{n}{n/2}$$2^n$

Prawdopodobieństwo lądowania linii wynosi również . Prawdopodobieństwo lądowania na którejkolwiek linii jest sumą tych lub , z wyjątkiem podwójnego liczenia prawdopodobieństwa lądowania w obu liniach i musimy je odjąć, aby to zrekompensować.$y=-x$$s$$2s$$x=y=0$

Okazuje się, że prawdopodobieństwo lądowania na to po prostu , iloczyn prawdopodobieństwa lądowania na każdej linii. Możemy argumentować, że zdarzenia są niezależne w następujący sposób: jeśli wybierzemy losową sekwencję równych liczb „w górę lub w lewo” i „w dół lub w prawo”, aby wylądować na i podobnie z „w górę lub w prawo” i „w dół lub w lewo "dla możemy jednoznacznie połączyć je w sekwencję Góra, Dół, Lewo, Prawo, biorąc przecięcie par kierunków w każdej pozycji.$x=y=0$$s^2$$x=y$$x=-y$

Zatem prawdopodobieństwo lądowania na lub wynosi .$x=y$$x=-y$$2s-s^2$

Kod oblicza dwumianowy przy użyciu tego wyrażenia jak w przypadku podstawy . Aby wyodrębnić licznik z ułamka prawdopodobieństwa, zauważamy, że mianownik jest potęgą 2, więc używamy wyrażenia do podzielenia maksymalnej potęgi 2 , wyrażonej jako klasyczna sztuczka bitowa .$\binom{n}{n/2}$(b+1)**n/b**(n/2)%bb=2**nr/(r&-r)rr&-r

Rozgrywka polega na zapisaniu jako dzięki czemu jest przywoływany tylko raz, i działa bez ułamków aby pozostać w liczbach całkowitych. Obliczenia są czasem wielomianowym w nawet przy funkcyjnym sposobie obliczania dwumianów.$2s-s^2$$1-(1-s)^2$$s$$1/2^n$$n$

Po napisaniu dowodu prawdopodobieństwa śmierci bota znalazłem prawdopodobnie czystszy sposób, aby to udowodnić i przedstawić.

Trzymajmy utwór z wartości i po każdym ruchu bot. Każdy z czterech kierunkach, w górę, w dół, w lewo lub w prawo albo zwiększa lub zmniejsza każdy z i , z czterech kierunków odpowiadających czterech kombinacjach.$a=x+y$$b=x-y$$a$$b$

Tak więc losowy ruch jest równoważny losowemu dodaniu do i niezależnie do . Jest to równoważne robi oddzielne losowe spacery na i .a ± 1 b a $\pm 1$$a$$\pm 1$$b$$a$$b$

Teraz robot kończy się na linii lub dokładnie wtedy, gdy lub . Prawdopodobieństwo zakończenia na to i podobnie dla . Ponieważ spacery są niezależne, prawdopodobieństwo, że i wynosi , więc prawdopodobieństwo, że co najmniej jeden wynosi zero, jest uzupełnieniem .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$