Schachbrett abdecken(L-Steine) < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Gegeben sei ein Schachbrett der Größe [mm] 2^n \times 2^n [/mm], aus dem ein beliebiges Feld entfernt wurde. Beweisen Sie, dass sich ein solches Brett ohne Lücken und ohne Überlappung mit L-förmigen Steinen, die jeweils drei Felder bedecken, überdecken lässt.
Anleitung: Zeigen Sie die Behauptung per vollständiger Induktion. Führen Sie dazu eine geeignete Nummerierung der Felder (analog zur Matrixschreibweise) ein, und betrachten Sie die Zerlegung des Bretts in vier gleichgroße Teile. Zeigen Sie, dass sich bei geeigneter Wahl des "ersten" L-Steins des Induktionsprinzip anwenden lässt. |
Hallo zusammen,
ich komme mit der Aufgabe nicht ganz klar und bräuchte zumindest mal einen vernüftigen Ansatz.
Mir ist an sich klar, dass das für [mm] n = 1 [/mm] also einem 2x2-Brett funktioniert. Auch bei einem 4x4-Brett kann ich mir das vorstellen. Aber bei einem 8x8-Brett fehlt mir noch komplett ein Ansatz, wenn dass fehlende Feld irgendwo ist (für die 4 Ecken klappt das gedanklich schon noch).
Ich kann auch mit dem Hinweis, dass Brett i 4 gleichgroße Teile zu teilen nicht viel anfangen. Theoretisch würde ich sagen, dass eine Einteilung Sinn macht, wenn das fehlende Feld in der Mitte des Bretts ist. Dann kann ich das bei einem 8x8-Brett so konstruieren, dass an Ende ein L-Stein in der Mitte das Brett komplettiert.
Generell sehe ich noch keinen Weg Struktur in das Problem zu bringen. Kann mir jemand auf die Sprünge helfen?
LG fagottator
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:36 Fr 08.04.2011 | | Autor: | abakus |
> Gegeben sei ein Schachbrett der Größe [mm]2^n \times 2^n [/mm],
> aus dem ein beliebiges Feld entfernt wurde. Beweisen Sie,
> dass sich ein solches Brett ohne Lücken und ohne
> Überlappung mit L-förmigen Steinen, die jeweils drei
> Felder bedecken, überdecken lässt.
>
> Anleitung: Zeigen Sie die Behauptung per vollständiger
> Induktion. Führen Sie dazu eine geeignete Nummerierung der
> Felder (analog zur Matrixschreibweise) ein, und betrachten
> Sie die Zerlegung des Bretts in vier gleichgroße Teile.
> Zeigen Sie, dass sich bei geeigneter Wahl des "ersten"
> L-Steins des Induktionsprinzip anwenden lässt.
> Hallo zusammen,
>
> ich komme mit der Aufgabe nicht ganz klar und bräuchte
> zumindest mal einen vernüftigen Ansatz.
>
> Mir ist an sich klar, dass das für [mm]n = 1[/mm] also einem
> 2x2-Brett funktioniert. Auch bei einem 4x4-Brett kann ich
> mir das vorstellen. Aber bei einem 8x8-Brett fehlt mir noch
> komplett ein Ansatz, wenn dass fehlende Feld irgendwo ist
> (für die 4 Ecken klappt das gedanklich schon noch).
> Ich kann auch mit dem Hinweis, dass Brett i 4 gleichgroße
> Teile zu teilen nicht viel anfangen. Theoretisch würde ich
> sagen, dass eine Einteilung Sinn macht, wenn das fehlende
> Feld in der Mitte des Bretts ist. Dann kann ich das bei
> einem 8x8-Brett so konstruieren, dass an Ende ein L-Stein
> in der Mitte das Brett komplettiert.
>
> Generell sehe ich noch keinen Weg Struktur in das Problem
> zu bringen. Kann mir jemand auf die Sprünge helfen?
Hallo,
da es eine gerade Anzahl von Zeilen und Spalten ist, liegt die Lücke nie "genau in der Mitte", sondern in einem der 4 Viertel.
Wenn du die Aufgabe für [mm] 2^n [/mm] lösen konntest, so kannst du sie auch für 2^(n+1) lösen, wenn du das 2^(n+1)-Feld viertelst. Die Lücke ist dann in einen [mm] 2^n-Feld [/mm] (welches zerlegt werden konnte), und du muss nur noch zeigen, dass das restliche Drei-Viertel-Feld immer darstellbar ist.
Gruß Abakus
>
> LG fagottator
|
|
|
| |
|
> Hallo,
> da es eine gerade Anzahl von Zeilen und Spalten ist, liegt
> die Lücke nie "genau in der Mitte", sondern in einem der 4
> Viertel.
Ja, ich hab mich da ein wenig doof ausgedrückt... Ich meinte den Fall, dass die Lücke in einem der mittleren vier Felder liegt. Dann könnte ich alle Viertel so konstruieren, dass in einer Ecke jeweils ein Feld fehlt. Wenn ich die Viertel dann zusammensetze kann ich einen L-Stein ergänzen und behalte das freie Feld übrig.
> Wenn du die Aufgabe für [mm]2^n[/mm] lösen konntest, so kannst du
> sie auch für 2^(n+1) lösen, wenn du das 2^(n+1)-Feld
> viertelst. Die Lücke ist dann in einen [mm]2^n-Feld[/mm] (welches
> zerlegt werden konnte), und du muss nur noch zeigen, dass
> das restliche Drei-Viertel-Feld immer darstellbar ist.
Mir ist schon klar, wie Induktion generell funktioniert, aber ich habe ja noch keinen brauchbaren Ansatz, wie ich die Situation mathematisch erfassen soll. Kann ich bei teilen des Schachbretts die oben geschilderte Situation konstruieren? Was muss ich überhaupt zeigen?!? Ich meine ich kann ja aufzeichnen, dass das für ein 2x2-Brett klappt, aber wie soll ich daraus eine Induktionsvoraussetzung machen, die ich dann im Induktionsschritt verwende? Ich kann ja schlecht sagen "Das hat für [mm] 2^n \times 2^n [/mm] funktioniert und wenn ich das [mm] 2^{n+1} \times 2^{n+1} [/mm]-Brett in Viertel aufteile erhalte ich ja wieder vier 2x2-Bretter, also klappt dass auch für n+1"...
> Gruß Abakus
LG fagottator
|
|
|
| |
|
Hallo fagottator,
es genügt, wenn Du eine Zerlegung eines 4*4-Brett zeigst, aus dem ein Viertel herausgeschnitten ist. Wenn du die restlichen 12 Felder (die sozusagen ein "großes L" bilden) in vier "kleine L" zerlegen kannst, schaffst Du auch die gesamte Induktion, denn das ist der eigentliche Induktionsschritt.
Grüße
reverend
PS: Die Aufgabe gehört zu den Klassikern der mathematischen Denksportaufgaben und findet sich m.W. schon bei einem ihrer Pioniere, Sam Lloyd.
|
|
|
|
