Zahlen verteilen < Kombinatorik < Stochastik < Oberstufe < Schule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 08:34 Fr 14.12.2012 | | Autor: | Ferma |
Hallo,
kennt jemand eine Formel, mit der man folgendes berechnen kann?
Die Anzahl der Möglichkeiten, wie auf einem n x n "Schachbrett" n² Zahlen verteilt werden können. Beispiel: auf 2x2 Feldern können die Zahlen 1 bis 4 auf 8 verschiedene Arten platziert werden. Wie sieht es mit den Zahlen 1 bis 9 aus, auf einem 3 x 3 Feld?
Danke im Voraus
Ferma
|
|
| |
|
Hallo Ferma,
> Hallo,
> kennt jemand eine Formel, mit der man folgendes berechnen
> kann?
> Die Anzahl der Möglichkeiten, wie auf einem n x n
> "Schachbrett" n² Zahlen verteilt werden können. Beispiel:
> auf 2x2 Feldern können die Zahlen 1 bis 4 auf 8
> verschiedene Arten platziert werden.
Was verstehst du in diesem Zusammenhang unter platzieren? Also wenn man da keine weiteren Kriterien fordert, dann gibt es beim 2x2-Feld 24 und beim nxn-Feld allgemein n! Möglichkeiten. Von daher meine Frahe: wie bist du denn zu deiner Zählweise gekommen?
Gruß, Diophant
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:24 Fr 14.12.2012 | | Autor: | Ferma |
Hallo Diophant,
die Zahlen sollen in "schlangenform" platziert werden. Fortlaufende Zahlen sollen entweder horizontal oder vertikal, aber nie diagonal, aufeinander stoßen. Beispiel 3 x 3
123 321 789 543 189 923
654 456 654 672 276 814
789 987 123 981 345 765
Alle unterschiedlichen Darstellungen, soweit sie die Bedingungen erfüllen, sind gültig.
LG Ferma
|
|
|
| |
|
Hallo,
ad hoc würde ich sagen, dass man vielleicht für einfache Fälle wie 2x2 bzw. 3x3 eine explizite Zählformel angeben kann (für 2x2 ist es leicht), für den allgemeinen Fall sehe ich da jedoch schwarz, da das dann viel zu komplex wird. Die Schlange darf ja offensichtlich an jeder Stelle 'abbiegen' mit der einzigen Restriktion, dass sie einen Weg wählen muss, auf dem man alle restlichen Zahlen unterkriegt.
Aber mal wieder eine interessante Fragestellung! 
Gruß, Diophant
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:14 Sa 15.12.2012 | | Autor: | Ferma |
Hallo,
mit n=3 habe ich 32 Möglichkeiten gefunden, mit Ausprobieren. Jetzt möchte ich noch mit n=4 probieren. Das wird etwas länger dauern. Ich hoffe, da ist noch jemand dran!
VG Ferma
|
|
|
| |
|
Hallo Ferma,
in der Tat eine interessante Aufgabe. Eine Formel dafür habe ich auch nicht und zweifle ebenfalls, ob man so leicht eine finden wird. Hier werden auch topologische Fragen berührt, die womöglich nicht ohne weiteres in "Zahlen" zu übersetzen sind.
> mit n=3 habe ich 32 Möglichkeiten gefunden, mit
> Ausprobieren.
Ich finde 40 für n=3.
> Jetzt möchte ich noch mit n=4 probieren. Das
> wird etwas länger dauern. Ich hoffe, da ist noch jemand
> dran!
Mal sehen. Am weiteren Ausprobieren habe ich kein Interesse, aber an einer allgemeinen Lösung. Ab ca. n=5 sehe ich da aber eben ziemliche Schwierigkeiten.
Grüße
reverend.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:37 Sa 15.12.2012 | | Autor: | Ferma |
Hallo reverend,
stimmt, die 40 bei 3 x 3 habe ich jetzt auch. Bei 4 x 4 finde ich 180 Möglichkeiten. Bei n=2=>M=8. Bei n=3=>M=40. Bei n=4=>M=240.
Hier setze ich voraus, noch nicht alle Möglichkeiten gefunden zu haben. (Habe nur 180 gefunden.)
Die Formel M=(1/3)*(2+n)! entspricht für die 3 Fälle, doch allgemein ist da noch nichts bewiesen.
LG Ferma
|
|
|
| |
|
Hallo Ferma,
witzig, ich war auch gerade so weit, wieder etwas zu schreiben. Gutes Timing. 
> stimmt, die 40 bei 3 x 3 habe ich jetzt auch. Bei 4 x 4
> finde ich 180 Möglichkeiten. Bei n=2=>M=8. Bei n=3=>M=40.
> Bei n=4=>M=240.
> Hier setze ich voraus, noch nicht alle Möglichkeiten
> gefunden zu haben. (Habe nur 180 gefunden.)
Ich habe bisher 424...
Schau mal das anliegende ![[a]](/images/paperclip.gif "Dateianhänge") pdf an.
Das sind alle grundlegenden Verläufe, die ich bisher gefunden habe und die nicht durch Drehung oder Spiegelung ineinander übergeführt werden können. Die fünf blauen sind allerdings achsensymmetrisch.
Damit gibt es 24 (schwarze) Verläufe in je 8 Orientierungen auf dem Brett, und jeden kann man vorwärts oder rückwärts nummerieren, also hierfür 24*8*2=384 Möglichkeiten.
Dazu fünf (blaue) Verläufe in nur je 4 Orientierungen, wieder vorwärts oder rückwärts, also weitere 5*4*2=40 Möglichkeiten.
> Die Formel M=(1/3)*(2+n)! entspricht für die 3 Fälle,
> doch allgemein ist da noch nichts bewiesen.
Ich sehe auch nach wie vor nicht, wie man z.B. induktiv vorgehen könnte. Deine Formel jedenfalls kann ja dann so noch nicht stimmen.
Grüße
reverend
Dateianhänge:
Anhang Nr. 1 (Typ: pdf) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:29 Sa 15.12.2012 | | Autor: | Ferma |
Hallo reverend,
habe noch 3 Möglichkeiten gefunden!. Hatte meine Gefundenen mit Deiner PDF Datei verglichen. Ich denke, es sind keine Wiederholungen.
Leider kann ich meine jpg-Datei nicht anhängen! Finde hier keinen Link.
VG Ferma
Datei-Anhang
Dateianhänge:
Anhang Nr. 1 (Typ: jpg) [nicht öffentlich]
|
|
|
| |
|
Hallo Ferma,
Deine erste Möglichkeit habe ich tatsächlich übersehen. Glückwunsch!
Die zweite entspricht meiner Variante K.
Die dritte entspricht Deiner ersten, nur gespiegelt.
Also: ein zusätzlicher Fund mit acht möglichen Orientierungen und jeweils zwei Nummerierungsrichtungen. Macht also (Zwischenstand) bisher 440 Möglichkeiten insgesamt.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:01 Sa 15.12.2012 | | Autor: | Ferma |
Hallo reverend,
ist das nicht neu?!
Ich hoffe es ist keine Spiegelung oder Drehung!
Datei-Anhang
LG Ferma
Dateianhänge:
Anhang Nr. 1 (Typ: jpg) [nicht öffentlich]
|
|
|
| |
|
Hallo nochmal,
> ist das nicht neu?!
> Ich hoffe es ist keine Spiegelung oder Drehung!
> Datei-Anhang
Doch, das ist auch neu. Ich habe Deinen letzten Fund mal auf meinem Blatt als Variante DD, diesen neuen als EE angefügt, und einen eigenen (auch noch fehlenden) als FF, einen weiteren (symmetrischen) als GG.
Bisher damit 6 achsensymmetrische (5*4*2 M.) und 27 symmetrielose (27*8*2 M.), zusammen 480 Möglichkeiten.
Irgendwie habe ich den Eindruck, da fehlen immer noch welche. Aber ich bin gerade mit etwas anderem beschäftigt, suche also nicht aktiv. Was ja auch noch nicht heißt, dass ich dann auch etwas finden würde...
Hier die neue Übersicht
Grüße
reverend
Dateianhänge:
Anhang Nr. 1 (Typ: pdf) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 01:42 So 16.12.2012 | | Autor: | reverend |
Hallo,
ich habe immer noch nicht systematisch gesucht, siehe unten.
Trotzdem habe ich noch einen symmetrischen und einen unsymmetrischen Verlauf gefunden, damit weitere 8+16 Wege einer Nummerierung.
Das sind in der Übersicht natürlich die letzten beiden, HH und II. GG habe ich mal auf den Kopf gestellt, dann fällt eine Einordnung später m.E. leichter.
Um Vollständigkeit zu erlangen, schwebt mir gerade ein eher einfaches Programm vor. Nur müsste ich mir auf den mittlerweile gefühlte 17mal abgestürzten Rechner wieder eine Programmiersprache aufspielen, was mir irgendwie riskant erscheint. Wahrscheinlich zuviel der Vorsicht, oder auch Faulheit. Nur habe ich die letzten Male Python nicht zum Laufen bekommen, C++ fraß zuviel Speicher, VisualBasic verleitet mich zu Spaghettitricks, und für ein vernünftiges CAS fehlt mir das Geld.
Trotzdem dürfte es jetzt nicht mehr viel Fehlbestand geben. Zur Zeit haben wir 504 mögliche "Schlangen" auf dem 4*4-Brett. Das ist immerhin eine schön faktorisierbare Zahl: [mm] 504=2^3*3^2*7, [/mm] damit lässt sich für etwaige Hypothesen vielleicht doch etwas anfangen...
Andererseits habe ich einfach mal durchgesehen, ob es Hinweise auf eine sinnvolle Rekursion gibt. Die rot markierten Variantennamen enthalten keine 3*3 Substruktur, die schwarzen haben eine solche, wären also ableitbar.
Knapp gesagt: es gibt zu viele rote.
Eine ähnliche Erhebung für ein 5*5-Feld halte ich ohne System für sinnlos. Von daher lohnt sich vielleicht doch eine Programmierung? Ich könnte ja mal Pseudocode versuchen, aber ob das in den nächsten Tagen und Wochen klappt, würde ich bezweifeln. Bis incl. 25.12. habe ich genügend Arbeit, der 26. ist verplant, dann bin ich bis zum Ende der ersten Januarwoche verreist und im Anschluss familiär eingespannt, und wenn ich so etwa am 7.1. meinen Schreibtisch wiedersehe, wird der einfach voll sein...
Darum hier eine kleine Skizze der zu lösenden Probleme für eine Programmierung:
1) Auswahl von Startfeldern und Reihenfolge der Bearbeitung
Am einfachsten ohne Beachtung jeglicher Symmetrien! Der Rechenaufwand kann hierdurch fast 8mal so hoch sein, wie bei einer geschickteren Programmierung. Diese verliert ihren Vorteil aber durch aufwändige Symmetriebetrachtungen.
Felder werden durchgezählt wie man westlich liest: von links nach rechts, von oben nach unten (was auch aus einer sinnvollerweise anzulegenden zweidimensionalen Indizierung leicht herzuleiten ist). Ein "fertiger" Weg darf nur bei einem Feld mit höherer Ordnungszahl enden. Dann zählt jeder Weg doppelt, weil er vorwärts oder rückwärts durchnummeriert werden kann.
1.1) Bei n*n-Feldern mit n=2k ist jedes Feld als Startfeld denkbar.
1.2) Für n=2k-1 gehen nur die als Startfeld, die bei einer Schachbrettfärbung die Farbe der Ecken haben.
2) Es genügt, die Richtungswahl für den nächsten Schritt einfach rekursiv zu halten: die Richtungspriorität ist z.B. rechts, unten, links, oben (oder jede andere Prioritätenfolge). Ist das so zu betretende Feld schon besetzt, zurück zur Richtungswahl und nächste Richtung. Steht keine mehr zur Verfügung, ein Feld zurück.
3) Hat der Weg [mm] n^2 [/mm] Schritte erreicht, so ist er vollständig. Überprüfung Ordnungszahl Endfeld im Vergleich zum Anfangsfeld.
4) Ganz nebenbei Zählung aller gefundenen vollständigen Wege.
Das genügt, um die genaue Zahl aller möglichen "Schlangen" zu ermitteln. Das meiste ist leicht umzusetzen, birgt aber u.U. ein paar Justierungsfallen.
Falls Du es selbst versuchen willst, wünsche ich Dir viel Erfolg!
Grüße
reverend
Dateianhänge:
Anhang Nr. 1 (Typ: pdf) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 07:55 So 16.12.2012 | | Autor: | Ferma |
Guten Morgen,
ich hab noch eine!
Vielen Dank für Deinen Beistand, professionell, herzerfrischend, wie immer.
Hoffe, dass es im Januar weiter geht.
Viele Grüße
Ferma
Datei-Anhang
Dateianhänge:
Anhang Nr. 1 (Typ: wmf) [nicht öffentlich]
|
|
|
| |
|
Guten Morgen,
> ich hab noch eine!
stimmt, die fehlte auch noch. Ich hab mal eine zweite Seite aufgemacht und die letzte Zeile von vorher mit herübergenommen, damit "JJ" nicht so allein herumsteht. (neue Übersicht)
Neuer Stand: 520 Möglichkeiten (unwahrscheinliches Ende - wieso sollte das durch 13 teilbar sein?)
Es ist schon auf diesem kleinen "Brett" gar nicht so einfach, den Überblick zu behalten.
> Vielen Dank für Deinen Beistand, professionell,
> herzerfrischend, wie immer.
> Hoffe, dass es im Januar weiter geht.
Das ist nett, danke.
Wir werden sehen. Angeblich habe ich in Italien, wo ich zwischendurch bin, sogar einen Internetanschluss, aber die letzten Male wo einer "garantiert" war, funktionierte dann gerade die Technik nicht oder der Onkel hatte den Provider gewechselt, die Stadtwerke die Leitung beschädigt oder eine fortschrittsfeindliche Nachbarin hatte alle Übertragungsprotokolle kaputtgebetet. Mal sehen, was es diesmal für Gründe gibt.
Aber noch ist ja eine Woche; bis dahin sollte sich das Problem doch wenigstens für das 4*4-Brett lösen lassen.
Ich habe auf Deutsch und Englisch nach der Problemstellung gegoogelt und nichts Gutes gefunden. Die Frage gibt schon hie und da, aber der einzige Link, der aus einer Diskussion heraus auf eine Lösung verweist, zeigt auf eine nicht mehr existente Seite.
Du hast oft spannende Fragestellungen. Ich nehme an, das resultiert vor allem daraus, dass Du Dir selbst überlegst, ob Du ein bestimmtes Problem lösen kannst. Das ist halt etwas anderes als die typischen Übungsaufgaben und oft nicht oder nur schwer lösbar. Jedenfalls braucht man eine eigene Herangehensweise.
Hier habe ich immer noch keine außer dem Vorschlag einer programmtechnischen Lösung, die wahrscheinlich ein 8*8-Brett gerade noch schafft, je nach Rechner und Zeitaufwand, den man da opfern möchte, auch noch etwas größer. Dabei wäre es ja nur eine "Krücke", um vielleicht zu einer Hypothese zu finden, wie sich die genaue Zahl solcher Wege berechnen ließe - und diese Hypothese müsste man dann auf andere Art beweisen. Das scheint noch sehr weit weg zu sein.
Grüße
reverend
Dateianhänge:
Anhang Nr. 1 (Typ: pdf) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:06 So 16.12.2012 | | Autor: | reverend |
Hm. Das nimmt kein Ende.
Übersicht, neu: KK.
Jetzt also 536=8*67 Möglichkeiten. Das kann auch noch nicht das Ende sein...
Dateianhänge:
Anhang Nr. 1 (Typ: pdf) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:16 So 16.12.2012 | | Autor: | Ferma |
nein, das war nicht die letzte...hier ist noch einer. Jetzt 552 Möglichkeiten!
Datei-Anhang
Dateianhänge:
Anhang Nr. 1 (Typ: wmf) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:49 So 16.12.2012 | | Autor: | Ferma |
da ist mir leider ein Fehler unterlaufen! LL=X
womöglich ist das Ende der Fahnenstange erreicht.
VG Ferma
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:17 Mo 17.12.2012 | | Autor: | Ferma |
Hallo reverend,
doch, es gibt garantiert keine einzige Variante mehr! Jetzt könnte man an die allgemeine Formel denken. Aber das wird schwer und in diesem Jahr nicht mehr machbar sein! Eine gute Zeit!
Ferma
|
|
|
|
![[a]](uploads/forum/00936305/forum-i00936305-n001.jpg "Dateianhänge"){kind=small}
Datei-Anhang![[a]](uploads/forum/00936356/forum-i00936356-n001.jpg "Dateianhänge"){kind=small}
Datei-Anhang