Kugeln auf Brettern platzieren

06.09.2008, 13:53

Vieta

Kugeln auf Brettern platzieren

Ich habe in einem anderen, nicht mathematischen Forum folgendes Rätsel gefunden:

Zitat:

Es gibt eine Art Schachfeld mit $\begin{eqnarray*} 21\cdot 21 \end{eqnarray*}$ Feldern also insgesamt 441 stück. Auf diese Felder kann immer ENTWEDER eine schwarze ODER eine rote Kugel gelegt werden. Jedes Feld muss am Ende mit einer Kugel gedeckt sein. Am Ende müssen alle "Informationen" auf das gelegte Feld passen. Die Informationen sind: - Für jede Spalte habe ich die Anzahl der Roten Kugeln vorgegeben. - Für jede Zeile habe ich die Anzahl der schwarzen Kugeln vorgegeben. - Für jede Diagonale (von links unten nach rechts oben) habe ich die Anzahl der schwarzen Kugeln vorgegeben. - Ich weiß, das es in etwa (nicht genau) soviele schwarze wie rote Kugeln gibt.

Eine genaue Frage fehlte, aber es ist anzunehmen, dass derjenige Wissen wollte, ob es möglich ist, die Kugeln den Informationen entsprechend zu verteilen....

Dann kam im Forum noch folgender Hinweis:

Zitat:

Mit Backtracking müsstest du es rausbekommen, für ein lin. Gleichungssys. hast du zu viele Unbekannte.

Ferner hat jemand folgende Aussage getätigt:

Zitat:

Hi, Tut mir Leid das ich erst heute das Rätsel lese, wahrscheinlich ist es jetzt eh schon zu spät trotzdem möchte ich noch beweisen das es nicht geht nur um die neugier zu befriedigen. Es gibt insgesamt 2^(21*21) Möglichkeiten Steine auf dem Brett zu plazieren, wobei 2 die anzahl an Farbmöglichkeiten darstellt und 21*21 die Brettgröße. Nun habe ich mir angeschaut wie viele verschiedene Möglichkeiten es gibt die Zahlen um das Brett zu verteilen. Für jede spalte und jede Zeile gibt es insgesamt 22 Möglichkeiten (nämlich alle von 0-21). Für die Diagonalen wachsen die Möglichkeiten für die Zahlen von 2 auf 22 an und sinken dann wieder auf 2 ab. Nehme ich also alle Möglichkeiten für die Zahlengebung mit einander mal komme ich hiermit auf (22^42)*(21Fakultät*22Fakultät). Hierbei ergibt sich das Problem das es mehr Möglichkeiten gibt Steine auf das Feld zu legen als Zahlen an den Rand zu schreiben. Um genau zu sein 4,1*10^35 mal so viele. Anders ausgedrückt auf eine Ausgangskombination von Zahlen fällt nicht etwa ein Lösung sondern 410 Pentalliarden. Die Lösung lässt sich nicht eindeutig bestimmen.

Jetzt wollte ich mal fragen, was ihr als fachkundige Leute zu dem Rätsel und den zitierten Beiträgen sagt. smile

Ich habe mir natürlich auch gedanken gemacht, bin aber nicht sehr weit gekommen...

Quelle: http://board.ogame.de/thread.php?threadid=648914

06.09.2008, 16:51

Auf diesen Beitrag antworten »

Es ist schon aus einem viel banaleren Grund klar, dass nicht jede Vorgabe von Zeilen- und Spaltenanzahlen von roten Kugeln erfüllbar ist:

Schließlich muss die Summe aller Zeilenanzahlen mit der Summe aller Spaltenanzahlen übereinstimmen - beides muss die Gesamtanzahl der roten Kugeln auf dem Brett ergeben!

06.09.2008, 18:38

Kakaozwiespalt

Auf diesen Beitrag antworten »

Es wäre trotzdem mal interessant, ob man mit vorgegebenen Zahlen ein eindeutiges Muster erhält(vorrausgesetzt die Kombination ist überhaupt möglich).
Wenn man alle Diagonalen bedenkt, müsste man für die Zahlen auf
$\begin{eqnarray*} 22^{42}(22!21!)^2>2^{22*21}>2{241 \choose 120} \end{eqnarray*}$
Möglichkeiten kommen. Der letzte Term sind die Möglichkeiten für fast Gleichverteilung der Farben.
Aus der ersten Zahl müsste natürlich alles rausgestrichen werden, was keine mögliche Verteilung ergibt...

Das scheint nicht wirklich zu helfen, kann man das nicht irgendwie anders zeigen? verwirrt

06.09.2008, 20:08

Auf diesen Beitrag antworten »

Zitat:

Original von Kakaozwiespalt
Es wäre trotzdem mal interessant, ob man mit vorgegebenen Zahlen ein eindeutiges Muster erhält(vorrausgesetzt die Kombination ist überhaupt möglich).

Nein, nicht in jedem Fall:

code:
1: 2: 3: 4: 5: 6: 7: 8:	0 1 0 0 0 1 1 0 0 0 0 1 1 0 0 0 1 0

Sollte klar sein, dass man dieses 3x3-Beispiel auch auf 21x21 erweitern kann (z.B. durch Nullen auffüllen).

06.09.2008, 20:19

Kakaozwiespalt

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent

code:
1: 2: 3: 4: 5: 6: 7: 8: 9: 10:	\2\0 0\0 1 0 0\0 0 1 1\1 0 0 \0 \1 0\0 0 1 2\1 0 0 0\0 1 0

Daran hatte ich auch zuerst gedacht, aber die Figur ist ja nur nicht eindeutig wenn man nur die Diagonalen nach "oben rechts" beachten. Hat man noch die nach "unten rechts gegeben", wären die beiden Muster eindeutig.

Sehe gerade: Im Ausgangsposting war nur nach den einen Diagonalen gefragt, ich erweitere das Problem einfach mal ^^

06.09.2008, 20:34

Auf diesen Beitrag antworten »

Zitat:

Original von Kakaozwiespalt
Sehe gerade: Im Ausgangsposting war nur nach den einen Diagonalen gefragt

Eben!

Sag mal:

Vieta = Kakaozwiespalt ? verwirrt