Gegeben ist ein weißes Quadrat mit Seitenlange 2^k, k element |N,
das mit einem Einheitsgitter uberdeckt ist (wie ein Schachbrett
ohne schwarze Felder). Genau ein beliebiges der Einheitskastchen im Gitter ist schwarz gefarbt.
Beweist, dass es immer moglich ist, die weiße Flache des
Quadrats mit roten L-formigen Steinen wie im Bild luckenlos
und uberlappungsfrei zu uberdecken. Die Steine durfen auch
gedreht werden.
(das bild ist ein quadrat , und das quadrat ist in 4 kleinen gleichen quadraten geteilt, 2 oben , 2 unten, und das quadrat unten recht ist schwarz gefärbt und die drei anderen formen ein L und sind rot gefärbt
wie kann ich das beweisen ?
danke
Indunktionsanfang: Für 2^1 ist es offensichtlich möglich.
Induktionsschritt: Angenommen, es ist für 2^k möglich. Dann kann man ein Quadrat mit der Seitenlänge 2^(k+1) in vier Quadrate mit einer Seitenlänge von 2^k zerlegen. Eines dieser kleineren Quadrate enthält das schwarze Kästchen, es lässt sich also mit Ls füllen. Von den anderen drei kleineren Quadraten nimmt man je ein Kästchen an einer Ecke weg, und zwar so, das diese drei Kästchen zusammen wieder ein L ergeben. Den drei kleineren Quadraten fehlt dann auch jeweils ein Kästchen, sie sind also gemäß Annahme füllbar. Damit ist auch das Quadrat mit der Seitenlänge 2^(k+1) füllbar.