"unendliches Sudoku"

11.10.2014, 18:00

Infinity42

"unendliches Sudoku"

Meine Frage:
Angenommen ich habe eine (beliebig große) Tabelle. Kann ich dann in jede Zelle eine natürliche Zahl schreiben, so dass jede natürliche Zahl in jeder Spalte und jeder Zeile genau einmal vorkommt?

Meine Ideen:
Wenn ich nur eine begrenzte Anzahl an Zahlen nehme, ist es kein Problem (z.B. alle Zahlen mit 3):
1 2 3
2 3 1
3 1 2
ich verschiebe also einfach die Zahlenreihe um eins und schreibe die letze Zahl vorne hin. Diese Strategie funktioniert bei allen natürlichen Zahlen ja nicht mehr, da es keine "letzte Zahl" gibt.

11.10.2014, 18:08

Dopap

Auf diesen Beitrag antworten »

eine beliebig großes Quadrat hat ein letztes Element, genauer:
die Menge $\begin{eqnarray*} \{1,2,3, \cdots , n\} \end{eqnarray*}$ hat ein größtes Element.

Was genau meinst du ?

11.10.2014, 18:19

Guppi12

Auf diesen Beitrag antworten »

Guten Abend,

eines vorweg: es ist ein Unterschied, ob man eine beliebig große Tabelle oder eine unendlich große Tabelle hat. Du meinst hier letzters denke ich.

Was hälst du hiervon(das ist einfach mal drauf los, habe noch nicht bewiesen, dass es wirklich die richtige Eigenschaft hat) :

1 2 3 4 5 6 7 8 9 10 ...
2 1 4 3 6 5 8 7 10 9 ...
3 2 1 6 5 4 9 8 7 12...
4 3 2 1 8 7 6 5 12 11 ...
...

?

Erkennst du, was ich gemacht habe?

11.10.2014, 18:47

Infinity42

Auf diesen Beitrag antworten »

ja, ich meinte eine unendliche Tabelle. Erkenne aber leider auch nicht was du genau gemacht hast. Du hast doch auch bereits in der zweiten Spalte die "2" doppelt

11.10.2014, 18:53

Guppi12

Auf diesen Beitrag antworten »

Äh ja, da war ich kurzsichtig, du hast Recht Augenzwinkern

Wie gesagt, das war einfach mal drauf los. Du kannst ja selbst auch mal etwas überlegen, wie man das machen kann. Ich überlege später auch noch etwas mehr. Habe gerade keine Zeit.

11.10.2014, 18:57

HAL 9000

Auf diesen Beitrag antworten »

Ich fang mal bei 0 statt 1 an, macht sich besser bei den "Bitmanipulationen": Augenzwinkern

code:
1: 2: 3: 4: 5: 6: 7: 8:	0 1 2 3 4 5 6 7 8 9 1 0 3 2 5 4 7 6 9 8 2 3 0 1 6 7 4 5 10 11 3 2 1 0 7 6 5 4 11 10 4 5 6 7 0 1 2 3 12 13 5 4 7 6 1 0 3 2 13 12 6 7 4 5 2 3 0 1 14 15 7 6 5 4 3 2 1 0 15 14

Einfaches bitweises XOR von Zeilen- und Spaltennummer, beide bei 0 beginnend zählen.

11.10.2014, 19:14

Dopap

Auf diesen Beitrag antworten »

sehr gepflegt Freude

die Frage ist nur: wie kommt man darauf verwirrt

oder ist das dem übergroßen Hardwarespeichers des "Computers" geschuldet ? Augenzwinkern

11.10.2014, 19:17

HAL 9000

Auf diesen Beitrag antworten »

Na so richtig funktioniert der Computer momentan nicht, hatte immer noch ein paar Fehler drin (siehe letzte Edits). Na liegt wahrscheinlich an den der beginnenden Erkältung...

11.10.2014, 22:04

Infinity42

Auf diesen Beitrag antworten »

@HAL 9000
kannst du mir bitte noch mal kurz erläutern, was du bei deinem Lösungsvorschlag gemacht hast? Die 1 kommt ja bspw. noch nicht in den letzten Spalten vor. Wie kann ich garantieren, dass wirklich jede Zahl genau einmal vorkommt?

12.10.2014, 10:44

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Infinity42
Die 1 kommt ja bspw. noch nicht in den letzten Spalten vor.

Es war mir leider unmöglich, die gesamte Tabelle aufzulisten. Augenzwinkern

