0 Daumen
1,4k Aufrufe

Zeigen Sie durch vollständige Induktion: Für alle n ∈ N kann ein Schachbrett mit 2n × 2n 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

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

Induktiosnannahme:

3 teilt 2n * 2n -1

Induktionsschritt:

2(n+1) * 2n+1) -1 = 4 * 2n * 2n = 4 * (2n * 2n - 1 + 1) -1 =

von

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 2n × 2n Feldern, von denen ein beliebiges Feld entfernt worden ist, durch L-förmige Teile (siehe Abbildung 1) vollständig bedeckt werden.

20211123_004046.jpg

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.

5 Antworten

+1 Daumen

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:

blob.png

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:

blob.png

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

von 48 k

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!

0 Daumen

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) \)

von 4,6 k

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

0 Daumen

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

von 123 k 🚀

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

schach.png   

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.

0 Daumen
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

AA




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
DD


AD
BAAC
BBCC
von 53 k 🚀

okay danke, damit werde ich versuchen, weiterzuarbeiten

0 Daumen

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.

von 477 k 🚀

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community