0 Daumen
417 Aufrufe

Aufgabe (L-Plättchen):

Beweisen Sie die folgenden Aussagen mittels vollständiger Induktion!

Das linke Bild zeigt ein \( 4 \times 4 \)-Gitter, bei dem ein Feld entfernt wurde, und das rechte Feld zeigt eine Abdeckung dieses Gitters mit L-Plättchen, die in verschiedenen Farben dargestellt wurden. Ein L-Plättchen deckt drei Felder auf die angegebene Art ab. Die Farbe spielt keine Rolle.

blob.png

Für jedes \( n \in \mathbb{N} \) gilt: jedes \( 2^{n} \times 2^{n} \)-Gitter, bei dem ein beliebiges Feld entfernt wurde, kann mit L-Plättchen abgedeckt werden, so dass jedes Feld von genau einem L-Plättchen abgedeckt wird.

Avatar von

1 Antwort

0 Daumen

Zu der Aufgabe mit den L-Plättchen:

Induktionsanfang: n=1: Egal, welches der 4-Eckfelder fehlt, die anderen 3 bilden ein L.

Induktionsschritt n->n+1

Induktionannahme: Die Aussage gilt für n

Induktionsbehauptung: Dann gilt sie auch für n+1

Beweis: Wir zerlegen das 2^{n+1}*2^{n+1} Quadrat in vier (2^n)*(2^n) Quardrate (jeweils das links untere, rechts untere, links obere, rechts obere). In einem davon fehlt ein Quadrat, dieses lässt sich also nach Induktionsannahme vollständig mit Ls pflastern. Nun zu den drei übrigen Quadraten: alle vier große Teil-Quadrate stoßen aufeinander in der Mitte des 2^{n1}*2^{n+1} Quadrat. Wir tun so, als würden bei den übrigen drei Quadraten auch ein 1x1 Quadrat fehlen, nämlich dasjenige, was an diesen Berührpunkt dieser vier großen Quadrate stößt mit einer Ecke. Diese 3 1x1 Quadrate bilden ein L. Die übrigen 3 großen Quadrate wurden so um je ein 1x1 Quadrat reduziert, sodass auch diese sich nach Induktionsannahme pflastern lassen. Zudem  überlappen sich keine zwei L (da sie vollständig in disjunkten Quadraten liegen) Dies schließt den Beweis ab. qed

Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community