ich weiss das ist schon älter aber es soll immer welche geben dies noch niocht kennen:
aufgabe: belege ein schachbrett so mit dominosteinen, dass ein dominostein zwei felder überdeckt
geht
?? geht das auch wenn ich die linke obere und die rechte untere ecke „wegschneide“??
viel spass
Martin
Ps wers schon kennt nicht auflösen - die andern sollen noch spass haben - mailt mir einfach
Achtung: SPOILER (d.h. Lösung) 
Hallo,
wenn das Rätsel hier schon gestellt wird, dann will ich es auch lösen:
Also, es geht nicht!
Ein Dominostein bedeckt immer ein schwarzes und ein weißes Feld. Wenn ich aber die zwei Eckfelder abschneide, verschwinden zwei gleichfarbige Felder, d.h. ich kann mit den Dominosteinen nicht mehr alle Felder abdecken.
Gruß Alex
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
wenn das Rätsel hier schon gestellt wird, dann will ich es
auch lösen:Also, es geht nicht!
wieso?
im ersten falle lege ich 8 reihen zu je 4 steinen, die jeweils 2 nebeneinander liegende felder bedecken.
--------
--------
--------
--------
--------
--------
--------
--------
im 2 falle lege ich in der ersten reihe (beginnend mit dem 2.feld (li.o. fehlt)) 3 steine nebeneinander, ins 8.feld (gezaehlt das siebente) lege ich einen stein so, dass er in die naechste 2.zeile ragt. dort lege ich 3 steine, die jeweils 2 nebeneinanderliegende steine ueberdecken, ins erste feld wieder einer, der in die naechste zeile geht.
------|
|------|
|------|
|------|
|------|
|------|
|------|
|------
Ein Dominostein bedeckt immer ein schwarzes und ein weißes
Feld. Wenn ich aber die zwei Eckfelder abschneide,
verschwinden zwei gleichfarbige Felder, d.h. ich kann mit den
Dominosteinen nicht mehr alle Felder abdecken.
wieso sollte die farbe relevant sein?
kleiner Denkfehler
Hi,
Die Erklärung mit der Farbe ist mathematisch völlig richtig, allein deshalb schon kann es nicht gehen.
Deine Skizze ist etwas verwirrend.
Mal das doch mal auf kariertem Papier sauber auf, dann wirst du sehen, dass du am Ende 2 einzelne Felder, die weit auseinander liegen, übrig hast.
Gruss,
Aufgabenstellung beachten!
Hi dog.je,
deiner Skizze entnehme ich, dass bei dir jeder Dominostein auf genau eines der 64 Felder passt. Die Aufgabe besteht aber darin, dass Dominosteine verwendet werden sollen, deren Groesse gerade ZWEI Felder bedecken. Wenn du es so versuchst, wirst du feststellen, dass eine vollstaendige Bedeckung des 64 Felder grossen Schachbrettes nicht moeglich ist, falls zwei gegenueberliegende Eckfelder fehlen.
Gruss
Jens
Hi dog.je,
deiner Skizze entnehme ich, dass bei dir jeder Dominostein auf
genau eines der 64 Felder passt.
tun sie nciht, jeder strich ist ein halber dominostein.
aber das tut nix zur sache.
Hi,
Die Erklärung mit der Farbe ist mathematisch völlig richtig,
allein deshalb schon kann es nicht gehen.
ok, nachdem ich die urspr. erlaeuterung gelesen habe, ist mir die relevanz der farben gekommen.
weil am schachbrett nebeneinander bzw. untereinander immer wechselnde farben sind, muss ein stein immer ein sw und ein ws feld belegen, was heisst, dass ich immer gleich viel sw und ws felder benoetige, und wenn ich re o und li u wegnehme, ist die anzahl der sw + ws felder ungleich, weil die 1+letzte zeile um 1 verschoben sind, weil die gesamtanzahl gerade ist.
so verquer muss man erst mal denken… und sowas lernt ihr im mathe-studium?
Ja!
Hallo dog.je,
so verquer muss man erst mal denken… und sowas lernt ihr im
mathe-studium?
das war eine typische Einstiegsaufgabe aus dem Bereich der Kombinatorik.
Falls du noch was zum Knobeln suchst, dann schau doch mal hier im Forum-Archiv nach dem „Ziegenproblem“…
Gruß Alex
Nochmal Ja
Hi,
so verquer muss man erst mal denken… und sowas lernt ihr im
mathe-studium?
Im Physikstudium geht es ähnlich zu.
Man beschreitet zum Teil Wege, die mit der Lösung zunächst mal nichts zu tun haben, und plötzlich PLUMPS ist man am Ziel.
Gruss,
Variante der Aufgabe
Hallo,
hier eine Abwandlung der Aufgabenstellung.
Von dem Schachbrett werden jetzt nicht zwei gegenüberliegende Eckfelder entfernt, sondern zwei beliebige ungleichfarbige Felder. Lässt sich dann das verbleibende Brett vollständig mit Dominosteinen überdecken?
Wie sieht es auf einem „Schach“-Brett aus, das aus n mal n Feldern besteht (n eine gerade natürliche Zahl)?
Viel Spaß beim Knobeln.
Gruß
Jens
Hallo,
kurze Antwort - ja es ist möglich. Die Begründung dazu liefere ich, falls sich bis heute abend kein anderer findet (evtl. bekomme ich es bis dahin auch noch etwas kompakter dargestellt).
Gruss
Enno
Lsg.
Hallo,
ich halte das ganze weitgehend informal, scheint mir so verständlicher zu sein. Wenn man das verallgemeinerte n x n Schachbrett als
a(1,1) a(2,1) ... a(n,1)
a(1,2) a(2,2) ... a(n,2)
. . .
a(1,n) a(2,n) ... a(n,n)
darstellt mit a(i,j) aus {s,w} und a(i1,j1)=a(i2,j2) gdw. i1+j1 mod 2=i2+j2 mod 2 und die beiden Traversierungen
Links oben beginnend:
(1,1),(1,2),...,(1,n),
(2,n),(2,n-1),...,(2,1),
. . .
(n-1,1),(n-1,2),...,(n-1,n),
(n,n),(n,n-1),...,(n,1)
(1,1) ist der Startindex. (n,1) ist der Endindex.
und Links unten beginnend:
(1,n),(1,n-1),...,(1,1),
(2,1),(2,2),...,(2,n),
. . .
(n-1,n),(n-1,n-1),...,(n-1,1),
(n,1),(n,2),...,(n,n)
(1,n) ist der Startindex. (n,n) ist der Endindex.
betrachtet, werden alle Felder des Schachbretts besucht und abwechselnd schwarze und weisse Felder betreten. Ein „Weg“ von einem Index (i1,j1) zu (i2,j2) mit (i1,j1)h wird analog behandelt, g=h durch Drehen des Schachbretts um 90°), laesst sich die Traversierung in drei Teile splitten: Einem „Anfangsweg“ vom Startindex zum Vorgaenger von (g,h), einen „mittleren Weg“ vom Nachfolger von (g,h) zum Vorgaenger von (k,l) und letztlich einen „abschliessenden Weg“ vom Nachfolger von (k,l) zum Endindex. Der mittlere Weg hat immer gerade Laenge. Beim Anfangs- und abschliessenden Weg haengt dies von der Traversierung ab. Es gilt aber, dass in genau einer der beiden Traversierungen beide Weglaengen gerade sind. Genau diese Traversierung ziehen wir heran um die n^2-2 validen Felder mit Dominosteinen zu ueberdecken. Das funktioniert praechtig, bis auf den Fall, dass der Startindex invalide, also der Anfangsweg leer resp. die leere Folge ist. Hier beginnen wir die Traversierung beim Nachfolger des Startindex und verfahren analog.
Gruss
Enno
Leichte Zusatzfrage
Hallo,
an sich sehr leicht aber dennoch wg. der Aufgabenstellung nicht uninteressant. Kann man mehr als 2 (ungleichfarbige) Felder entfernen (so daß die Überdeckung bei beliebig aber gerader Seitenlänge des Schachbretts immer noch möglich ist) ?
Gruss
Enno
ich denke ja solange die anzahl der felder insgesamt gerade bleibt und genausoviele weisse wie schwarze felder vorahnden sind ist die aufgabe lösbar
Martin
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
Hallo Enno,
dein Beweis funktioniert, gratuliere.
Die Argumentation wird etwas einfacher, wenn man einen geschlossenen Weg wählt, zum Beispiel
((1,1),(1,2),(1,3),…,(1,n),
(2,n),(3,n),(4,n),…,(n,n),
(n,n-1),(n-1,n-1),(n-2,n-1),…,(2,n-1),
(2,n-2),(3,n-2),(4,n-2),…,(n,n-2),
(n,n-3),(n-1,n-3),(n-2,n-3),…,(2,n-3),
…
(n,1),(n-1,1),(n-2,1),…,(2,1).
Die beiden markierten Felder unterteilen diesen Weg in zwei Teilwege. Da die beiden markierten Felder ungleichfarbig sind, bestehen beide Teilwege aus je einer geraden Anzahl an Feldern. Beide Teilwege lassen sich also komplett mit Dominosteinen bedecken. (Falls die markierten Felder benachbart sind, kann es sein, dass einer der Teilwege zu einem Nullweg entartet (bestehend aus 0 Feldern), der andere Weg besteht dann aus 2^n-2 Feldern.)
Viele Grüße
Jens
Leider falsch
Hallo Martin,
einfaches Gegenbeispiel:
ich markiere die folgenden 4 Felder:
(1,2),(2,1),(n-1,1),(n,2).
Da n gerade ist, sind die beiden ersten Felder gleichfarbig, die beiden anderen Felder haben die jeweils andere Farbe. Es sind also 2 weiße und 2 schwarze Felder markiert. Eine vollständige Belegung ist jedoch nicht möglich, denn die Felder (1,1) und (n,1) sind unerreichbar.
Gruß
Jens
Hallo,
ja man kann Ecken „isolieren“ (für den Fall eines mind. 4 x 4 Schachbretts. Für ein 2 x 2 Schachbrett wäre die Überdeckung bei 4 entfernten Steinen zugegebenermaßen leicht *g*).
Auf der anderen Seite gibt es natürlich schon Möglichkeiten max. n^2/2 schwarze und weiße Felder zu entfernen, so daß eine Überdeckung möglich ist. Die naheliegende Frage wäre nun, ob man eine schwächste Bedingung für das Entfernen der Felder findet, so daß immer noch eine Überdeckung möglich ist. Für den Fall von einem schwarzen und einem weißen Feld wäre die gerade „wahr“. Wie sieht es für 4,6,8,…,n^2 Felder aus ?
Gruss
Enno
PS: Die Lsg. kenne ich selbst nicht.
Hallo,
ja die Lsg. ist eleganter. Meine Lsg. war eher ad hoc, da ich den Beweis zunächst über Induktion der Feldgröße geführt hatte und der länglich und umständlich war.
Gruss
Enno
Lösung?
Hallo,
also ich fasse noch mal zusammen.
Wenn man bei einem n^2-Schachbrett (n gerade) unterschiedlich viele weiße und schwarze Felder entfernt (egal welche), ist eine Überdeckung mit Dominosteinen nicht möglich.
Werden ein beliebiges weißes und ein beliebiges schwarzes Feld entfernt (also insgesamt 2), so ist eine vollständige Überdeckung stets möglich.
Werden 2*m Felder entfernt (m weiße und m schwarze, 1 0
bzw q = n, falls 2*m mod n = 0
und p = 1 + (2*m-q)/n.
Eine mögliche Bedeckung ist dann einfach die folgende:
((p,q+1),(p,q+2)),((p,q+2),(p,q+3)),…,((p,n-1),(p,n)),
((p+1,1),(p+1,2)),(p+1,3),(p+1,4)),…,((p+1,n-1),(p+1,n)),
…
((n,1),(n,2)),(n,3),(n,4)),…,((n,n-1),(n,n)).
Eine solche Überdeckung ist deshalb immer möglich, weil q und n beide durch 2 teilbar sind.
w.z.b.w.
Es kann natürlich sein, dass ich die Frage falsch verstanden habe, denn die Lösung kommt mir irgendwie zu einfach vor.
Viele Grüße
Jens.
Hallo,
die Aufgabe ist einen Tick komplizierter. Du hast eine hinreichende Bedingung geliefert, die das Entfernen der Felder genau in der von Dir beschrieben Art einschränkt. Die/eine „schwächste Bedingung“ wäre eine notwendige Bedingung zum Entfernen der Felder, so daß eine Überdeckung immer noch möglich ist. Es ist z.B. auch möglich, in dem von Dir beschriebenen „Rundkurs“ aufeinanderfolgende Felder zu entfernen - trotzdem findet sich noch eine Überdeckung.
Der „Rundkurs-Beweis“ läßt sich auch auf n x m Schachbretter (mit nm gerade und n>=4, m>=3) verallgemeinern. Ein etwas allgemeineres Kriterium könnte nun z.B. fordern, daß sich das n x n Schachbrett (mit n>=4) in z.B. t Schachbretter der Größe k(1) x n, k(2) x n, … , k(t) x n (mit k(1)+k(2)+…+k(t)=n und k(i)>=4) zerlegen läßt, so daß in den t Schachbrettern jeweils ein schwarzes und ein weißes Feld entfernt wurde (das ist sicher nicht die „beste Näherung“ an ein notwendiges Kriterium).
Gruss
Enno