Die Mathe-Redaktion - 10.12.2019 19:37 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte / Top 15
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
Listenpunkt? im neuen Schwätz
ListenpunktWerde Mathe-Millionär!
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 735 Gäste und 15 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von viertel
Matroids Matheplanet Forum Index » Rätsel und Knobeleien (Knobelecke) » * Way of Primes
Druckversion
Druckversion
Antworten
Antworten
Autor
Kein bestimmter Bereich * Way of Primes
Primentus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 1064
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2019-11-18 19:00


Hallo liebe Rätselfreunde,

heute möchte ich Euch das Rätsel "Way of Primes" vorstellen. Jeder, der möchte, ist herzlich eingeladen mitzumachen!

Rätselbeschreibung:

Gegeben sei ein Feld der Größe $n\times n$, bei dem $n$ Quadrate nebeneinander und $n$ Quadrate untereinander liegen. In diesem Feld sind vom linken obersten Quadrat aus der Reihe nach Pflastersteine zu legen mit Anzahl der kleinsten Primzahl, dann der zweitkleinsten Primzahl, dann der drittkleinsten Primzahl, usw. - und das solange, bis am Ende das Quadrat ganz in der Mitte des Feldes erreicht ist, was natürlich nur bei ungeraden $n$ möglich ist.

Dabei gelten allerdings folgende Regeln:

1. Die Pflastersteine ein- und der selben Primzahl dürfen immer nur in eine Richtung angelegt werden (nach rechts, oben, links oder unten [R, O, L, U]). Am Anfang sind somit von links oben aus nur 2 Pflastersteine nebeneinander (R) oder untereinander (U) möglich.

2. Es wird solange die Primzahl erhöht, bis man zu einer primen Anzahl Pflastersteine gelangt, die in keine Richtung mehr gelegt werden kann, wobei die Richtung, aus der man zuletzt gekommen ist, generell unzulässig ist (zudem darf das Feld in seinen Außengrenzen nicht überschritten werden). In einem solchen Fall wird die nächstkleinere Primzahl in Bezug auf die zuletzt gelegte prime Anzahl genommen, wobei für die weiteren Schritte die Primzahl dann solange verkleinert wird, bis man wieder bei der kleinsten Primzahl 2 angelangt ist. Ab der Primzahl 2 wird dann wieder nach oben gezählt, solange wie dabei noch die Anzahl Pflastersteine gelegt werden kann, dann wieder primmäßig nach unten gezählt, usw.

3. Die Pflastersteinlegung führt man solange fort, bis man erstmals eine prime Pflastersteinlegung vornimmt, die exakt in dem Quadrat ganz in der Mitte des Feldes endet.

4. Es ist nicht so, dass die einzelnen Quadrate des Feldes nur einmal betreten werden dürfen, sondern auf den einzelnen Quadraten dürfen beliebig oft Pflastersteine ausgelegt werden, falls man später nochmal an dem Quadrat vorbeikommt.

Beispiel für $n=11$:

2 2 0 0 0 0 0 0 0 0 0
0 3 0 0 0 0 0 0 0 0 0
0 3 0 0 0 0 0 0 0 0 0
0 3 0 0 0 3 3 3 5 0 0
0 5 0 0 0 2 0 0 5 0 0
0 5 0 0 0 2 0 0 5 0 0
0 5 0 0 0 0 0 0 5 0 0
0 5 0 0 0 0 0 0 5 0 0
0 5 7 7 7 7 7 7 7 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0


Das Feld hat die Quadrate (1,1) bis (11,11), dargestellt durch Nullen. Es wird stets links oben im Quadrat (1,1) begonnen. Am Anfang wird die kleinste Primzahl (2) gewählt und eine solche Anzahl Pflastersteine gelegt (alle Pflastersteine in eine Richtung). Da anfangs nur nach rechts oder nach unten geht, wählt man beispielsweise rechts (siehe Beispielfeld).

Anschließend wählt man die nächstgrößere Primzahl (3) und wie ersichtlich wurden diesmal 3 Pflastersteine nach unten gelegt (siehe 3mal die 3). Hierbei ist nochmals wichtig, dass beim nach unten gehen der erste Pflasterstein nicht neben die 2 gelegt und erst dann nach unten gegangen werden darf, weil man dann von der letzten Position aus nach rechts gegangen wäre, was unzulässig ist. Alle Pflastersteine zu ein- und derselben Primzahl müssen in dieselbe Richtung angelegt werden (hier unten).

