Schachbrett mit der Seitenlänge 2^n - Beweis mittels Vollständiger Induktion?

21.04.2010, 15:41

Matheversteher

Schachbrett mit der Seitenlänge 2^n - Beweis mittels Vollständiger Induktion?

Hallo Matheboarder Wink

Seit geraumer Zeit hänge ich nun schon an folgender Aufgabe:

Gegeben sei ein Schachbrett mit der Seitenlänge $\begin{eqnarray*} 2^n \end{eqnarray*}$ , von dem man ein beliebiges Feld entfernt. Zeigen Sie, dass man das Brett mit "L"-förmigen Kartonstücken überdecken kann. Die Kartonstücke sind dabei so groß, dass sie genau drei Felder bedecken. Die Kartonstücke dürfen sich nicht überlappen.

So habe ich nun angefangen:
$\begin{eqnarray*} (2^n)^2 - 1 \end{eqnarray*}$ durch 3 teilbar $\begin{eqnarray*} \forall n \in \mathbb N \end{eqnarray*}$

IA: für n=1
$\begin{eqnarray*} ({2^1})^2-1 = 3 \end{eqnarray*}$ --> $\begin{eqnarray*} 3/3 = 1 \end{eqnarray*}$ und $\begin{eqnarray*} 1 \in \mathbb N \end{eqnarray*}$ (wahr)

IV: Die Behauptung gelte bis n (fest)

(Ich hoffe ich habe bis hierher keinen Fehler gemacht verwirrt

)

IS: n --> n+1

$\begin{eqnarray*} ({2^{n+1})^2}-1<br /> = {2^{n+1} *2^{n+1} } -1<br /> = 2^n * 2 * 2^n * 2 - 1<br /> = (2^n + 2^n) * (2^n+2^n) - 1 \end{eqnarray*}$

so und an dieser Stelle komme ich nicht mehr weiter. was muss ich nun tun/umformen, damit ich in absehbarer Zeit mal etwas inder Art von $\begin{eqnarray*} (2^n)^2 - 1 \end{eqnarray*}$ da stehen habe. (Oder in Form von $\begin{eqnarray*} (2^n + 1) * (2^n -1 ) \end{eqnarray*}$ ) Ist doch eine binomische Formel, oder ?!

Ich hoffe ich habe bishier her noch alles soweit richtig gemacht. habe jetzt auf meinem Zettel viel rumprobiert aber weis nun nicht mehr weiter. Über Hilfe und Anregungen würde ich mich freuen.

Gruß Flo

21.04.2010, 15:55

tmo

Auf diesen Beitrag antworten »

Es ist $\begin{eqnarray*} 4\cdot2^n-1=3\cdot 2^n + (2^n-1) \end{eqnarray*}$

Aber nur mal so: Das Problem hat eigentlich nichts damit zu tun, dass die $\begin{eqnarray*} (2^n)^2-1 \end{eqnarray*}$ durch 3 teilbar ist. Klar muss das notwendigerweise gelten. Aber die eigentliche Aussage ist noch weitaus stärker.

Mache dir darüber mal Gedanken.

21.04.2010, 17:01

Matheversteher

Auf diesen Beitrag antworten »

Zitat:

Zitat von tmo:
Aber die eigentliche Aussage ist noch weitaus stärker.

Mhhh verstehe ich es recht, dass du auf die "L"-Form hinaus willst?

Dann müsste ja das ganze nicht durch 3 teilbar sein, sondern durch
$\begin{eqnarray*} n* (2^2 -1) \end{eqnarray*}$ ?! bin mir jetzt nicht so sicher.
also 2^2 ist ja ein quadrat von 2x2 kleinen Quadraten. Nehme ich nun ein kleines Quadrat heraus, so sollte ich meine "L"-Form erhalten. Mhhh aber muss ich das (2^2)-1 dann noch mit n "malnehmen"? oder reicht "nur" 2^2?

Edit: Danke für die schnelle Hilfe Freude

21.04.2010, 17:08

tmo

Auf diesen Beitrag antworten »

Vielleicht solltest du mal von der Teilbarkeit wegkommen.

