Dominosteine < Kombinatorik < Stochastik < Oberstufe < Schule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:13 Sa 26.11.2011 | | Autor: | Blubie |
| Aufgabe | Gegeben sei ein 3 x n-Rechteck, das wir vollständig mit 2 x 1-Dominosteinen belegen.
Sei [mm] A_{n} [/mm] die Anzahl der verschiedenen Belegungen (also z.B. [mm] A_{0} [/mm] = 1, [mm] A_{1} [/mm] = 0, [mm] A_{n} [/mm] = 3).
Sei [mm] B_{n} [/mm] die Anzahl der Belegungen, in denen genau die linke obere Ecke frei bleibt (also
[mm] B_{0} [/mm] = 0, [mm] B_{1} [/mm] = 1, [mm] B_{2} [/mm] = 0). Stelle Rekursionen für [mm] A_{n}, B_{n} [/mm] auf. |
Also, ich habe jetzt schon mindestens 10 din-a4 seiten mit skizzen voll gemacht aber komme immer noch nicht auf die korrekte lösung.
Für F(4) gibt es 11 Möglichkeiten und für F(6) = 41, wenn ich mich nicht vertan habe. Ich bin nun für [mm] A_{n} [/mm] auf die Gleeichung F(n) = F(n-2) + 2 gekommen, bin mir da aber nicht so richtig sicher.
Kann mir jemand auf die Sprünge helfen?
Danke und viele Grüße
|
|
| |
|
Hallo Blubie,
da stimmen Angaben nicht. Vielleicht verstehe ich die Aufgabe deswegen nicht ganz.
> Gegeben sei ein 3 x n-Rechteck, das wir vollständig mit 2
> x 1-Dominosteinen belegen.
"Vollständig"? Bei ungeradem n ist ja keine vollständige Belegung möglich, wie die weitere Aufgabe ja auch voraussetzt. Soll das also heißen, dass eben kein Platz mehr für einen weiteren Dominostein bleibt? Wenn ja, dann muss immer noch geklärt werden, ob freie Einzelfelder erlaubt sind.
Das ist nicht anzunehmen, aber eben schlecht formuliert. Ich deute "vollständig" also als wirklich vollständig bei geradem n, und bei ungeradem n als "so dass genau ein Feld freibleibt".
> Sei [mm]A_{n}[/mm] die Anzahl der verschiedenen Belegungen (also
> z.B. [mm]A_{0}[/mm] = 1, [mm]A_{1}[/mm] = 0, [mm]A_{n}[/mm] = 3).
Müsste das nicht [mm] A_0=\blue{0}, A_1=\blue{2}, A_{\blue{2}}=3 [/mm] heißen?
> Sei [mm]B_{n}[/mm] die Anzahl der Belegungen, in denen genau die
> linke obere Ecke frei bleibt (also
> [mm]B_{0}[/mm] = 0, [mm]B_{1}[/mm] = 1, [mm]B_{2}[/mm] = 0).
Diese Zahlen stimmen dagegen.
> Stelle Rekursionen für
> [mm]A_{n}, B_{n}[/mm] auf.
> Also, ich habe jetzt schon mindestens 10 din-a4 seiten mit
> skizzen voll gemacht aber komme immer noch nicht auf die
> korrekte lösung.
>
> Für F(4) gibt es 11 Möglichkeiten und für F(6) = 41,
Das sind [mm] A_4 [/mm] und [mm] A_6 [/mm] ? [mm] A_4=11 [/mm] kann ich bestätigen, [mm] A_6 [/mm] habe ich nicht versucht.
> wenn ich mich nicht vertan habe. Ich bin nun für [mm]A_{n}[/mm] auf
> die Gleeichung F(n) = F(n-2) + 2 gekommen, bin mir da aber
> nicht so richtig sicher.
Viel zu wenig. Da ja schon [mm] A_2=3 [/mm] ist, muss [mm] F_n\ge F_{n-2}\blue{*A_2}=3F_{n-2} [/mm] sein.
Gleichheit wäre gegeben, wen man z.B. die linken n-2 Spalten mit den bisherigen [mm] F_{n-2} [/mm] Möglichkeiten belegt. Dann hat man für die restlichen beiden Spalten eben noch [mm] F_2 [/mm] Möglichkeiten.
Hinzu kommen nun noch die Lösungen, bei denen mindestens ein Stein die Grenze zwischen der (n-2)ten und der (n-1)ten Spalte überschreitet.
Im übrigen scheint mir eine Zweischritt-Rekursion zwar einfacher, aber womöglich nicht im Sinn des Aufgabenstellers. Du kannst trotzdem so anfangen, dann kann man ja immer noch mal sehen, ob man nicht eine einschrittige Rekursion daraus bauen kann.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:29 So 27.11.2011 | | Autor: | Blubie |
Mit F meinte ich A, das stimmt.
[mm] A_{0} [/mm] = 1 stimmt. Es gibt genau eine Möglichkeit ein leeres Feld vollständig zu füllen, nämlich genau dann, wenn man keine Steine nimmt. Ja, für A braucht man nur gerade und für B nur ungerade Steine zu betrachten.
Allerdings komme ich immer noch nicht weiter
|
|
|
| |
|
Hallo Blubie,
ich habe auch nochmal über die Aufgabe nachgedacht.
Es gilt [mm] A_n=0 [/mm] für ungerades n, weil dann keine vollständige Belegung möglich ist.
Es gilt auch [mm] B_n=0 [/mm] für gerades n, weil dann keine Belegung möglich ist, so dass die linke obere Ecke frei bleibt.
Schauen wir uns nun die beiden möglichen Schritte an, nämlich von einem geraden n nach n+1, sowie von einem ungeraden n nach n+1. Wir fügen jeweils links eine neue 3er-Spalte hinzu.
[mm] A_0=1, B_1=1, A_2=3 [/mm] können wir ja voraussetzen.
Gehen wir nun allgemein von 2k nach 2k+1. Die vorher äußerste linke Spalte (#2k) kann drei verschiedene Gestalten haben:
Fall g1: sie wird von drei verschiedenen Dominosteinen (je zur Hälfte) belegt. Dann muss die neue linke Spalte (#2k+1) einen Dominostein enthalten, der auf den beiden unteren Feldern liegt. Damit sind die linken drei Spalten definiert, und für den Rest gibt es [mm] A_{2k-2} [/mm] Möglichkeiten.
Fall g2: ein kompletter Dominostein liegt in den beiden oberen Feldern von Spalte (#2k). Dann muss Spalte (#2k+1) wieder einen Stein auf den unteren Feldern haben; hier ist die Zahl der Möglichkeiten nicht so leicht zu bestimmen, lautet aber [mm] \tfrac{1}{2}(A_{2k}-A_{2k-2}). [/mm] Denk mal drüber nach.
Fall g3: ein kompletter Dominostein liegt in den beiden unteren Feldern von Spalte (#2k). Dann gibt es zwei Möglichkeiten der Erweiterung nach links, nämlich entweder wieder einen kompletten Stein senkrecht in Spalte (#2k+1), oder aber zwei "halbe" Steine in den unteren Feldern, wozu der bisherige Stein in (#2k) natürlich gedreht werden muss. Das gibt insgesamt [mm] (A_{2k}-A_{2k-2}) [/mm] Möglichkeiten, was Du leicht ermitteln kannst, wenn Du Fall g2 gelöst hast.
Damit ist [mm] B_{2k+1}=\tfrac{3}{2}A_{2k}-\tfrac{1}{2}A_{2k-2}
[/mm]
Jetzt versuch Du mal den Schritt von ungerade nach gerade. Der ist leichter.
Grüße
reverend
|
|
|
|
