Schachbrett Problem mit L-förmigen Teilen

Question

Zeigen Sie durch vollständige Induktion: Für alle n ∈ N kann ein Schachbrett mit 2ⁿ × 2ⁿ Feldern, von denen ein
beliebiges Feld entfernt worden ist, durch L-förmige Teile vollständig bedeckt werden

Dabei dürfen die L-förmigen Teile natürlich beliebig gedreht sein, aber nicht übereinander liegen oder
über das Schachbrett hinausragen.

Mein Ansatz:

Zeige:
3 teilt 2^n * 2^n -1

Induktionsanfang:

n = 1

2ⁿ * 2ⁿ -1 = 3
=> 3 teilt 3

Induktiosnannahme:

3 teilt 2ⁿ * 2ⁿ -1

Induktionsschritt:

2⁽ⁿ⁺¹⁾ * 2ⁿ⁺¹⁾ -1 = 4 * 2ⁿ * 2ⁿ = 4 * (2ⁿ * 2ⁿ - 1 + 1) -1 =

Comments

Vom Duplikat:

Titel: Zeigen Sie durch vollständige Induktion: Für alle n ∈ ℕ kann ein Schachbrett mit 2n × 2n Feldern, von denen ein …

Stichworte: diskrete

Aufgabe:

Zeigen Sie durch vollständige Induktion: Für alle n ∈ ℕ kann ein Schachbrett mit 2ⁿ × 2ⁿ Feldern, von denen ein beliebiges Feld entfernt worden ist, durch L-förmige Teile (siehe Abbildung 1) vollständig bedeckt werden.

Text erkannt:

Abbildung 1: L-förmige Teile

Dabei dürfen die L-förmigen Teile natürlich beliebig gedreht sein, aber nicht übereinander liegen oder über das Schachbrett hinausragen.

Problem/Ansatz:

Es wäre sehr lieb, wenn jemand mir hilft. Ich bitte Sie um Ihre Hilfe.

Answer 1

Hallo kolt,

wie Roland schon erwähnt hat, genügt es nicht zu zeigen, dass die Anzahl der Felder minus 1 durch 3 teilbar ist. Nehme z.B. mal ein Feld von \(3\times 3\). Es besteht aus 9 Feldern. Und man kann es trotzdem nicht vollständig mit 3 L-förmigen Puzzlestücken auslegen. Versuche es einfach mal.

Beginne mit dem Induktionsanfang. Für \(n=1\) sieht das Feld so aus:

Es ist ein \(2\times 2\)-Feld und das freie Feld liegt in diesem Fall immer in einer Ecke. Und in den Rest passt das L-Stück genau hinein. Damit ist für \(n=1\) gezeigt, dass es geht.

.. und wir kommen zum Induktionsschritt:

Es ist zu zeigen, dass man ein Feld von \(2^{n+1} \times 2^{n+1}\) so mit den L-Stücken auslegen kann, dass ein beliebiges Feld frei bleibt. Wir dürfen dazu annehmen, dass es bei einem \(2^n\times 2^n\)-Feld möglich ist (das ist die Induktionsannahme). Das neue Feld ist viermal so groß, jede Kantenlänge hat sich verdoppelt. D.h. es liegt nahe, es in vier gleich große Quadrate zu zerteilen:

Das Quadrat links unten ist ein \(2^n\times 2^n\)-Feld und enthält bereits das freie Feld (grün). Die anderen drei Teilquadrate legen wir nun so mit L-Stücken aus, dass das freie Feld jedes der drei zusätzlichen Teilquadrate den Mittelpunkt \(M\) berührt. Dies ist ja möglich, da diese ebenfalls \(2^n\times 2^n\)-Felder sind (s. Induktionsannahme). Und in die so entstandene freie Stelle passt wieder genau ein L-Stück hinein (rot).

Und da man das ganze Gebilde jeweils um 90° drehen kann und vorher das grüne Feld beliebig plazieren kann, kann das freie Feld sich an jeder beliebigen Stelle befinden.

Damit ist bewiesen, dass es auch für \(2^{n+1}\times 2^{n+1}\)-Felder möglich ist.

Gruß Werner

Comments

Sehr gut erklärt und verbildlicht. Danke für deine Mühen.

Jedoch habe ich Schwierigkeiten, das in einen mathematischen Beweis zusammenzufassen.

---

Jedoch habe ich Schwierigkeiten, das in einen mathematischen Beweis zusammenzufassen.

Das IST ein mathematischer Beweis ;-) Die Antwort oben besteht aus logischen Schlüssen, die auf gegebenen Annahmen basieren. Mehr braucht es nicht für einen mathematischen Beweis.

---

Ja, aber es soll ja durch vollständige Induktion bewiesen werden. Und da hakt es halt bei mir

---

.. aber es soll ja durch vollständige Induktion bewiesen werden.

Nun - ich habe es doch durch vollständige Induktion bewiesen. Oder bist Du da anderer Meinung? Was fehlt Dir an der Antwort?

---

Vollständige Induktion darf man auch durch Sätze anstatt durch mathematische Formeln beweisen? Wusste ich nicht sorry

---

Vollständige Induktion darf man auch durch Sätze anstatt durch mathematische Formeln beweisen?

Mathematik besteht nicht (nur) aus Formeln. Das Fixieren auf Formeln ist eh' ein weit verbreiteter Fehler gerade von Schülern, die ein paar Schwierigkeiten mit Mathe haben.