Als nächstes ist die nächstgrößere Primzahl an der Reihe (5), wozu eine solche Anzahl Pflastersteine beispielsweise ebenfalls nach unten angelegt wird.

Dann ist die Primzahl 7 an der Reihe. Hierbei stellt man fest, dass man vom Feld (9,2) aus lediglich nach rechts gehen kann, da sowohl nach links als auch nach unten nicht möglich ist, und nach oben ist unzulässig, da dies die Richtung ist, aus der man gekommen ist. Somit landet man nach Auslegen der 7 Pflastersteine im Feld (9,9).

Als nächstes wäre die Primzahl 11 an der Reihe, die jedoch in keine der vier Richtungen gelegt werden kann ohne die Außengrenzen des Feldes zu überschreiten (wobei die Richtung, aus der man zuletzt gekommen ist [hier links] wieder generell unzulässig ist). Also geht es jetzt mit der nächstkleineren Primzahl weiter in Bezug zur zuletzt gelegten primen Anzahl, also 5. Hier werden schließlich 5 Pflastersteine nach oben gelegt, bis man im Feld (4,9) landet.

In den nächsten Schritten wird die Primzahl solange verkleinert, bis man bei der kleinsten Primzahl (2) angelangt ist, von der aus dann wieder so weit nach oben gezählt wird, wie noch Pflastersteine in eine Richtung gelegt werden können (bevor dann wieder primmäßig nach unten gezählt würde). Die nächste Primzahl ist also die 3, und im Beispiel wurden 3 Pflastersteine nach links gelegt.

Dann ist die Primzahl 2 an der Reihe, und man legt genauso viele Pflastersteine in die untere Richtung, und siehe da, man ist bereits im Quadrat ganz in der Mitte des Feldes angelangt, so dass das Prozedere an dieser Stelle beendet ist und der nächste Schritt mit Primzahl 3 (wieder hochzählen) gar nicht mehr nötig ist. Der sog. Way of Primes wurde damit gefunden und kann damit wie folgt angegeben werden (Liste von Primzahlen mit Richtungsangaben):

Way of Primes: 2R, 3U, 5U, 7R, 5O, 3L, 2U

Damit ergibt sich folgende Länge des Way of Primes: 7
Mit kürzester Way of Primes ist die kleinstmögliche Länge eines Way of Primes für ein gegebenes $n$ gemeint.

Anmerkungen:
1. Es ist nicht entscheidend, mit welcher Primzahl der Way of Primes endet.
2. Bei den einzelnen primen Pflastersteinlegungen dürfen die Quadrate beliebig oft betreten werden, d. h. es kann im Laufe des Weges sein, dass man auf einem Quadrat mehr als einen Pflasterstein ablegen muss.
3. Es ist nicht erforderlich, auf jedem möglichen Quadrat einen Pflasterstein abgelegt zu haben. Einzig und allein das Erreichen des Feldes ganz in der Mitte nach den gegebenen Regeln ist das maßgebende Ziel.

Aufgabe:

Man ermittle den kürzesten Way of Primes für $n=101$ und gebe ihn in der Form an wie eben im Beispiel gezeigt (d. h. Liste der Primzahlen mit Richtungsangaben).

Bitte beachte, dass keine Lösungseinsendungen hier im Thread gemacht werden sollen, sondern lediglich per Privatnachricht an mich. Vielen Dank!


Ich habe selbst eine Lösung vorzuweisen, von der ich denke, dass es der kürzeste Way of Primes ist.

Wer am schnellsten die richtige Lösung einsendet, d. h. auf die gleiche Länge des Way of Primes kommt wie ich, erhält die (virtuelle) Goldmedaille, der/die zweitschnellste mit der richtigen Lösung die (virtuelle) Silbermedaille und der/die drittschnellste die (virtuelle) Bronzemedaille.

Wer einen richtigen und zulässigen kürzesten Way of Primes einreicht mit einer Länge kleiner als ich es herausgefunden habe, erhält generell die (virtuelle) Platinmedaille. Diese Medaille kann ggf. an mehr als nur einen Rätselgewinner vergeben werden, wohingegen die drei anderen Medaillen nur einmal von mir vergeben werden.

