Anzahl an Möglichkeiten, Steine zu pflastern

Question

Aufgabe: Es sei an die Anzahl an Möglichkeiten, ein Feld der Größe 3 × n mit Steinen der Größe 1 × 3 zu pflastern.
Pflastern meint dabei, das Feld vollständig zu bedecken, ohne das ein Stein über das Feld hinaus ragt. Die
Steine können gedreht werden.

i) Geben Sie ai, i = 1, . . . 5, an.

ii) Geben Sie einen rekursiven Ausdruck für an, inklusive Startwert(e), an und beweisen Sie ihn.

Problem/Ansatz: Wie gehe ich hier vor?

Liebe Grüße

Answer 1

Wie gehe ich hier vor?

zu i)

Gib die Anzahl der Möglichkeiten an,

- ein 3x1-Feld zu pflastern

- ein 3x2-Feld zu pflastern

- ein 3x3-Feld zu pflastern

- ein 3x4-Feld zu pflastern

- ein 3x5-Feld zu pflastern

Comments

Gib die Anzahl der Möglichkeiten an,

Und solltest du das eventuell nicht schaffen. Und du darfst es dir dazu auch aufzeichnen, dann gib eventuell an wobei du hier Probleme hast.

---

Ich habe schon Probleme, überhaupt auf die Möglichkeiten von @abakus zu kommen.

Also ich setze für n einfach mal 1,2,3,4,5.

Beim 3x1 Feld wäre das ja dann genau eine Möglichkeit, oder? da 3x1 = 1 x 3.

Oder denke ich falsch?

---

Ja, da gibt es genau eine Möglichkeit.

---

Und dann bei 3x2 gäbe es dann wie viele? 3 * 2 = 6, Stein ist 1*3 = 3, also 2 Möglichkeiten?

Und dann beim dritten 3x3 = 9, also 3 Möglichkeiten.

Also an = an-1 + an-2 ?

---

Bei einem 3x2 Feld brauchst du zwar 2 Steine, du hast aber nur eine Möglichkeit diese anzuordnen (die Steine sind nicht unterscheidbar). Also \(a_1=a_2=1\). Erst in einem 3x3 Feld hast du genug Platz, Steine zu drehen, so dass du mehr als eine Möglichkeit bekommst.

---

Ich Packe mal meine Legosteinchen aus. Was denkst du wieviel Möglichkeiten du hast die 2 1x3 Steine auf der 2x3 Platte zu platzieren. Du kannst die Steine nicht voneinander unterscheiden. Ich denke es gibt da nur eine Möglichkeit. Man platziert die beiden Steine einfach parallel nebeneinander auf der Platte. Aber vielleicht siehst du noch eine andere Möglichkeit.

Wenn du das verstanden hast nimmst du 3 1x3 Steine und dafür eine 3x3 Platte. Wie viele Möglichkeiten hat man dann.

Ich gebe zu, das ist etwas trickreich, wenn man es nur virtuell ohne richtige Steine machen soll. Da braucht man schon extrem gute Vorstellungskraft.

---

Und wenn man jetzt 4 1x3 Steine auf einer 3x4 Platte platzieren möchte, dann könnte man sie auch alle parallel und nebeneinander platzieren. Das ist jetzt aber denke ich nicht die einzige Möglichkeit. Welche Möglichkeiten gibt es noch und wie viele gibt es insgesamt?

---

Bei 3 1x3 Steinen und einer 3x3 Platte, dann gibt es 6 Möglichkeiten (3+3).

Und bei 4 1x3 Steinen auf einer 3x4 Platte, da gibt es nur 3 Möglichkeiten, oder? Entweder alle parallel, oder drei vertikal parallel und eins horizontal oben drauf, oder drei vertikal parallel und eins horizontal drunter.

---

Bei einem 3x3 großem Feld gibt es 2 Möglichkeiten: entweder alle Steine waagerecht oder alle Steine senkrecht platzieren. Es gibt zwar 6 mögliche Positionen für einen Stein, danach ist aber nicht gefragt.

---

Und bei 4 1x3 Steinen auf einer 3x4 Platte, da gibt es nur 3 Möglichkeiten, oder? Entweder alle parallel, oder drei vertikal parallel und eins horizontal oben drauf, oder drei vertikal parallel und eins horizontal drunter.

Das hast du völlig richtig analysiert. Ich wundere mich das es dir nicht ganz bei 3 Steinen geglückt ist. Denn hier hast du ja auch analysiert das 3 Steine parallel angeordnet werden und zwar entweder horizontal oder vertikal. Also nur 2 Möglichkeiten und nicht zweimal 3 Möglichkeiten.

---

Stimmt.

Bei 1 1x3 Stein und einer 1x3 Platte, gibt es ja auch nur genau eine Möglichkeit, also a₁ = 1.

Bei 2 1x3 Steinen und einer 2x3 Platte, da gibt es nur eine Möglichkeit, also a2 = 1.

Wenn es bei 3 1x3 Steinen und einer 3x3 Platte genau 2 Möglichkeiten gibt, nämlich horizontal parallel und vertikal parallel, dann gilt ja a_{3 = 2.}

Bei 4 1x3 Steinen und einer 4x3 Platte, da gibt es dann wie gesagt die 3 Möglichkeiten, nämlich einmal alle parallel, einmal 3 parallel und einer oben, oder drei parallel und einer unten. Also a₄ = 3.

Bei 5 1x3 Steinen und einer 5x3 Platte, da gibt es genau 4 Möglichkeiten. Nämlich einmal alle parallel, einmal 3 von oben nach unten, und zwei links, einmal 3 von oben nahc unten und zwei rechts, einmal eins links, 3 parallel von oben nach unten in der mitte und eins rechts. Also a₅ = 4.

a₁ = 1

a₂ = 1
a₃ = 2

a₄ = 3

a₅ = 4

Jetzt muss ich noch einen rekursiven Ausdruck angeben.

a5 = 4 wäre ja z.B. a4 + a2.

a4 = 3 wäre a3 + a1

aber wie kommt man auf a3?