Kombinatorik - Schachbrett < Kombinatorik < Stochastik < Oberstufe < Schule < Mathe < Vorhilfe
|
| Aufgabe | | Zeigen Sie, dass such für jedes n [mm] \in [/mm] N ein [mm] 2^{n} [/mm] x [mm] 2^{n} [/mm] - Schachbrett überdeckungsfrei durch L-Stücke belegen lässt, so dass einzig und allein das Feld in der rechten oberen Ecke frei bleibt. Die L-Stücke sollen dabei so groß wie drei Felder des Schachbretts sein. |
Ich bin ratlos wie ich an die Aufgabe herantreten soll...
Beispiel n=1
Dann ist das Schachfeld ja 4 Kästchen groß und das L passt einmal rein.
Ist das L dann 2 x 1 ?
2 x 1 | [mm] 2^{n} [/mm] x [mm] 2^{n} [/mm] - 1
Bitte um Denkanstöße bzw. Lösungsansatz.
MFG
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
moin Grischa,
Ich würde dir raten es mit Rechtecken zu versuchen.
Du kannst etwa indem du zwei L nebeneinander legst ein 3x2-Rechteck zulegen.
Auf diese Art (und vielleicht noch mit anderen Rechtecken) kannst du dein Problem auf ein kleineres zurückführen, also wenn du etwa ein 32x32-Schachbrett hast kannst du mit den 3x2-Rechtecken schonmal ein 30x32-Feld voll legen, dann ist (oBdA) oben noch ein 2x32 Streifen übrig, davon kann man mit den 3x2-Rechtecken auch nochmal einen 2x30 voll legen, bleibt also nur (oBdA oben rechts) ein 2x2 Feld übrig; da ein L draufzulegen so dass die obere rechte Ecke frei bleibt dürftest du schaffen. ;)
Du müsstest jetzt nur noch zeigen, dass sich für alle $n [mm] \in \IN$ [/mm] ein Feld auf diese Art zumauern lässt (oder auch mit anderen Rechtecken, das sei dir überlassen).
lg
Schadow
|
|
|
|