Wird ein Way of Primes mit einer Länge eingereicht, die länger ist als die Länge meines kürzesten Way of Primes, wird hierfür leider keine Platzierung vergeben.

Viel Spaß beim Rätseln!

LG Primentus



  Profil  Quote  Link auf diesen Beitrag Link
Dies ist eine Knobelaufgabe!
Der Themensteller hat bestimmt, dass Du Deine Lösung nicht direkt im Forum posten darfst.
Sende stattdessen Deine Lösung als private Nachricht an den Themensteller. Benutze dazu den Link 'Privat', den Du unter seinem Beitrag findest.
Der Themensteller wird zu gegebener Zeit über eingesandte (richtige) Lösungen informieren
und nach Ablauf einer (von ihm) festgelegten Zeit alle Lösungen veröffentlichen.
viertel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 04.03.2003
Mitteilungen: 26872
Aus: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2019-11-19 02:24


Primentus schreibt:
Hierbei ist nochmals wichtig, dass beim nach unten gehen der erste Pflasterstein nicht neben die 2 gelegt und erst dann nach unten gegangen werden darf, weil man dann von der letzten Position aus nach rechts gegangen wäre, was unzulässig ist.
Diese Einschränkung ergibt sich aber nicht aus den 4 von dir aufgestellten Regeln. Das nochmals kann ich somit nicht nachvollziehen.
Wenn nun aber der erste Stein des nächsten Abschnittes nicht in der gleichen Richtung gelegt werden darf, in die der vorherige Abschnitt gelegt wurde, wie können dann die 5er die 3er-Serie fortsetzen?

Verwirrung beim  ¼


-----------------
Bild



  Profil  Quote  Link auf diesen Beitrag Link
pzktupel
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.09.2017
Mitteilungen: 1045
Aus: Thüringen,Erfurter Raum
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2019-11-19 08:47


>>>Wenn nun aber der erste Stein des nächsten Abschnittes nicht in der gleichen Richtung gelegt werden darf, in die der vorherige Abschnitt gelegt wurde, wie können dann die 5er die 3er-Serie fortsetzen?

Dann wäre das n=11 Bsp nicht korrekt.
Ich vermute, das die Anzahl solange in eine Richtung gelegt werden darf (oder muss), bis die nächste PZ den Rand übertreten würde. Ich finde das Rätsel zu schwer für mich...das muß ich einräumen.
Die Regeln sind etwa klar, aber bis zum Punkt 51,51 ..nene




-----------------
Pech in der Liebe , Glück im Verlieren !!!



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3254
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2019-11-19 10:15


Ich äußere mal vorsichtig Interesse an der Aufgabenstellung, es wird bei mir aber nach dem Grundsatz gehen: Gut Ding will Weile haben.

Danke für die Anregung für die kleinen grauen Zellen, Primentus!


-----------------
~ to fight! (Don Quijote de la Mancha)



  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 1064
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2019-11-19 10:32


Hallo viertel, hallo pzktupel,

die nächste Primzahl (z. B. die 5) darf nur dann in die gleiche Richtung gelegt werden wie die vorige Primzahl (z. B. die 3), wenn, alle Pflastersteine dieser Primzahllegung in diese Richtung gelegt werden (siehe im Beispiel senkrechte 3en und daran anschließende senkrechte 5en).

Es ist nur so gemeint, das wenn eine Richtungsänderung bei einer Primzahl im Vergleich zur vorigen stattfindet, dass dann der erste Stein nicht noch in der Richtung der vorigen Primzahl angelegt werden darf.

Beispiel: "3 rechts, dann 5 unten" muss so gemacht werden:
3 3 3
    5
    5
    5
    5
    5


... und nicht so:

3 3 3 5
      5
      5
      5
      5


Weil dann wäre eine 5 ja nach rechts angelegt worden und die weiteren 5en nach unten. Dies ist aber nicht zulässig, da bei der Primzahllegung einer bestimmten Primzahl diese Pflastersteine in dieselbe Richtung gelegt werden müssen. Ok, das gehört dann sozusagen noch als fünfte Regel mit dazu (ist aber eigentlich das, was ich mit Regel 1 ausdrücken wollte). Sorry, falls ich mich da unklar ausgedrückt habe.