Du redest da von Spalte 9. Der Eintrag 1 kommt dort in Zeile

$\begin{align*} 9 \operatorname{XOR} 1 = 8 \end{align*}$

vor, in meiner Tabelle oben hatte ich aber nur die Zeilen 0..7 aufgeführt (lass dich nicht von der Zeilennummerierung 1: 2: 3: ... 8: in dem code-Fenster irritieren, auf die habe ich keinen Einfluss). Ansonsten liest du dir mal das hier durch:

http://de.wikipedia.org/wiki/Bitweiser_Operator#XOR

Tabelleneintrag $\begin{align*} t \end{align*}$ in Zeile $\begin{align*} z \end{align*}$ findet man wegen der Zuordnungsvorschrift $\begin{align*} t = z \operatorname{XOR} s \end{align*}$ sowie wegen

$\begin{align*} z \operatorname{XOR} t = z \operatorname{XOR} (z \operatorname{XOR} s) = (z \operatorname{XOR} z) \operatorname{XOR} s = s \end{align*}$

in eben jener Spalte $\begin{align*} s = z \operatorname{XOR} t \end{align*}$ .

12.10.2014, 13:09

Infinity42

Auf diesen Beitrag antworten »

Cool danke!!
habe ich es richtig verstanden, dass durch die Zuordnungsvorschrift s=zXORt einer beliegen Zahl t zu einer gegebenen Zeile z eine eindeutige Spalte s zugeordnet wird. Aufgrund der Definition von XOR ist für verschiedene Werte von z (bei festem t) s stehts verschieden --> in einer Spalte kommt eine Zahl nie doppelt vor.
Aber habe ich damit auch gezeigt, dass t in jeder Spalte s vorkommt und dass jeder Tabellenplatz besetzt ist?
Ach ja, was micht noch interessieren würde: wie kommt man eigentlich auf die Zuordnungsvorschrift (die einzelnen Umformungen sind mir klar, nur wo dein erster Ansatz/erste Formel herkommt, verstehe ich nicht so ganz)?

12.10.2014, 13:15

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Tabelleneintrag $\begin{align*} t \end{align*}$ in Zeile $\begin{align*} z \end{align*}$ findet man wegen der Zuordnungsvorschrift $\begin{align*} t = z \operatorname{XOR} s \end{align*}$ sowie wegen

$\begin{align*} z \operatorname{XOR} t = z \operatorname{XOR} (z \operatorname{XOR} s) = (z \operatorname{XOR} z) \operatorname{XOR} s = s \end{align*}$

in eben jener Spalte $\begin{align*} s = z \operatorname{XOR} t \end{align*}$ .

Das ganze lässt sich völlig analog übertragen in die Situation, dass man in Spalte $\begin{align*} s \end{align*}$ den Eintrag $\begin{align*} t \end{align*}$ sucht - und das ist dann genau in Zeile

$\begin{align*} z = s \operatorname{XOR} t \end{align*}$ .

Oder kurz gesagt: Sowohl $\begin{align*} z\mapsto z \operatorname{XOR} s \end{align*}$ (für feste Spalte $\begin{align*} s \end{align*}$ ) als auch $\begin{align*} s\mapsto z \operatorname{XOR} s \end{align*}$ (für feste Zeile $\begin{align*} z \end{align*}$ ) sind bijektive Abbildungen $\begin{align*} \mathbb{N}_0\to \mathbb{N}_0 \end{align*}$ , und das ist es ja letztlich, was du benötigst.

12.10.2014, 22:19

Infinity42

Auf diesen Beitrag antworten »

Ok danke, ich glaube jetzt habe ich es verstanden. D.h. dann, dass ich für die Bildungsforschrift statt t = z XOR s jede beliebige Abbildung f(z,s) nehmen kann für die gilt:
$\begin{eqnarray*} z \rightarrow f(z,s) \end{eqnarray*}$ ist bijektive Abbildung $\begin{eqnarray*} \mathbb{N}_0 \rightarrow \mathbb{N}_0 \end{eqnarray*}$ für s fest bzw.
$\begin{eqnarray*} s \rightarrow f(z,s) \end{eqnarray*}$ ist bijektive Abbildung $\begin{eqnarray*} \mathbb{N}_0 \rightarrow \mathbb{N}_0 \end{eqnarray*}$ für z fest

Neue Frage »

Antworten »

"unendliches Sudoku"

Verwandte Themen