Die Frage nach der Formel ist im Allgemeinen die falsche Frage. Die Formel ist oft 'nur' das Ergebnis. Z.B. die berühmte Mitternachtsformel ist das Ergebnis von der (logischen) Überlegung wie man eine quadratische Gleichung löst. Die Zahlenwerte dort einsetzen und in den Taschenrechenr eintippen ist keine Mathematik.

Mathematik ist vor allen Logik. Ein Beweis ist das an einander reihen von logischen Schlüssen. Formeln dienen lediglich dazu, die Schlüsse und das Ergebnis genau (also formal, daher Formel) zu beschreiben. Man könnte sich jetzt eine 'Formelsprache' für das obige Problem ausdenken, aber das macht den Beweis nicht besser.

Tipp: Vergiss das 'formeln' und bei der Gelegenheit schmeiß den Taschenrechner weg; ist auch nur 'ne Denkbremse!

---

Sehr schöner Beweis!

Answer 2

Also das, was du in deinem Ansatz zeigen möchtest, ist eigentlich sehr einfach ohne Induktion möglich:

\( \begin{aligned} R_{3}\left(2^{n} \cdot 2^{n}-1\right) &=R_{3}\left(2^{2 n}-1\right)=R_{3}\left(R_{3}(2)^{2 n}-1\right) \\ &=R_{3}\left((-1)^{2 n}-1\right)=R_{3}(1-1)=0 \end{aligned} \)

\(R_3(x)\) bezeichnet hier den Rest von \(x\) modulus 3.

Für den Induktionsschritt:
\( 2^{n+1} \cdot 2^{n+1}-1=4 \cdot 2^{2n}-1=4 \cdot 2^{2n}-1-3+3=4\left(2^{2n}-1\right)+3\\=4 \cdot 3 k+3 = 3(4k+1) \)

Comments

Wir sollen es aber mit vollständiger Induktion zeigen.

---

ok, ich bearbeite meine Antwort schnell

---

Danke schonmal im voraus

---

Also das, was du in deinem Ansatz zeigen möchtest, ist eigentlich sehr einfach ohne Induktion möglich:\( \begin{aligned} R_{3}\left(2^{n} \cdot 2^{n}-1\right) &=R_{3}\left(2^{2 n}-1\right)=R_{3}\left(R_{3}(2)^{2 n}-1\right) \\ &=R_{3}\left((-1)^{2 n}-1\right)=R_{3}(1-1)=0 \end{aligned} \)

Dann hast du das Problem nicht erfasst. Es geht nicht nur darum, irgendeine Feld mit Vielfachen von 3 auszulegen.

Es geht um die PRAKTISCHE Realisierbarkeit, das mit den verwinkellen Teilen zu schaffen.

---

Du musst in deinem Beweis natürlich schon auf die L-förmige Form der Teile eingehen !

---

Ihr habt wohl meine Antwort missverstanden. Ich habe lediglich das gezeigt, was er in seinem Ansatz zeigen wollte. Ob das nun für das Problem der richtige Ansatz ist, habe ich mit keinem Wort behauptet!

---

Du kannst ruhig sagen, wenn mein Ansatz falsch ist. Es ist ja nicht Sinn der Sache, einen falschen Ansatz fortzuführen

---

Der Ansatz ist ja nicht falsch. Mir war nur nicht bewusst, das dies deine ganze Lösung ist. Das, was du in deinem Ansatz zeigst, ist schliesslich eine notwendige Bedingung für das eigentliche Problem.

---

Okay. Es wäre nett, wenn jemand meinen Ansatz und die Aufgabe vollenden könnte

Answer 3

Es genügt nicht, die Teilbarkeit durch 3 zu zeigen. Zeige, dass ein 2ⁿ⁺¹×2ⁿ⁺¹-Feld sich in vier 2ⁿ×2ⁿ-Felder zerlegen lässt und dass sich das offene Feld durch Drehungen von Teil-Feldern an jede Position bringen lässt.

Comments

Georgs Motto "Ein Bild sagt mehr als tausend Worte" passt hier sehr gut :

  

---

Gerade hatte ich behauptet, hj2166 will dem FS nicht wirklich helfen. Das ist jetzt wohl anders?

---

Dies ist ganz eindeutig eine Hilfe, insbesondere um den Sachverhalt zu erfassen und zum weiteren eigenständigen Denken anzuregen. Natürlich (!) ist es keine abschreibfertige, getextete Komplettlösung.

Answer 4

XXX

Für n=1 ist die Aussage wahr.

Für n=2 lässt sich 1/4 der Felder (siehe oben links) wie für n=1 belegen:

xxx	...
...	...	A
	A	A

Die übrigen drei Viertel lassen sich auslegen, denn nach der Belegung mit den drei A in den übrigen drei Vierteln ist die weitere Auslegung jedes Viertels wie bei n=1 möglich:

xxx		D	D
		A	D
B	A	A	C
B	B	C	C

Comments

okay danke, damit werde ich versuchen, weiterzuarbeiten

Answer 5

Hast du schon beim Induktionsanfang probleme ?

Zeige es also zunächst mal, dass es für n = 1 gilt.

Indunktionsschritt.: Zeige dann, dass wenn es für ein beliebiges n gilt es auch für n + 1 gilt. Du kannst 4 Quadrate für ein n. so zusammenfügen, dass alle fehlenden Felder in der Mitte liegen. Dort kannst du dann ein dreier Teil so reinlegen, dass nur noch eine Ecke frei ist und das Quadrat kannst du so drehen, dass die fehlende Ecke wieder als Ecke außen liegt.