Und bei jeder neuen Pflastersteinlegung für eine bestimmte Primzahl darf sozusagen die Richtung immer frei gewählt werden. Man muss also nicht solange nach unten anlegen, bis es nicht mehr geht oder solange nach rechts anlegen bis es nicht mehr geht. Aber wenn eine Pflastersteinlegung in eine bestimmte Richtung nicht mehr geht, dann muss man eine andere Richtung wählen. Nur falls gar keine Richtung mehr geht, muss primzahlmäßig wieder nach unten gezählt werden.

Und der Rand des Feldes darf sozusagen nie übertreten werden, ja.

Ich hoffe es ist nun klar geworden.

LG Primentus

[Die Antwort wurde nach Beitrag No.2 begonnen.]



  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 1064
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2019-11-19 10:34


Hallo gonz,

das freut mich, das Du auch mitmachen möchtest.
Wünsche Dir und auch allen anderen Rätselteilnehmern viel Freude an der Rätselaufgabe.

LG Primentus



  Profil  Quote  Link auf diesen Beitrag Link
viertel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 04.03.2003
Mitteilungen: 26872
Aus: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2019-11-19 12:26


Ist denn sowas erlaubt:
Erlaubt?
3 3 3
    5 5 5 5 5



  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 5018
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2019-11-19 12:45


2019-11-19 12:26 - viertel in Beitrag No. 6 schreibt:
Ist denn sowas erlaubt:
Erlaubt?
3 3 3
    5 5 5 5 5


Die logische Antwort wäre nein, da die erste 5 ja nach unten, die weiteren 5'en aber nach rechts verlegt wurden, außer ich habe hier gar nichts verstanden.  cool



  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 1064
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, vom Themenstarter, eingetragen 2019-11-19 12:58


2019-11-19 12:26 - viertel in Beitrag No. 6 schreibt:
Ist denn sowas erlaubt:
Erlaubt?
3 3 3
    5 5 5 5 5


Hallo viertel,

nein, ein solches Anlegen ist nicht erlaubt, da ja dann - wie weird schon sagte - eine der 5en nach unten angelegt wurde, aber die anderen 5en nach rechts. Es müssen jedoch alle 5en in dieselbe Richtung angelegt werden in Bezug auf die zuletzt gelegte Vorgängerprimzahl (also hier in Bezug auf die dritte 3).

Diagonales Anlegen ist übrigens nicht erlaubt.

LG Primentus

Edit:
Anderes Beispiel: Seien im Laufe des Weges zuletzt 3en nach oben gelegt worden und anschließend sollen 5en nach rechts angelegt werden, so muss dies wie folgt geschehen:

3 5 5 5 5 5
3
3


... und nicht so:

5 5 5 5 5
3
3
3





  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 5018
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2019-11-19 13:21


@Primentus

Du erklärst im Startposting wortreich, was alles erlaubt ist, stattdessen wäre es sehr viel besser gewesen, von Anfang an einige typische Fälle anzuführen, welche hier nicht erlaubt sind, was du ja mittlerweile auch nachgeholt hast. Da man diesen Fehler sehr, sehr häufig sieht, ist es vielleicht aus didaktischen Gründen ganz lehrreich, darauf nochmals gesondert hinzuweisen.  wink



  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 1064
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, vom Themenstarter, eingetragen 2019-11-19 13:35


Hallo weird,

ok, dann danke ich Dir für die ergänzende Erklärung.
Normalerweise bin ich ja schon immer recht präzise im Erklären (denke ich), aber vielleicht ist es mir dieses Mal nicht so gut gelungen - dafür nochmals sorry. Meine Erklärung im Startposting war ohnehin schon so umfangreich, dass ich es nicht noch weiter aufblähen wollte. Ich dachte, es wäre soweit klar verständlich.

@alle:

Man Betrachte am besten auch nochmal mein Beispielfeld für $n=11$. Dort kann man denke ich sehr gut sehen, wie ich bei einem Richtungswechsel die Primzahlen angelegt habe.

Ansonsten - falls weiterhin etwas unklar ist, gerne einfach fragen!

LG Primentus



  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 1064
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, vom Themenstarter, eingetragen 2019-11-19 14:21


2019-11-19 08:47 - pzktupel in Beitrag No. 2 schreibt:
Ich vermute, das die Anzahl solange in eine Richtung gelegt werden darf (oder muss), bis die nächste PZ den Rand übertreten würde.

