Vollständige Induktion Schachbrett

Question

Aufgabe:

Gegeben ist ein Schachbrett der Größe 2^n ×2^n, 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.

Problem/Ansatz:

$$\forall n \in \mathbb{N}, n \geq 1 : 2^{n}\cdot 2^{n} - 1 = \frac{2^{n+1}\cdot2^{n+1}-4}{4}$$ : war die Idee, weiß aber nicht ob das bis dahin stimmt.

Answer 1

Deine Gleichung stimmt, nützt dir aber wahrscheinlich nichts. Wenn du nur theoretisch mit Formeln den Induktionsbeweis führst, heißt das noch nicht, dass die Überdeckung auch gelingt.

Beginne zeichnerisch mit einem 2×2-Feld und überlege dann, wie man ein 4×4-Feld überdecken könnte, in dem ein 2×2-Feld bereits bedeckt ist. Dann bekommst du vielleicht eine Beweisidee.

Hier eine Anregung: