Wie der Titel vermuten lässt, ist dieses Problem teilweise vom höflichen, kurzsichtigen, betrunkenen Bot von @NP inspiriert

Unser armer Bot wird am Ursprung auf ein kartesisches Gitter gelegt und bewegt nach jeder Minute 1 Einheit in eine von vier Richtungen (Auf, Ab, Links, Rechts).

Nach n Minuten werden alle latenten Minen auf dem Gitter aktiviert und töten jeden armen Bot, der sich über ihnen befindet. Die Minen befinden sich an allen ganzzahligen Koordinaten, die der Gleichung | y | = | x | entsprechen.

Herausforderung

Sie erhalten n , die Anzahl der Minuten, bevor die Minen explodieren, als Eingabe und als Ausgabe müssen Sie die Wahrscheinlichkeit ermitteln, dass der Bot tot ist .

Eingabe : Eine natürliche Zahl, die n darstellt .

Ausgabe : Die Wahrscheinlichkeit, dass der Bot tot ist, sei p / q, wobei p und q relativ ganze Primzahlen sind (q kann nicht 0 sein, aber p kann). Ausgabe p.

Regeln

• Ihr Algorithmus darf nicht in exponentieller oder höherer Zeit ausgeführt werden. Es sollte idealerweise in Polynomzeit oder weniger laufen.
• Ihr Algorithmus muss in der Lage sein, Eingaben von n<20 (kann angepasst werden, wenn zu hart eingestellt wird) in angemessener Zeit zu verarbeiten.
• Dies ist eine Code-Golf- Herausforderung.
• Das Durchlaufen aller Möglichkeiten für ein gegebenes n wird definitiv nicht als Antwort akzeptiert.

Testfälle

1->0

2->3

4->39

6->135

8->7735

10->28287

Beispielberechnung für n = 6

Wir haben 4 mögliche Züge: U, D, R und L. Die Gesamtzahl der Pfade, die genommen werden könnten, beträgt 4 ^ 6 oder 4096. Es gibt 4 mögliche Fälle, die entlang der Linie y = x: x, y = landen ± 1; x, y = ± 2; x, y = ± 3; oder x = y = 0. Wir werden die Anzahl der Wege zählen, um zu (1,1), (2,2) und (3,3) zu gelangen, sie mit 4 multiplizieren, um die anderen Quadranten zu berücksichtigen, und addieren dies auf die Anzahl der Möglichkeiten, um bei (0,0) zu enden.

Fall 1: Der Bot endet bei (3, 3). Damit der Bot hier landen kann, muss er 3 richtige Züge und 3 Züge nach oben gehabt haben. Mit anderen Worten, die Gesamtzahl der Wege, um hierher zu gelangen, ist der Weg, um die Buchstaben in der Sequenz RRRUUU neu anzuordnen, die 6 ist. Wählen Sie 3 = 20.

Fall 2: Der Bot endet bei (2,2). Damit der Bot hier landen kann, hätte er 2 Aufwärtszüge, 3 Rechtszüge und 1 Linkszug haben können. oder 2 Rechtsbewegungen, 3 Aufwärtsbewegungen und 1 Abwärtsbewegung. Die Gesamtzahl der Wege, um hierher zu gelangen, ist also die Summe der Wege, um die Buchstaben in den Sequenzen RRRLUU und UUUDRR neu anzuordnen, die beide (6 wählen 1) * (5 wählen 2) = 60 sind, was insgesamt 120 Möglichkeiten ergibt .

Fall 3: Der Bot endet bei (1,1). Damit der Bot hier landen kann, hätte er Folgendes haben können: 1 Rechtsbewegung, 3 Aufwärtsbewegung und 2 Abwärtsbewegung. In diesem Fall beträgt die Anzahl der Möglichkeiten zum Neuanordnen der Buchstaben in der Sequenz RUUUDD (6 wählen 1) * (5 wählen 2) = 60.

1 Zug nach oben, 3 nach rechts und 2 nach links. In diesem Fall beträgt die Anzahl der Möglichkeiten zum Neuanordnen der Buchstaben in der Sequenz URRRLL (6 wählen 1) * (5 wählen 2) = 60.

2 Rechtsbewegungen, 1 Linksbewegung, 2 Aufwärtsbewegungen und 1 Abwärtsbewegung. In diesem Fall beträgt die Anzahl der Möglichkeiten zum Neuanordnen der Buchstaben in der Sequenz UUDRRL (6 wählen 1) * (5 wählen 1) * (4 wählen 2) = 180.

Somit beträgt die Gesamtzahl der Wege, um bei (1,1) zu enden, 300.

Fall 4: Der Bot endet bei (0,0). Damit der Bot hier landen konnte, hätte er Folgendes haben können:

3 Rechtsbewegungen und 3 Linksbewegungen. In diesem Fall beträgt die Anzahl der Möglichkeiten zum Neuanordnen der Buchstaben in der Sequenz RRRLLL (6 wählen 3) = 20.

3 Aufwärtsbewegungen und 3 Abwärtsbewegungen. In diesem Fall beträgt die Anzahl der Möglichkeiten zum Neuanordnen der Buchstaben in der Sequenz UUUDDD (6, Auswahl 3) = 20.

1 Rechtsbewegung, 1 Linksbewegung, 2 Aufwärtsbewegungen und 2 Abwärtsbewegungen. In diesem Fall beträgt die Anzahl der Möglichkeiten zum Neuanordnen der Buchstaben in der Sequenz RLUUDD (6 wählen 1) * (5 wählen 1) * (4 wählen 2) = 180.