Um auch dies nochmal zu verdeutlichen bzw. klarzustellen:
Die Folgeprimzahl (z. B. 5) darf in der gleichen Richtung angelegt werden wie die Vorgängerprimzahl (z. B. 3), sofern alle 5en dieses Legevorganges in diese Richtung gelegt werden.
Es muss aber keinesfalls die Richtung so lange beibehalten werden, bis man aufgrund des Randes des Feldes diese Richtung nicht mehr legen kann. Das heißt also, mit jedem Wechsel der Primzahl kann man eine beliebige gültige Richtung einschlagen.
Nicht gültig sind dabei
1. Richtungen, bei denen man den Rand des Feldes übertreten würde und
2. generell die Richtung aus der man gekommen ist.

Das Ziel ist es praktisch, eine Art "Pflastersteinweg" zu legen, der exakt im Quadrat in der Mitte des Feldes endet. Auf dem Weg dorthin dürfen einzelne Quadrate aber auch mehr als einmal betreten worden sein.

LG Primentus



  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 1064
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, vom Themenstarter, eingetragen 2019-11-19 17:41


Hallo,

die Goldmedaille geht an querin für die am schnellsten eingesandte gültige Lösung mit selber Länge wie mein kürzester Way of Primes.
Es ist zugleich die erste eingereichte Lösung überhaupt.

Hervorragende Leistung!

Herzlichen Glückwunsch und vielen Dank für's Mitmachen!

LG Primentus



  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 1064
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, vom Themenstarter, eingetragen 2019-11-23 20:52


Hallo,

die Silbermedaille geht an gonz für die am zweitschnellsten eingesandte gültige Lösung mit selber Länge wie mein kürzester Way of Primes.

Super Leistung!

Herzlichen Glückwunsch und auch Dir vielen Dank für's Mitmachen!

LG Primentus



  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 1064
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.14, vom Themenstarter, eingetragen 2019-11-29 20:33


Hallo,

falls sich noch jemand die Bronzemedaille schnappen möchte - nur zu. wink

LG Primentus



  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 1064
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.15, vom Themenstarter, eingetragen 2019-12-05 12:02


Hallo,

nachdem keine weiteren Lösungseinsendungen seit meinem letzten Beitrag eingegangen sind, möchte ich verkünden, dass ich das Rätsel am Samstagnachmittag, 07.12.2019 auflösen werde.

Sollte doch noch jemand an diesem Rätsel knobeln und mehr Zeit benötigen, so bitte ich um kurze Info hier im Thread oder per PN.

Vielen Dank!

LG Primentus



  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 1064
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.16, vom Themenstarter, eingetragen 2019-12-07 15:54


Hallo,

nachdem von niemandem mehr um eine Laufzeitverlängerung des Rätsels gebeten wurde, möchte ich nun das Rätsel auflösen.

