| |
| Autor |
 [*] komplette Quadratrasterpfade |
|
cramilu
Aktiv 
Dabei seit: 09.06.2019
Mitteilungen: 2260
Wohnort: Schwäbischer Wald, seit 1989 freiwilliges Exil in Bierfranken
 |  Themenstart: 2023-03-18
|
Auf wieviele unterschiedliche Arten, reduziert um Dreh- und
Spiegelsymmetrie, kann man ein quadratisches Raster \(4×4\)
vollständig durchfahren?
Da nicht den Überblick zu verlieren, ist nicht ohne. 😎
Diesmal gerne direkt hier, auf dass es viel zu sehen gebe!
|
 Profil
| Dies ist eine Knobelaufgabe!
Der Themensteller hat bestimmt, dass Du Lösungen oder Beiträge zur Lösung direkt im Forum posten darfst.
Bei dieser Aufgabe kann ein öffentlicher Austausch über Lösungen, Lösungswege und Ansätze erfolgen. Hier musst Du keine private Nachricht schreiben! |
tactac
Senior 
Dabei seit: 15.10.2014
Mitteilungen: 2800
 | Beitrag No.1, eingetragen 2023-03-18
|
\(\begingroup\)\(\newcommand{\sem}[1]{[\![#1]\!]}
\newcommand{\name}[1]{\ulcorner#1\urcorner}
\newcommand{\upamp}{\mathbin {⅋}}
\newcommand{\monus}{\mathbin {∸}}\)
Anders als beim 3x3-Raster liegt nicht mindestens ein Ende in einer Ecke. Daher reicht es nicht, Pfade zu generieren, die etwa in der linken oberen Ecke anfangen. Aber es sollte reichen, in der linken oberen Ecke zu starten, ihrem rechten Nachbarfeld, und dessen unteren Nachbarfeld.
Hier ein Programm, das theoretisch auch für größere Felder funktioniert (bei nicht-Quadraten ist die Symmetriebehandlung aber Unfug), und das bei den Starts noch etwas großzügiger ist:
\sourceon Haskell
import qualified Data.Set as S
import qualified Data.Map as M
import Control.Monad
main = print $ S.size $ S.fromList $ generate 4 4
type Pos = (Int, Int)
type Path = M.Map Pos Int
generate :: Int -> Int -> [Path]
generate wid hei = do
start <- liftM2 (,) [1..(wid+1)`div`2] [1..(hei+1)`div`2]
go start $ M.singleton start 1
where
siz = wid*hei
go (x,y) m
| M.size m == siz = [normalize m]
| otherwise = do
pos@(x',y') <- [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]
guard $ 1 <= x' && x' <= wid && 1 <= y' && y' <= hei
guard $ pos `M.notMember` m
go pos $ M.insert pos (M.size m + 1) m
normalize :: Path -> Path
normalize p = minimum [transform a b c d p | [a,b,c,d] <- replicateM 4 [False, True]]
transform :: Bool -> Bool -> Bool -> Bool -> Path -> Path
transform negX negY swapXY rev p = M.fromList $ do
((x,y),n) <- M.toList p
let a = if negX then wid+1-x else x
let b = if negY then hei+1-y else y
let (c,d) = if swapXY then (b,a) else (a,b)
let m = if rev then siz+1-n else n
return ((c,d),m)
\sourceoff
Dieses gibt jedenfalls 38 aus (und 549 für 5x5, und 28728 für 6x6).\(\endgroup\)
|
Profil
|
cramilu
Aktiv
Dabei seit: 09.06.2019
Mitteilungen: 2260
Wohnort: Schwäbischer Wald, seit 1989 freiwilliges Exil in Bierfranken
| Beitrag No.2, vom Themenstarter, eingetragen 2023-03-18
|
Chapeau, tactac! 😮
Es ist ein Hamilton-Pfad-Problem: OEIS A265914
Dann lasst uns doch zunächst festlegen, wie wir
die Dinger normiert darstellen wollen, und dann
mit bunten Bildchen loslegen... 🤗
|
Profil
|
gonz
Senior
Dabei seit: 16.02.2013
Mitteilungen: 4745
Wohnort: Harz
 | Beitrag No.3, eingetragen 2023-03-19
|
Guten Morgen zusammen :)
Ja, das ist eine schöne Sache, unter anderem, weil es einfacher zu beschreiben ist als der "Fleissige Sammler", und weil es mit weniger Parametern daherkommt (es braucht keine Zufallsfolge um die Felder zu füllen).
Auch hier könnte man die Frage nach der Existenz oder Anzahl von geschlossenen Rundkursen stellen (für 3x3 gibt es keinen, wie sieht es bei 5x5 aus?) und damit eine zweite Integerfolge erzeugen.
Jedenfalls auch so ein schönes "Spielzeug" ;)
Grüße aus dem Harz - heute kalt und trocken -
Gerhard/Gonz
|
Profil
|
querin
Aktiv
Dabei seit: 12.01.2018
Mitteilungen: 864
 | Beitrag No.4, eingetragen 2023-03-19
|
Hallo 🙂
mit einem etwas umständlichen python Programm kann ich zumindest tactacs Werte 38 für 4x4 und 549 für 5x5 bestätigen.
Als Nebenprodukt erhalte ich mit allen Symmetrien 552 Pfade für 4x4 und 8648 Pfade für 5x5.
Für beide Zählungen gibt es - wenig überraschend - OEIS Einträge:
https://oeis.org/A265914 ohne Symmetrien
https://oeis.org/A096969 mit Symmetrien
Grüße
querin
|
Profil
|
cramilu
Aktiv
Dabei seit: 09.06.2019
Mitteilungen: 2260
Wohnort: Schwäbischer Wald, seit 1989 freiwilliges Exil in Bierfranken
| Beitrag No.5, vom Themenstarter, eingetragen 2023-03-20
|
Denk' ich an Pfade in der Nacht... 🙄
\(7\,+\,31\,=\,38\) ; \(7\cdot8\,+\,31\cdot16\,=\,552\)
@querin, Deine \(8\,648\) für \(5×5\) lassen unter den reduziert
\(549\) Pfaden dort \(17\) achsen- oder punktsymmetrische ahnen:
\(17\,+\,532\,=\,549\) ; \(17\cdot8\,+\,532\cdot16\,=\,8\,648\)
Ob wir wenigstens die grafisch dokumentieren können? 😉
|
Profil
|
hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 2010
 | Beitrag No.6, eingetragen 2023-03-20
|
\quoteon(2023-03-19 17:21 - querin in Beitrag No. 4)
...
Nebenprodukt ...
Für beide Zählungen gibt es - wenig überraschend - OEIS Einträge:
https://oeis.org/A265914 ohne Symmetrien
https://oeis.org/A096969 mit Symmetrien
Grüße
querin
\quoteoff
Hallo querin,
die Formel für die sym. A096969 (die nicht mal dort bei oeis zu finden ist!), habe ich in 1 Zeile packen können:
\sourceon mathematica
Table[Length[FindHamiltonianCycle[AdjacencyGraph[PadRight[AdjacencyMatrix[g=GridGraph[{k,k}]],(VertexCount[g]+1) {1,1},1]],All]]*2,{k,2,6}]
={8, 40, 552, 8648, 458696}
\sourceoff
Da Du beide Folgen "als Nebenprodukt" hast, folgende Frage:
Wie kommt man leicht zu den "ohne Symmetrien" (also zu A265914)?
{aus den gewaltig großen Zahlen-Arrays ein sym. "Muster" zu erkennen und zu eliminieren ist sehr komplex...}
Grüße Gerd
P.S. @cramilu: 4 Uhr ist ja absolute Nachtschicht-Zeit https://matheplanet.com/matheplanet/nuke/html/images/forum/subject/shocked.gif
|
Profil
|
hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 2010
| Beitrag No.7, eingetragen 2023-03-20
|
\quoteon(2023-03-18 22:08 - tactac in Beitrag No. 1)
...
Hier ein Programm, das theoretisch auch für größere Felder funktioniert (bei nicht-Quadraten ist die Symmetriebehandlung aber Unfug), und das bei den Starts noch etwas großzügiger ist:
\sourceon Haskell
import qualified Data.Set as S
import qualified Data.Map as M
import Control.Monad
main = print $ S.size $ S.fromList $ generate 4 4
type Pos = (Int, Int)
...
\sourceoff
...
\quoteoff
Hallo tactac,
ich würde gern Deine feste Konstante 4 als variablen Parameter qsize für die Feldgröße als Kommandozeilenparameter an die EXE übergeben, aber mein Versuch mit:
\sourceon Haskell
...
import System.Console.CmdArgs
do
op <- cmdArgs options
let qsize = read op :: Integer
main = print $ S.size $ S.fromList $ generate qsize qsize
...
\sourceoff
bringt "Could not find module `System.Console.CmdArgs'"
vermutlich, weil ich kein LINUX, sondern Win10 mit
ghc --make -O2 A265914CmdLine.hs ...
habe.
Gibt es da was EINFACHES?
Grüße
|
Profil
|
tactac
Senior
Dabei seit: 15.10.2014
Mitteilungen: 2800
| Beitrag No.8, eingetragen 2023-03-21
|
\quoteon(2023-03-20 19:34 - hyperG in Beitrag No. 7)
bringt "Could not find module `System.Console.CmdArgs'"
vermutlich, weil ich kein LINUX, sondern Win10 mit
ghc --make -O2 A265914CmdLine.hs ...
habe.
Gibt es da was EINFACHES?
Grüße
\quoteoff
Hmm, kommt drauf an, wie du es installiert hast. Möglicherweise kannst du das fehlende Package mit cabal install cmdargs nachinstallieren.
|
Profil
|
cramilu
Aktiv
Dabei seit: 09.06.2019
Mitteilungen: 2260
Wohnort: Schwäbischer Wald, seit 1989 freiwilliges Exil in Bierfranken
| Beitrag No.9, vom Themenstarter, eingetragen 2023-03-21
|
So... zunächst die neuen Grafiken:
Die begriffliche Unterscheidung zwischen kongruent und
symmetrisch ist hier konkretisiert. Außerdem habe ich die
Pfade etwas nachgegrünt.
Ob bzw. wann ich dazu komme, die \(119\) symmetrischen
unter den um kongruente reduzierten \(28\,728\) Hamilton-
Pfaden für das Raster \(6×6\) nachzureichen, bleibt offen...
Zu möglichen Symmetrien findet sich im Rahmen von
OEIS - A265914 schon die Feststellung »For odd n > 1
the only symmetry possible is rotation by 180 degrees.
For even n the only symmetries are reflections either
horizontally or vertically.«. Also für ungerade \(n\geq3\) bloß
[einfach] punktsymmetrische, und für gerade \(n\geq2\) bloß
[einfach] achsensymmetrische.
Vor Betrachtung figürlicher Symmetrie lässt sich jeder zu
einem anderen kongruente Pfad auf \(16\) Arten denken -
jeweils in \(\frac{360°}{90°}=4\) Drehpositionen, an einer orthogonalen
Achse des Rasters gespiegelt und mit Orientierung 'vorwärts'
oder 'rückwärts'. \(4\cdot2\cdot2=16\) . Bei symmetrischen Figuren
von Pfaden halbiert sich das zu \(8\) .
Sei nun jeweils \(h_n\) die Gesamtanzahl an Hamilton-Pfaden
nach OEIS - A096969 (eine exakte Formel in Abhängigkeit
von \(n\) ist bis dato noch nicht gefunden), \(k_n\) die Anzahl an
reduziert kongruenten (OEIS - A265914) und \(s_n\) die Anzahl
an symmetrischen unter letzteren, so muss gelten:
\(8\,\cdot\,s_n\;+\;16\,\cdot\,(k_n-s_n)\;=\;h_n\) \(\Leftrightarrow\) \(s_n\;=\;2\,\cdot\,k_n\;-\;\frac{h_n}{8}\)
\(s_1\) bis \(s_{15}\) lassen sich demnach via OEIS ermitteln:
\([1{,}875]\;1,\;1,\;7,\;17,\;119,\;1\,014,\;10\,027,\;252\,680,\;2\,588\,176,\;...\)
\(...\;270\,980\,912,\;4\,196\,708\,747,\;1\,295\,846\,398\,401,\;20\,398\,831\,422\,630,\;...\)
Untersucht man die Entwicklungen der \(s_n\) für gerade \(n\)
und für ungerade \(n\) getrennt voneinander, so drängt sich
eine grobe Abhängigkeit auf wie folgt:
für gerade \(n\geq2\) \(s_n\;\approx\;\left(\frac{5}{8}\right)^n\;\cdot\;2^{(n^2)}\)
für ungerade \(n\geq3\) \(s_n\;\approx\;\left(\frac{2}{7}\right)^n\;\cdot\;\left(\frac{19}{9}\right)^{(n^2)}\)
EDIT Leider habe ich mein Gekrakel wohl falsch abgelesen;
wird in Kürze berichtigt!
Ob sich das noch irgendwie polynomial hinformen lässt,
wage ich zu bezweifeln... 🤔
|
Profil
|
hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 2010
| Beitrag No.10, eingetragen 2023-03-23
|
A265914[n] hat für n>8 sehr exotische Eigenschaften:
- immer zusammengesetzte Glieder (nie Primzahl)
- ein Glied hat nie 2 gleiche Faktoren
- ggT(aller Primfaktoren aller Glieder)=1,
- sehr große größte Primfaktoren:
904632709, 687129481, 49166967897139531, 12564648373391999, 8796606975990781, 409412076081792019, 9505851656755832332675810867
\sourceon nameDerSprache
fast wie f(n)=Prime[n]*Prime[54^n]
\sourceoff
...und die Berechnung ab n>=7 dauert sehr lange...
|
Profil
|
cramilu
Aktiv
Dabei seit: 09.06.2019
Mitteilungen: 2260
Wohnort: Schwäbischer Wald, seit 1989 freiwilliges Exil in Bierfranken
| Beitrag No.11, vom Themenstarter, eingetragen 2023-04-02
|
Nachfolgend die neuesten Grafiken:
Die ersten beiden habe ich nachangepasst, weil mir im Zuge der Studie
des \(6×6\) eine Darstellungsnormierung eingefallen ist, welche ich für
sämtliche größeren \(n\) sowie für andere Pfadanforderungen gleicher-
maßen als geeignet einschätze.
|
Profil
|
| cramilu hat die Antworten auf ihre/seine Frage gesehen. | Dies ist eine Knobelaufgabe!
Der Themensteller hat bestimmt, dass Du Lösungen oder Beiträge zur Lösung direkt im Forum posten darfst.
Bei dieser Aufgabe kann ein öffentlicher Austausch über Lösungen, Lösungswege und Ansätze erfolgen. Hier musst Du keine private Nachricht schreiben! |
|
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. 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]
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
