Primzahlen auf einer Linie besuchen

Question

Vor kurzem habe ich ein großartiges Handyspiel namens Dicast: Rules of Chaos gespielt und es hat mich dazu inspiriert, dieses Puzzle zu machen.

Dieses Rätsel wird auf einer unendlichen Zahlenlinie fortgesetzt, wobei jede Ganzzahl als Zelle dargestellt wird. Sie beginnen mit der mit 0 gekennzeichneten Zelle. Sie haben die folgenden zehn Karten zur Verfügung:

• Erstens: Sie bewegen sich 1 Zelle nach rechts
• Zwei: Verschiebt Sie 2 Zellen nach rechts
• Drei: Verschiebt Sie 3 Zellen nach rechts
• Viertens: Verschiebt Sie 4 Zellen nach rechts
• Fünf: Verschiebt Sie 5 Zellen nach rechts
• Sechs: Verschiebt Sie 6 Zellen nach rechts
• Minus: Verschiebt Sie 1 Zelle nach links
• Ungerade: Verschiebt Sie 1, 3 oder 5 Zellen nach rechts. Die Anzahl wird gleichmäßig zufällig gewählt
• Gerade: Verschiebt Sie 2, 4 oder 6 Zellen nach rechts. Die Anzahl wird gleichmäßig zufällig gewählt
• Zufällig: Verschiebt Sie 1, 2, 3, 4, 5 oder 6 Zellen nach rechts. Die Anzahl wird gleichmäßig zufällig gewählt

Die Karten bringen Sie direkt zum endgültigen Ziel, sodass Sie keine anderen Zellen dazwischen besuchen. Sie können jede Karte einmal verwenden und in beliebiger Reihenfolge spielen. Wie können Sie die Karten spielen, um sicherzustellen, dass Sie auf den meisten unterschiedlichen Primzahlen landen? Mit anderen Worten, auf welcher Anzahl unterschiedlicher Primzahlen können Sie landen, unabhängig davon, welche Zufallszahlen ausgewählt werden? Viel Glück!

Answer 1

Ich denke, das Beste, was wir bekommen können, ist

6 Primzahlen

insgesamt.

Eine mögliche Strategie

Versuchen Sie zunächst, so viele Primzahlen wie möglich nur mit nicht zufälligen Karten zu generieren. Da alle Primzahlen außer 2 ungerade sind und wir bei 0 beginnen (was gerade ist), können wir höchstens fünf ungerade Primzahlen (ungerade, gerade, gerade, gerade, ungerade + ungerade) überschreiten. Wenn wir jedoch über 2 gehen, können wir ungerade Karten am besten nutzen, indem wir diesen Weg gehen: ungerade, ungerade (2), ungerade, gerade, gerade, gerade , was tatsächlich möglich ist:$0 \to 3 \to 2 \to 7 \to 11 \to 13 \to 19$mit Karten $3, -1, 5, 4, 2, 6$in Ordnung. Da wir sieben Karten haben (was 7 Primzahlen ergeben würde, wenn jeder einzelne Schritt eine Primzahl ergibt) und die Summe von 7 Karten 20 (zusammengesetzt) ergibt , sind 6 Primzahlen zu diesem Zeitpunkt optimal.

Nachdem Sie auf die 6 Primzahlen getreten sind (wobei die aktuelle Zahl entweder 17 oder 19 ist), haben Sie vier Karten: eine 1 oder 3, eine ungerade, eine gerade und eine zufällige. Wenn Ihre verbleibende Konstante 1 ist, können die zufälligen Karten Sie zwingen, beide zu erhalten$6k+2$ oder $6k+3$ so dass das Ergebnis sowie seine $+1$ist zusammengesetzt; Wenn Sie 3 haben, können die Zufälle Sie zu einem Vielfachen von 3 zwingen. Daher können Sie zu diesem Zeitpunkt keine weiteren Primzahlen garantieren. Das Beste, was Sie bekommen können, sind 6 Primzahlen .

Warum andere Strategien nicht weiter kommen

Kein strenges Argument, aber ein möglicher Grund ist:

Mit den sieben Zahlenkarten können wir höchstens 6 Primzahlen erhalten, da die Summe aller zusammengesetzt ist. Wenn wir eine der zufälligen Karten dazwischen einfügen, ist es sehr wahrscheinlich, dass der "Teufel" eine Zahl aus dem zufälligen Pool auswählen kann, so dass der Zug zusammengesetzt ist UND die Gesamtsumme zusammengesetzt bleibt (daher werden null Primzahlen hinzugefügt, wie auch immer wir es versuchen). . Die einzigen Ausnahmen, an die ich denken kann, sind 2 + ungerade und 1 + gerade, aber 1 ist keine Primzahl (eine Primzahl im Weg zu verlieren) und 2 + ungerade verliert den maximalen Nutzen, wenn wir vor der ungeraden über 3 gehen (genau wie die 6) -primes Lösung bereits vorgestellt).

Computerüberprüfung

Ich konnte überprüfen, ob das optimale Ergebnis tatsächlich ist

6 Primzahlen mit einem naiven Python 3-Programm . Die verknüpfte Version verwendet nur 9 Karten (mit Ausnahme der Zufallskarte), und es dauerte ca. 20 Minuten, bis der vollständige Code auf meinem lokalen Computer ausgeführt wurde.

Wenn Sie die Verlaufsprüfung entfernen, erhalten Sie 7 Primzahlen . (Leider zeigt das Programm nicht die optimalen Züge an.) Anscheinend verwendet der optimale Zug sowohl ungerade als auch gerade; ohne beide ist die optimale Punktzahl 6.