Lösung des Rätsels "Way of Primes"
Dieses Rätsel lässt sich aufgrund der Größe des Feldes ($n=101$) am besten durch einen Algorithmus lösen, den man dazu anfertigt. Ich selbst habe diesen in Form eines Mathematica-Programmes realisiert. Folgendermaßen sieht der Programmcode dazu aus:
Mathematica
  1. NewPos[a_, b_, p_, r_] :=
  2. Module[{c, d},
  3. If[a == 0 && b == 0,
  4. If[r == 1, Return[{a + 1, b + p}],
  5. If[r == 2, Return[{a, b}],
  6. If[r == 3, Return[{a, b}],
  7. If[r == 4, Return[{a + p, b + 1}]]
  8. ]
  9. ]
  10. ],
  11. If[r == 1, Return[{a, b + p}],
  12. If[r == 2, Return[{a - p, b}],
  13. If[r == 3, Return[{a, b - p}],
  14. If[r == 4, Return[{a + p, b}]]
  15. ]
  16. ]
  17. ]
  18. ]
  19. ]
  20.  
  21. DirAllowed[n_, a_, b_, p_, lr_] :=
  22. Module[{z},
  23. If[a == 0 && b == 0 && p == 2 && lr == 0, Return[{1, 4}]];
  24. z = {};
  25. If[b + p <= n && lr != 3, z = Append[z, 1]];
  26. If[a - p >= 1 && lr != 4, z = Append[z, 2]];
  27. If[b - p >= 1 && lr != 1, z = Append[z, 3]];
  28. If[a + p <= n && lr != 2, z = Append[z, 4]];
  29. Return[z]
  30. ]
  31.  
  32. RandomDir[z_] :=
  33. Module[{rdm},
  34. If[z == {}, Return[0]]; rdm = RandomInteger[{1, 4}];
  35. While[! MemberQ[z, rdm],
  36. rdm = RandomInteger[{1, 4}]
  37. ];
  38. Return[rdm]
  39. ]
  40.  
  41. NewPrimeDir[n_, a_, b_, p_, lr_, pr_, prpos_, pdir_] :=
  42. Module[{},
  43. If[prpos == 1 && pdir == -1, Return[1]];
  44. If[prpos == Length[pr] && pdir == 1, Return[-1]];
  45. If[pdir == 1 && DirAllowed[n, a, b, pr[[prpos + 1]], lr] == {}, Return[-1]];
  46. If[pdir == -1 && DirAllowed[n, a, b, pr[[prpos - 1]], lr] == {}, Return[1]];
  47. Return[pdir]
  48. ]
  49.  
  50. Dir[r_] :=
  51. Module[{},
  52. If[r == 1, Return["R"],
  53. If[r == 2, Return["O"],
  54. If[r == 3, Return["L"],
  55. If[r == 4, Return["U"]]
  56. ]
  57. ]
  58. ]
  59. ]
  60.  
  61. WayOfPrimes[n_] :=
  62. Module[{ab, i, pr, lr, r, w, pdir},
  63. ab = {0, 0}; pr = {}; i = 1;
  64. While[Prime[i] < n,
  65. pr = Append[pr, Prime[i]];
  66. i = i + 1
  67. ];
  68. w = {}; lr = 0; pdir = 1; i = 0;
  69. While[! (ab[[1]] == Ceiling[n/2] && ab[[2]] == Ceiling[n/2]),
  70. i = i + pdir;
  71. r = RandomDir[DirAllowed[n, ab[[1]], ab[[2]], pr[[i]], lr]];
  72. If[r == 0, Return[{}]];
  73. ab = NewPos[ab[[1]], ab[[2]], pr[[i]], r];
  74. w = Append[w, pr[[i]]*Dir[r]];
  75. If[lr != 0, pdir = NewPrimeDir[n, ab[[1]], ab[[2]], pr[[i]], r, pr, i, pdir]];
  76. lr = r
  77. ];
  78. Return[w]
  79. ]
  80.  
  81. ShortestWayOfPrimes[n_] :=
  82. Module[{min, w},
  83. min = Infinity;
  84. While[True,
  85. w = WayOfPrimes[n];
  86. If[Length[w] < min && Length[w] != 0, Print[{w, Length[w]}]; min = Length[w]]
  87. ]
  88. ]
  89.  
  90. ShortestWayOfPrimes[101]
  91.  
  92. (* Ausgabe *)
  93. {{2U, 3R, 5U, 7U, 11R, 13O, 17R, 19U, 23R, 29R, 31U, 37L, 41O, 43L, 47U, 53R, 47O, 43L, 41U, 37R}, 20}
  94.  

Der Algorithmus zerfällt in mehrere Teilfunktionen.

Die erste Funktion NewPos liefert zu einer gegebenen Feldposition (a,b) eine neue Feldposition unter Vorgabe einer bestimmten Primzahl und Richtung (1=R, 2=O, 3=L, 4=U).

Die Funktion DirAllowed ermittelt für eine gegebenene Feldgröße $n$ und Feldposition (a,b) die erlaubten Richtungen, die für eine bestimmte Primzahl gegangen werden dürfen.

Die nächste Funktion RandomDir ermittelt unter Berücksichtigung der überhaupt erlaubten Richtungen eine beliebige Zufallsrichtung.

Die Funktion NewPrimeDir ermittelt für eine gegebene Feldgröße $n$ und Feldposition (a,b) eine neue bestimmte Richtung, die eine bestimmte Primzahl einschlagen soll.

Die Funktion Dir wandelt lediglich die Richtungen 1 bis 4 in verständliche Richtungsbuchstaben um (R, O, L oder U).

Das Herzstück des Algorithmus bildet schließlich die Funktion WayOfPrimes, welche alle zuvorgenannten Funktionen zusammenbringt und zu einer gegebenen Feldgröße einen kompletten Way of Primes ermittelt, der exakt in der Mitte des Feldes endet. Für $n=101$ ist die Position (51,51) der Feldmittelpunkt (51 = Ceiling[n/2]).

