0 Daumen
957 Aufrufe

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.

Avatar von

1 Antwort

+1 Daumen

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:

blob.png

Avatar von 123 k 🚀

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community