Wenn du ein Quadrat der Seitenlänge $\begin{eqnarray*} 2^{n+1} \end{eqnarray*}$ hast, dann besteht dieses Quadrat aus 4 Quadraten der Seitenlänge $\begin{eqnarray*} 2^n \end{eqnarray*}$ .

Nun nimmst du ein Feld aus dem großen Quadrat raus, das ist dann in irgendeinem der 4 kleinen Quadrate. Nun musst du nur noch aus den 3 anderen Quadraten jeweils ein geeignetes Feld herausnehmen und dann kannst du die Induktionsvorraussetzung 4 mal (auf jedes kleine Quadrat) anwenden.

21.04.2010, 17:33

Matheversteher

Auf diesen Beitrag antworten »

Ohne jetzt die Flinte ins Korn werfen zu wollen. Aber ich glaube ich verstehe dann die Problematik nicht verwirrt

Warscheinlich raufst du dir jetzt die Haare,aber ich habe bisher noch nicht so richtig verstanden, wie und vor allem was ich es hier zeigen soll. unglücklich

*Verdammt*
Oder hört sich das jetzt hier wieder nur schwer an?

Also verstehe ich es richtig, dass ich hier NICHT zeigen soll, dass etwas "immer" durch etwas teilbar ist?

Gruß Flo

21.04.2010, 18:42

Huggy

Auf diesen Beitrag antworten »

Da tmo offenbar offline ist, mische ich mal ein.

Du sollst zeigen, dass ein bestimmtes aus Quadraten zusammengesetztes Brett durch Bausteine, die sich aus Quadraten der gleichen Größe zusammensetzen, überdeckbar ist.

Wenn das Brett aus N Quadraten besteht und der Baustein aus b Quadraten, dann muss selbstverständlich N durch b teilbar sein oder, was dasselbe ist, N ein Vielfaches von b sein. Dabei spielt bisher die Form des Brettes und die Form der Bausteine noch keine Rolle. Ein Brett aus 20 Quadraten lässt sich nicht durch Bausteine aus 3 Quadraten überdecken, egal, wie Brett und Bausteine aussehen.

Dein Versuch die Teilbarkeit zu zeigen, ist also nicht unsinnig. tmo hat dir gezeigt, wie man das machen kann. Das solltest du dir noch mal ansehen.

Aber tmo hat dich auch darauf hingewiesen, dass der Nachweis der Teilbarkeit zwar notwendig, aber nicht hinreichend ist. Also ganz einfach:
Teilbarkeit nicht gegeben: Dann geht es nicht
Teilbarkeit gegeben: Dann geht es vielleicht, vielleicht aber auch nicht.

Ein Beispiel: Betrachte ein 3x3-Brett, bei dem ein Quadrat fehlt. Das Brett besteht also aus 8 Quadraten. Kann man es mit Bausteinen, die 4 Quadrate lang und 1 Quadrat breit sind, überdecken? Der Baustein besteht aus 4 Quadraten und 8 ist durch 4 teilbar. Wenn es geht, braucht man 2 Bausteine. Es geht aber trotzdem nicht. Jeder Baustein ragt, egal, wie man ihn legt, über das Brett hinaus.

Hast du das bis hierhin verstanden?

tmo hat nun angedeutet, wie du aus einer Überdeckung eines Brettes mit einer bestimmten Seitenlänge eine Überdeckung eines Brettes mit der doppelten Seitenlänge konstruieren kannst. Er hat es dir überlassen, die Details des Rezepts herauszufinden und das mache ich auch. Es ist nicht schwer.

Wenn du dieses Rezept gefunden bzw. verstanden hast, kannst du aus einer Überdeckung des 2x2-Bretts eine Überdeckung des 4x4-Bretts und daraus eine Überdeckung des 8x8-Bretts usw. konstruieren. Damit hast du die Aufgabe gelöst. Der Nachweis der Teilbarkeit ist darin implizit enthalten. Das musst du dann nicht mehr separat zeigen. Und die Überdeckbarkeit des 2x2-Bretts ist ja trivial

Neue Frage »

Antworten »

Schachbrett mit der Seitenlänge 2^n - Beweis mittels Vollständiger Induktion?

Verwandte Themen