Da es nun aber darum geht, den kürzesten Way of Primes zu ermitteln, muss man die WayOfPrimes-Funktion so lange laufen lassen, bis irgendwann kein kürzerer Way of Primes mehr gefunden wird. In der Tat liefert mein Lösungsalgorithmus lediglich zufällige Way of Primes, aber wenn man den Algorithmus entsprechend lange laufen lässt, wird irgendwann ein mutmaßlich kürzester Way of Primes ausgegeben. Die Funktion ShortestWayOfPrimes[n] gibt nacheinander immer kürzer werdende Ways of Primes aus, und man landet irgendwann bei einem kürzesten Way of Primes:

2U, 3R, 5U, 7U, 11R, 13O, 17R, 19U, 23R, 29R, 31U, 37L, 41O, 43L, 47U, 53R 47O, 43L, 41U, 37R

Damit ergibt sich eine Länge des kürzesten Way of Primes von 20. Durch Brute Force kann man um sicherzugehen auch zusätzlich noch alle Möglichkeiten, einen gültigen Way of Primes der Länge 1 bis 19 zu bilden, der im Mittelpunkt des Feldes (51,51) endet, durchprobieren. Dabei ergibt sich, dass es keinen kürzeren Weg als einen Weg mit Länge 20 gibt. Ich selbst wollte es aber letztlich offen lassen, ob es vielleicht doch einen noch kürzeren Weg gibt, um so ggf. tatsächlich eine Platinmedaille zu vergeben. Es zeigte sich aber, dass es offenbar keinen kürzeren Weg gibt.

Hinweis: Andere gültige Lösungen derselben Länge sind möglich.

Hier noch einmal der kürzeste Way of Primes im Detail. Er zeigt die einzelnen Primzahl-Richtungsangaben und die jeweilige Zeile/Spalte, in der man danach landet (beginnend ganz links oben im Feld):

2U $\rightarrow$ (2,1)
3R $\rightarrow$ {2,4)
5U $\rightarrow$ {7,4)
7U $\rightarrow$ {14,4)
11R $\rightarrow$ {14,15)
13O $\rightarrow$ (1,15)
17R $\rightarrow$ (1,32)
19U $\rightarrow$ (20,32)
23R $\rightarrow$ (20,55)
29R $\rightarrow$ (20,84)
31U $\rightarrow$ (51,84)
37L $\rightarrow$ (51,47)
41O $\rightarrow$ (10,47)
43L $\rightarrow$ (10,4)
47U $\rightarrow$ (57,4)
53R $\rightarrow$ (57,57)
47O $\rightarrow$ (10,57)
43L $\rightarrow$ (10,14)
41U $\rightarrow$ (51,14)
37R $\rightarrow$ (51,51)

Interessant ist hierbei, dass bei einem kürzesten Way of Primes der Feldmittelpunkt gegen Ende offenbar systematisch "eingekreist" wird durch schneckenförmige Annäherung (siehe Richtungssequenzen OLUR, OLUR).

Ich hoffe, das Rätsel hat Euch Spaß gemacht.
Die Bronzemedaille konnte leider nicht vergeben werden, aber umso mehr möchte ich dafür nochmals den beiden Gewinnern meine herzlichsten Glückwünsche aussprechen. Nochmals vielen Dank für's Mitmachen!


LG Primentus



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3254
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.17, eingetragen 2019-12-07 16:33


Es hat wie immer Spaß gemacht!

Ich hatte mich zunächst völlig verschätzt was die Größe des Suchraums betrifft und wollte mit Monte Carlo Methoden und Plausibilitäten was man abschneiden kann das Optimum finden - was mir dann auch in vielen vielen Schritten gelungen ist (danke an Primentus für seine Geduld!)

Später ist mir klargeworden, daß der Suchraum gar nicht "so groß" ist und bequem auch komplett abgesucht werden kann, was auch zeigt, daß es keine Platin-Medaillie mehr geben kann...

old plain C
#include "stdio.h"
#define N 101
#define M 51
#define maxstage 20
 
int  primes[26]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101};
char hist_dir[maxstage];
int  hist_prime[maxstage];
int  hist_x[maxstage];
int  hist_y[maxstage];
long gocnt=1;
 
