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

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

von 114 k 🚀

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

1 Antwort
Gefragt 11 Dez 2015 von Gast
1 Antwort
5 Antworten

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community