Beweisen Sie die Aussagen mittels vollständiger Induktion (Induktionsbeweis über natürliche Zahlen, L-Plättchen)

Question

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.

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.

Answer 1

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