1 Aufwärtsbewegung, 1 Abwärtsbewegung, 2 Rechtsbewegungen und 2 Linksbewegungen. In diesem Fall beträgt die Anzahl der Möglichkeiten zum Neuanordnen der Buchstaben in der Sequenz RRLLUD (6 wählen 1) * (5 wählen 1) * (4 wählen 2) = 180.

Somit beträgt die Gesamtzahl der Möglichkeiten, bei (0,0) zu landen, 400.

Wenn wir diese Fälle addieren, erhalten wir die Gesamtzahl der Möglichkeiten, auf | y | zu landen = | x | ist 4 (20 + 120 + 300) + 400 = 2160. Somit ist unsere Wahrscheinlichkeit 2160/4096. Wenn dieser Bruchteil vollständig reduziert ist, ist er 135/256, also lautet unsere Antwort 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)

Probieren Sie es online aus!

Die Wahrscheinlichkeit, dass der Bot tot ist, kann ausgedrückt werden als:

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

und das Binomial wird als gleich verstanden, wenn nicht ganz ist.$0$$n/2$

Wir können so argumentieren. Wie groß ist die Wahrscheinlichkeit, dass der Bot auf der Linie landet ? Dies geschieht, wenn die Gesamtzahl der Aufwärts- und Linksbewegungen der Gesamtzahl der Abwärts- und Rechtsbewegungen entspricht. Dies ist die gleiche Wahrscheinlichkeit, dass Sie beispielsweise mal eine Münze und so viele Schwänze wie Köpfe erhalten. Sie müssen Flips als Heads von Flips auswählen , was auf Arten von möglichen Sequenzen insgesamt erfolgen kann, was eine Wahrscheinlichkeit ergibt$y=x$$n$$n/2$$n$$\binom{n}{n/2}$$2^n$

Die Wahrscheinlichkeit, die Linie zu landen , beträgt ebenfalls . Die Wahrscheinlichkeit der Landung auf einer der Linien ist also die Summe dieser oder , außer dass wir die Wahrscheinlichkeit der Landung von in beiden Linien doppelt zählen und sie zum Ausgleich subtrahieren müssen.$y=-x$$s$$2s$$x=y=0$

Es stellt sich heraus, dass die Wahrscheinlichkeit der Landung auf nur , das Produkt der Wahrscheinlichkeit der Landung auf jeder Linie. Wir können argumentieren, dass die Ereignisse wie folgt unabhängig sind: Wenn wir eine zufällige Folge gleicher Anzahl von "Auf oder Links" und "Ab oder Rechts" auswählen, um auf zu landen, und ebenfalls mit "Auf oder Rechts" und "Ab oder Links" "Für können wir sie eindeutig zu einer Folge von Auf, Ab, Links, Rechts kombinieren, indem wir den Schnittpunkt der Richtungspaare an jeder Position nehmen.$x=y=0$$s^2$$x=y$$x=-y$

Die Wahrscheinlichkeit, auf oder landen, beträgt also .$x=y$$x=-y$$2s-s^2$

Der Code berechnet das Binomial Verwendung dieses Ausdrucks wie bei base . Um den Zähler aus dem Wahrscheinlichkeitsbruch zu extrahieren, stellen wir fest, dass der Nenner eine Potenz von 2 ist. Daher verwenden wir den Ausdruck , um die maximale Potenz von 2 zu teilen , ausgedrückt als klassischer Bittrick .$\binom{n}{n/2}$(b+1)**n/b**(n/2)%bb=2**nr/(r&-r)rr&-r

Die Lösung wird gespielt, indem als so dass nur einmal referenziert wird, und ohne die 1/2 Brüche gearbeitet wird, um innerhalb der ganzen Zahlen zu bleiben. Die Berechnung ist Polynomzeit in selbst mit der funky Art der Berechnung von Binomen.$2s-s^2$$1-(1-s)^2$$s$$1/2^n$$n$

Nachdem ich den Beweis für die Wahrscheinlichkeit geschrieben hatte, dass der Bot stirbt, fand ich einen möglicherweise saubereren Weg, ihn zu beweisen und zu präsentieren.

Lassen Sie uns nach jeder Bewegung des Bots die Werte von und verfolgen . Jede der vier Richtungen nach oben, unten, links und rechts erhöht oder verringert jeweils und , wobei die vier Richtungen den vier Kombinationen entsprechen.$a=x+y$$b=x-y$$a$$b$

Eine zufällige Bewegung entspricht also dem zufälligen Hinzufügen von zu und unabhängig zu . Dies ist gleichbedeutend mit getrennten zufälligen Spaziergängen auf und .$\pm 1$$a$$\pm 1$$b$$a$$b$

Jetzt endet der Roboter genau dann auf der Linie oder , wenn oder . Die Wahrscheinlichkeit, mit enden, ist also und ebenfalls für . Da die Spaziergänge unabhängig sind, ist die Wahrscheinlichkeit, dass und sind, , so dass die Wahrscheinlichkeit, dass mindestens eins Null ist, das Komplement .$x=y$$x=-y$$a=0$$b=0$$a=0$$s=\frac{1}{2^n}\binom{n}{n/2}$$b=0$$a\neq 0$$b\neq 0$$(1-s)^2$$1-(1-s)^2$