int set_hist(int stage,char dir,int x,int y,int myprime) {
        hist_dir[stage]=dir;
        hist_x  [stage]=x; hist_y  [stage]=y;
        hist_prime[stage]=myprime; }
 
int go(int x,int y,char lastdir,int stage,int nowprimeidx,int upwards) {
 
   int loop;
   if ((x==M)&&(y==M))
      { printf("[%5li] ",gocnt);
        for (loop=0;loop<stage;loop++) printf("%c%i ",hist_dir[loop],hist_prime[loop]);
        printf("(%i) x=%i y=%i\n",stage,x,y); }
 
   if (stage<maxstage) {
        if (upwards>0) nowprimeidx++;
        else { if (nowprimeidx>0) nowprimeidx--;
                else { upwards=1;
                       nowprimeidx=1; } }
 
        int myprime  = primes[nowprimeidx];
        int foundany = 0;
 
        if ((lastdir!='U') && (y>myprime)) {
                foundany=1; set_hist(stage,'O',x,y-myprime,myprime);
                go(hist_x[stage],hist_y[stage],hist_dir[stage],stage+1,nowprimeidx,upwards); }
 
        if ((lastdir!='R') && (x>myprime)) {
                foundany=1; set_hist(stage,'L',x-myprime,y,myprime);
                go(hist_x[stage],hist_y[stage],hist_dir[stage],stage+1,nowprimeidx,upwards); }
 
        if ((lastdir!='O') && (y+myprime<=N)) {
                foundany=1; set_hist(stage,'U',x,y+myprime,myprime);
                go(hist_x[stage],hist_y[stage],hist_dir[stage],stage+1,nowprimeidx,upwards); }
 
        if ((lastdir!='L') && (x+myprime<=N)) {
                foundany=1; set_hist(stage,'R',x+myprime,y,myprime);
                go(hist_x[stage],hist_y[stage],hist_dir[stage],stage+1,nowprimeidx,upwards); }
 
        if (foundany<1) {
                nowprimeidx--;
                go(x,y,lastdir,stage,nowprimeidx,0); }
    } else gocnt++;
   }
 
int main() {
        printf("\nGartenweg 1.01 by gonz\n\n");
        set_hist(0,'U',1,2,2);
        go(hist_x[0],hist_y[0],hist_dir[0],1,0,1);
        printf ("\nGesamtschrittzahl: %li\n\n",gocnt);  }


das quasi in Nullzeit folgende Ausgabe liefert:

ASCII output
Gartenweg 1.01 by gonz
 
[ 8124] U2 U3 R5 R7 R11 R13 U17 L19 U23 R29 O31 L37 U41 U43 R47 O53 L47 U43 R41 O37 (20) x=51 y=51
[ 9850] U2 R3 U5 U7 R11 O13 R17 U19 R23 R29 U31 L37 O41 L43 U47 R53 O47 L43 U41 R37 (20) x=51 y=51
[ 9864] U2 R3 U5 U7 R11 O13 R17 U19 R23 R29 U31 L37 U41 L43 O47 R53 U47 L43 O41 R37 (20) x=51 y=51
[11480] U2 R3 U5 R7 U11 R13 O17 R19 U23 L29 U31 U37 R41 R43 O47 L53 U47 R43 O41 L37 (20) x=51 y=51
[11497] U2 R3 U5 R7 U11 R13 O17 R19 U23 L29 U31 R37 R41 U43 L47 O53 R47 U43 L41 O37 (20) x=51 y=51
 
Gesamtschrittzahl: 17993


Vielen Dank und
ein schönes Adventswochenende!

Gerhard/Gonz



-----------------
~ to fight! (Don Quijote de la Mancha)



  Profil  Quote  Link auf diesen Beitrag Link
Primentus hat die Antworten auf ihre/seine Frage gesehen.
Dies ist eine Knobelaufgabe!
Der Themensteller hat bestimmt, dass Du Deine Lösung nicht direkt im Forum posten darfst.
Sende stattdessen Deine Lösung als private Nachricht an den Themensteller. Benutze dazu den Link 'Privat', den Du unter seinem Beitrag findest.
Der Themensteller wird zu gegebener Zeit über eingesandte (richtige) Lösungen informieren
und nach Ablauf einer (von ihm) festgelegten Zeit alle Lösungen veröffentlichen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2019 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]