Überdeckung Schachbrett

28.11.2021, 16:02	DanielZirpel	Auf diesen Beitrag antworten »
Überdeckung Schachbrett Meine Frage: Gegeben ist ein Schachbrett der Größe (2^n) x (2^n) (n ? ?, n ? 1, aus dem ein beliebiges Einzelfeld entfernt wurde. Beweisen Sie mit vollständiger Induktion, dass ein solches Schachbrett mit Hilfe von L-Formen (bestehend aus drei Einzelfeldern) ohne Lücken oder Überlappungen überdeckt werden kann. Meine Ideen: Also nahm ich ein 2n×2n Schachbrett und entfernte eines der Felder. Ich teilte das Schachbrett mit einer vertikalen und einer horizontalen Linie in Viertel auf. An dieser Stelle würde ich mich freuen, wenn die Lösung und ihre Antwort geklärt wären. Danke!
28.11.2021, 16:24	HAL 9000	Auf diesen Beitrag antworten »
Induktionsschritt $\begin{eqnarray} n\to n+1 \end{eqnarray}$ : Wir zerteilen das Gesamt-Schachtbrett $\begin{eqnarray} 2^{n+1}\times 2^{n+1} \end{eqnarray}$ in $\begin{eqnarray} 2\cdot 2 = 4 \end{eqnarray}$ Schachbretter der Größe $\begin{eqnarray} 2^n\times 2^n \end{eqnarray}$ . In genau einem dieser vier Bretter liegt das eine fehlende Feld. Von den anderen drei Brettern entfernen wir zunächst dasjenige Eckfeld, was dem Zentrum des Gesamtbrettes am nächsten liegt. Nun wenden wir auf all diese vier Teilbretter mit jeweils einem fehlenden Feld die Induktionsvoraussetzung an ... Klar, wie es weiter geht?

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »