Schachbrett mit L-Stücken < Abbildungen < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:05 Di 25.11.2008 | | Autor: | RyogaH |
| Aufgabe | Zeigen Sie, dass sich für jedes n [mm] \in \IN [/mm] ein [mm] 2^{n} [/mm] x [mm] 2^{n}-Schachbrett
[/mm]
derart mit L-Stücken, die so groß sind wie drei Felder des Schachbretts, überdeckungsfrei belegen lassen, dass einzig und allein die rechte obere Ecke frei bleibt. |
Hallo an alle hier im Matheraum, ich hoffe ich habe alles richtig gemacht für diesen Post!
Hier nun mein Problem...
Ich habe ziemlich sicher eine rekursive Funktion gefunden die, genau sagt wie viele L-Stücke je nach wahl des n gebraucht werden um die Bedingung zu erfüllen und nur noch ein Feld frei bleibt:
Eine Abbildung f: [mm] \IN \to \IN [/mm] n [mm] \mapsto [/mm] f(n) sei rekursiv definiert als
[mm] f(n)=2^{2 \* (n - 1)} [/mm] + f(n-1)
Wie kann könnte ich die obere rechte Ecke als freies Feld bestimmten und
es ist laut meinem Tutor auch notwendig, das ganze mit einer vollständigen Induktion zu beweisen. Aber irgendwie will das nicht so recht...
Ich weis zwar dass f(n) [mm] \* [/mm] 3 + 1 = [mm] 2^{n} \* 2^{n} [/mm] gelten sollte,
aber ich komm da einfach net weiter.
Ich hoffe wirklich dass mir ein paar Ansätze oder Tipps weiterhelfen...
Vielen dank im Vorraus!
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Das ist recht einfach zu lösen.
Für den Fall n=1 geht das ja ohne Mühe: 1 L-Stück.
Für n=2 kommen nun sozusagen 3 Quadrate der Größe [mm] 2^1*2^1 [/mm] dazu und bilden mit dem schon vorhandenen ein Quadrat der Größe [mm] 2^2*2^2. [/mm] Dabei liegt die linke untere Ecke des ursprünglichen 2*2-Quadrats genau in der Mitte des neuen Quadrats mit doppelter Kantenlänge.
Die drei "neuen" Quadrate werden nun mit Kopien des "ursprünglichen" Quadrats belegt. Das linke obere bekommt ein um 90° nach rechts gedrehte Kopie, das rechte untere eine um 90° nach links gedrehte, und das linke untere eine nicht gedrehte, also nur verschobene Kopie des ursprünglichen.
So bleiben nun drei Felder "in der Mitte" frei, genau in Form des L.
Die Methode führt allgemein von [mm] \a{}n [/mm] zu [mm] \a{}n+1.
[/mm]
Die Zahl der benötigten L-Stücke ist von [mm] \a{}n [/mm] abhängig und sei [mm] \a{}L(n). [/mm] Dann gilt [mm] \a{}L(1)=1 [/mm] und [mm] \a{}L(n+1)=4*L(n)+1
[/mm]
Vergleich das mal mit Deiner Funktion und versuch, eine explizite Form von [mm] \a{}L(n) [/mm] zu finden. Du hast sogar schon beschrieben, welche Bedingung sie erfüllen muss, daraus kannst Du sie auch herleiten.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:41 Di 25.11.2008 | | Autor: | RyogaH |
Erstmal, vielen dank für die schnelle Antwort!
Ich verstehe wie du auf deine Funktion gekommen bist, nur frag ich mich nun:
ist diese denn so ähnlich zu meiner möglichen Funktion?
Ich sehe zwar dass es ähnlichkeiten gibt und die Ergebnisse die selben sind, aber irgendwie ist nichts konkretes zu erkennen für mich...
Aber soviel steht fest, mit deiner Funktion würde ich jetzt klar kommen für Beweis und Beschreibung, ich möchte jetzt nur wissen, in wiefern die Funktionen zueinander in verbindung stehen, damit ich mir ein Bild machen kann.
Vielen Dank nochmal und im vorraus!
|
|
|
| |
|
Ich wollte nur zeigen, wie man auf die Funktion kommt und wie man die vollständige Bedeckung mit einer freien Ecke durchgängig rekursiv konstruieren kann.
Dein Ansatz war von Anfang an richtig. Ich habe bewusst den Schritt von [mm] f_n [/mm] zu [mm] f_{n+1} [/mm] gemacht, damit es anders aussieht als bei Dir, wo der Schritt von [mm] f_{n-1} [/mm] zu [mm] f_n [/mm] ging.
Nun sieht es ja aus, als hätten wir ganz unterschiedliche Rekursionsvorschriften, aber Du hast schon gesehen, dass die Ergebnisse gleich sind. Die Äquivalenz der Aussagen lässt sich trotzdem ohne Induktion zeigen:
[mm] f_n=2^{2(n-1)}+f_{n-1}=4f_{n-1}+1 \Rightarrow f_{n-1}=\bruch{1}{3}*(2^{2(n-1)}-1)
[/mm]
Zum Vergleich Deine explizite Form: [mm] f_{n-1}*3+1=2^{n-1}*2^{n-1}
[/mm]
Das lässt nun auch umformen zu [mm] f_{n-1}=\bruch{1}{3}*(2^{2(n-1)}-1)
[/mm]
Ja, unsere Aussagen sind äquivalent.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:42 Di 25.11.2008 | | Autor: | RyogaH |
Okay jetzt ist es mir klar ... da hätt ich auch drauf kommen können ...
Für mich ist die Frage damit eigentlich beantwortet, es hängt jetzt nur noch aus interesse für die Umformung, wie ich von meiner Funktion zu deiner komme. Aber das schau ich jetzt einfach mal.
Ansonsten, vielen Dank für die Antwort!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:53 Di 25.11.2008 | | Autor: | felixf |
Hallo
> Das ist recht einfach zu lösen.
> [...]
> So bleiben nun drei Felder "in der Mitte" frei, genau in
> Form des L.
Genau.
> Die Methode führt allgemein von [mm]\a{}n[/mm] zu [mm]\a{}n+1.[/mm]
> Die Zahl der benötigten L-Stücke ist von [mm]\a{}n[/mm] abhängig
> und sei [mm]\a{}L(n).[/mm] Dann gilt [mm]\a{}L(1)=1[/mm] und
> [mm]\a{}L(n+1)=4*L(n)+1[/mm]
>
> Vergleich das mal mit Deiner Funktion und versuch, eine
> explizite Form von [mm]\a{}L(n)[/mm] zu finden. Du hast sogar schon
> beschrieben, welche Bedingung sie erfüllen muss, daraus
> kannst Du sie auch herleiten.
Fuer [mm] $\a{}L(n)$ [/mm] kann man auch sehr einfach eine explizite Formel finden, wenn man folgendes beachtet:
- Es sind [mm] $(2^n)^2 [/mm] - 1$ Felder durch L-Stuecke belegt.
- Die L-Stuecke ueberdecken sich nicht.
- Jedes L-Stueck bedeckt 3 Felder.
LG Felix
|
|
|
|
