Trominos durch Teilen und Herrschen

Ein L-Tromino bedeckt drei Felder in L-Form. Jedes $2^n \times 2^n$-Brett mit einem entfernten Feld lässt sich mit L-Trominos parkettieren. Der Beweis ist Teilen und Herrschen: teile in vier Viertel, lege ein Tromino in die Mitte über die drei Viertel ohne Loch, und jedes Viertel ist wieder ein kleineres Brett mit einem Loch.

Die Flächenzählung prüft die Möglichkeit: $4^n - 1$ ist durch $3$ teilbar, weil $4 \equiv 1 \pmod 3$ gilt. Danach liefert die Rekursion die tatsächliche Konstruktion.