0 Daumen
816 Aufrufe

Aufgabe:

Lösen Sie folgendes Problem rekursiv: Auf wie viele Arten
kann man ein Rechteck der Größe 2 x n mit Dominosteinen der Größe 1 x 2
pflastern? Unter „pflastern“ ist dabei Folgendes zu verstehen: Das Rechteck soll so
bedeckt werden, dass sich keine zwei Dominosteine überlappen und sie nicht über
den Rand hinausragen.


Problem/Ansatz:

Hallo,

ist meine Lösung im Anhang so richtig?

Liebe GrüßeWhatsApp Image 2022-02-17 at 13.43.27.jpeg

Avatar von

Werden zwei Pflasterungen unterschieden, wenn sich die Lage der Dominosteine ändert:

blob.png

Sind alle Dominosteine verschieden?

Wie meinst du das? Ich glaube, es geht nur darum, Rechteck 2 x n auszufüllen mit den Steinen, oder? Also wenn ich z.B. bei n = 3 die erste Möglichkeit betrachte, ist es egal, ob sie auf dem Kopf stehen oder gerade, es ist trotztdem nur "eine" Möglichkeit. So verstand ich es zumindest.

3 Antworten

0 Daumen
 
Beste Antwort

Für n=4 gibt es 5 Möglichkeiten!

Du kannst entweder

an die Möglichkeiten für n=3 waagerecht anlegen

oder

an die Möglichkeiten für n=3 einen Stein hochkant anlegen.

Avatar von 55 k 🚀

Wie meinst du das? Wie sieht die 5. Möglichkeit denn aus? Durch anlegen auf n=3 würden doch keine Rechtecke rauskommen, außer wenn ich vertikal anlege. Ich glaube du meinst an die zweite Möglichkeit für n = 3 kann ich von links vertikal anlegen.

Und dann wäre es die fibonacci folge.

0 Daumen

für n=4 gibt es diese Möglichkeiten:

blob.png

Avatar von 123 k 🚀
0 Daumen

Du sollst das Ganze rekursiv lösen und nicht irgendwelchen kombinatorischen Schwachsinn machen.

Um ein 7x2 zu bekommen, kannst Du entweder einen senkrecht an ein 6x2 anlegen, oder zwei waagrecht an ein 5x2 anlegen.

Nenne ein \( n \times 2\)-Rechteck \(a_n\). Dann gilt hier \( a_7 = a_6+a_5 \) und allgemein \( a_n = a_{n-1}+a_{n-2} \).

Und wie Du schon erkannt hast, ist das die Fibonacci-Folge.

Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community