Wie viele Möglichkeiten diese Steine zu einem solchen Mauerstück zusammenzusetzen?

Question

Hallo an alle :-)

Ich habe folgende Aufgabe:

Der Regierungschef eines nicht näher spezifizierten Landes möchte zum Bau einer Mauer an der Landesgrenze unterschiedliche Steine begutachten, nachdem seine Berater ihm mitteilen mussten, dass ein Wassergraben mit Krokodilen leider keine Option ist. Hierzu wurden ihm quaderförmige, gleich große Steine jeder Art mitgebracht und jeweils zu einem Mauerstück aufgebaut. Hierbei soll wie im Diagramm die unterste Reihe aus 9 Steinen bestehen, wobei jeder Stein, außer in der untersten Reihe, mittig auf genau 2 anderen Steinen stehen muss und die unterste Reihe keine Lücken haben
darf. Wir gehen davon aus, dass von jedem Steintypen genügend Steine für jedes der beschriebenen Mauerstücke vorhanden sind. Wie viele Möglichkeiten gibt es, für einen gegebenen Steintypen die Steine zu einem solchen Mauerstück zusammenzusetzen?

Ansatz / Problem :

Ich weiß nicht wie ich das hier angehen soll, aber dennoch habe ich mir etwas überlegt.

Wir wissen, dass es quaderförmige Steine gibt, die gleich groß sind, aber unterschiedliche Arten sind.

Die unterste Reihe der Mauer besteht aus 9 Steinen ohne Lücken und jeder stein der drauf kommt muss mittig auf 2 Steinen der untersten Reihe stehen. Jedoch sind dort die Lücken nicht wichtig (wie auf dem Bild).

Wenn ich es richtig verstanden habe, kann man es mit dem Urnenproblem möglicherweise lösen, also In dem falle Bälle (=Steine) nicht unterscheidbar, da gleich groß, aber die Urne (= jede Reihe der Mauer) unterscheidbar. Und dann Injektiv oder Surjektiv (Unsicher) Verteilt, weil jede 2 Steine einen weiteren Stein haben muss oder weil jede Reihe mind. haben muss.

Also wenn Injektiv dann Berechnung:  (m+n-1 über n) und wenn Surjektiv dann: (n-1 über m-1)

Frage:

Hab ich das richtig verstanden ?

für jede Hilfe :-)

EDIT: Nachtrag aus Kommentar:

Also ich habe soeben in einer Mail gesehen, dass gemeint ist, dass wir die Anzahl der Möglichkeiten für einen Mauertsück mit fester Anzahl von Steinen geben sollen und das wir anscheinend auf ein früheres Problem zurück greifen können ...  Was mir aber dabei nichts einfällt.

Falls jemand noch eine Idee hat, dann bitte diese stellen :))

Und an allen bedanke ich mich sehr für die Antworten :-)

Comments

Hallo

die Frage scheint eigenartig, weil da steht:"Wie viele Möglichkeiten gibt es, für einen gegebenen Steintypen" da sehe ich nur die eine Möglichkeit.

---

Ja stimmt, aber so wurde es uns gegeben, trotzdem ist denke ich gemeint " Wie viele Möglichkeiten gibt es, die gegeben Steinen zu einem solchen Mauerstück zusammenzusetzen?"

Aber wie gesagt, an sich verwirrt mich die Aufgabe :(

---

Ja genau, aber wie kann ich dennoch die Möglichkeiten berechnen? :)

---

Hallo

 da nicht mal gesagt ist ob es 20 oder 5 Sorten Stein gibt, und ob in einer Reihe nur eine Sorte stehen soll, ist für mich die Aufgabe entweder sinnlos. oder wegen des einen Steintyps einfach 1 oder 2 wenn man auch das Spiegelbild bauen darf.

woher stammt denn die Aufgabe, die hört sich wie geocauching an?

lul

---

Die Aufgabe ist ein Aufgabenteil meiner Hausaufgabe für die Uni -Diskrete Mathematik ... :( Und ich arbeite auch mit einer Gruppe zusammen, aber wir sind jetzt zu 3. sehr verwirrt weil wir die Frage auch komisch finden ... Dazu müssen wir dann am Ende unsere Lösung auch mathematisch Argumentieren, aber da keiner von uns eine richtige Lösung hat, wissen wir nicht was wir schreiben sollen.

Zudem ist die Hausaufgabe, wie jede andere auch, leider sehr wichtig :(

---

In der Angabe heißt es "jeweils" und daraus schließe ich, das jedes Mauerstück nur aus genau einer Sorte Steinen bestehen soll. Davon abgesehen geht es doch wohl nur um die Anzahl unterschiedlicher Mauerstückprofile, die nach den drei genannten Bildungsregeln möglich sind.

---

Wenn das so sein sollte dann wäre es ein leichtes dafür ein kurzes Programm zu schreiben um später die mathematischen Hintergründe zu überprüfen. So würde ich zumindest vorgehen.

---

(Ich denke auch, dass die Steine nicht unterscheidbar sind, weil sie die gleiche Größe haben, auch wenn Art anders ist (bsp Farbe des Steins). Dann aber, weil es in der Abbildung so ist, dachte ich dass die Reihen die Urnen darstellen falls ja, dann sind die Urnen/ Reihen unterschiedlich, weil man entweder Lücken haben kann oder nicht (laut Bild).

Falls es genau nach bild sein muss, dann haben wir ja 20 Steine und der erste Stein kann in der ersten Position 20! Möglichkeiten haben oder?)

Anders gesagt, ich bin sehr verzweifelt und verwirrt, weil ich nicht weiß, was genau von uns erwartet wird.

Und wie könnte man das Programm dazu schreiben ? Wir müssen das eigentlich auf Papier haben.

---

Allerdings eine merkwürdige Aufgabe.

Das sind oft die besten!

---

Es tut mir sehr leid, aber ich hab jetzt immer noch nicht verstanden, wie ich es zu verstehen habe und was ich jetzt machen soll ^^' .

---

Die Idee von az0815 ergibt eine spannendere Aufgabe.

Wenn du nicht zu viel tun willst, meldest du dich am besten mit den verschiedenen Ideen beim Fragesteller. Ansonsten verschiedene Varianten durchrechnen und jeweils erst mal deine Interpretation der Fragestellung erklären.

---

Also so wie ich es verstanden habe wird von uns verlangt, dass wir nach der Anzahl der Möglichkeiten für ein Mauerstück mit fester Anzahl von Steinen suchen. Jedoch weiß ich nicht, wie ich es jetzt rechnen soll, also ich bin mir nicht sicher ob ich das auf das Urnenmodell beziehen kann oder was anderes machen muss.

Kann man dies mit dem Schubfachprinzip lösen ?

---

Beweise  1134903170

Wer hat denn meinen Kommentar zu einer Antwort gemacht ?

Ich hoffe, dass derjenige auch tatsächlich einen Beweis liefern kann. Ich kann es nicht, denn die angegebene Anzahl bezog sich auf eine Interpretation der Fragestellung, die sich durch den Zusatz des Fragestellers als unzutreffend herausgestellt hat, wodurch mein Beitrag obsolet geworden ist und komplett gelöscht werden kann.

---

@mathe_was_sonst Achso, Okay jetzt verstehe ich es! :)

Also ich habe soeben in einer Mail gesehen, dass gemeint ist, dass wir die Anzahl der Möglichkeiten für einen Mauertsück mit fester Anzahl von Steinen geben sollen und das wir anscheinend auf ein früheres Problem zurück greifen können ...  Was mir aber dabei nichts einfällt.

Falls jemand noch eine Idee hat, dann bitte diese stellen :))

Und an allen bedanke ich mich sehr für die Antworten :-)

---

Ist das denn die Lösung, wenn ich fragen darf ? Weil ich bin jetzt richtig verwirrt hehe ....

---

Ich habe jetzt versucht die verschiedenen Ideen zu trennen, damit du einzeln das weiterdiskutieren kannst, was dir am plausibeltsten erscheint unter den neuen Voraussetzungen.

Falls ich etwas übersehen habe: Bitte einfach eine weitere Antwort schreiben.

---

Vielen Dank @Lu :-)

---

dass wir die Anzahl der Möglichkeiten für einen Mauertsück mit fester Anzahl von Steinen geben sollen

Da hast du meine Mail missverstanden - in der ersten Version des Blatts habe ich die Aufgabe fälschlicherweise zu schwer gestellt und nach der Anzahl von Möglichkeiten für eine feste Gesamtanzahl von 20 Steinen gefragt - hier hätte man nur eine Rekursionsgleichung aufstellen können, aber ihr lernt erst noch, wie man mit Rekursionsgleichungen und erzeugenden Funktionen umgeht und hättet keinen geschlossenen Ausdruck dafür angeben können. Die Änderung bedeutet, dass ihr jetzt stattdessen das Problem für eine feste Anzahl von Steinen in der unteren Reihe betrachten sollt, also genau die Version der Aufgabe, die du hier gepostet hast.

---

Vielen Dank @sorachan für deine Hilfe :-) Hab die Aufgabe heute verstanden und hoffe, dass es richtig ist ... :-)

Answer 1

Ich denke die Steine sind nicht unterscheidbar.

Eine weitere Möglichkeit wären also in der untersten Reihe 9 Steine und in jeder darauffolgenden Reihe ein Stein weniger. Das wäre dann auch gleichzeitig eine Mauer in der die maximale Anzahl an Steinen verbaut wird.

Dann würde man nach Gauss höchstens 45 Steine verbauen.

Bevor man das durchrechnet könnte man erst diskutieren ob das so gemeint sein könnte.

Comments

Ich denke, dass bis auf die unterste Reihe es Lücken geben darf. Bin mir natürlich nicht sicher, es wird von uns ja die Anzahl der Möglichkeiten für einen Mausterstück mit fester Anzahl von Steinen verlangt.

---

es wird von uns ja die Anzahl der Möglichkeiten für einen Mausterstück mit fester Anzahl von Steinen verlangt.

Wo steht, dass du es für eine feste Anzahl an Steinen machen sollst? Kam die Email vom Dozenten oder von jemandem aus deiner Gruppe?

---

Vom Übungsleiter, also ich vermute der , der die Aufgabe erstellt hat.

Anscheinend sollte die Frage genau das bedeuten, also die Anzahl der Möglichkeiten geben für einen Mauerstück mit fester Anzahl von Steinen.

---

Also für

10 Steine 8 Möglichkeiten.

11 Steine (8 über 2) = 28 Möglichkeiten

12 Steine 7 + (8 über 3) = 63 Möglichkeiten

...

45 Steine 1 Möglichkeit

---

Wieso ?? Hab ich was verpasst ?

Und es ist ja maximal 45 Steine also es können 45 Steine sein, aber muss nicht richtig ?

---

Richtig. Wenn ich das richtig verstanden habe solltest du für jede Beliebige Zahl von 9 bis 45 angeben können wie viele mögliche Mauern es dazu gibt die gebaut werden könnten.

Wobei 9 und 45 die Trivialfälle sind, weil es dafür nur genau eine mögliche Mauer gibt.

Aber das ist jetzt auch nur das wie ich es bis jetzt verstanden habe.

---

Okay vielen Dank für die Hilfe :-)

---

Eine Frage, wie kommt man bei 10 Steine auf 8 Möglichkeiten und bei 12 Steine auf 7+(8 über 3) Möglichkeiten ? Also wie sind Sie hier vorgegangen und wie kann man weiter so rechnen ?

---

Da sich ja jetzt der Übungsleiter gemeldet hat und richtig gestellt hat, wie die Aufgabe gemeint war erübrigt sich jetzt deine Frage.

Daher hier nur ein Hinweis sich mit folgender kleinen Lektüre zu beschäftigen

https://www.bnv-bamberg.de/home/ba2636/catalanz.pdf

---

Wäre vielleicht C(45) - C(9) die Lösung ?

---

Die Lösung wäre dann nur

C₉ = 4862

https://de.wikipedia.org/wiki/Catalan-Zahl

---

Ach ja mein Fehler, stimmt ja

Weil ja alle Steine von der untersten Reihe mit 9 Steinen abhängig sind ...

Dankeschön :-)

Answer 2

Nehmen wir mal an, es sollen für ein solches Mauerbeispiel genau 12 Steine verbaut werden. Die erste Reihe (von unten) ist ja gesetzt und verbraucht 9 Steine. Wegen der Mittigkeitsregel müssen die nächsten beiden Steine in die zweite Reihe. Der zwölfte und letzte Stein kann dann auf jeden Fall auch in die zweite Reihe, oder, bei benachbarter Lage der beiden vorletzten Steine, auch in die dritte Reihe.

Comments

Vielleicht spricht jetzt meine Verwirrung, aber was wäre dann die Anzahl der Möglichkeit ?

---

Bei 12 Steinen wären das (2 aus 8) + 7 = 35 mögliche Mauerstückprofile.

Die Anzahl der verbaubaren Steine reicht von 9 bis zu 45.

---

Dankeschön :-)

Für 13 Steine wäre es dann 6+(8 über 4) also 76 Möglichkeiten ? Oder hab ich das wieder falsch verstanden?

---

Oder anders gefragt, wie kommt man für die 10 Steine auf 8 Möglichkeiten und dann bei 12 auf 7+ (8über 3) ?? Ich versteh das nicht so ganz :(

---

Entschuldige bitte, ich habe mich vertan, ich meinte

Bei 12 Steinen wären das (3 aus 8) + 7 = 56 + 7 = 63 mögliche Mauerstückprofile.

Die 3 Steine, die nicht in der ersten Reihe liegen können, können auf den 8 Plätzen der zweiten Reihe liegen. Dafür gibt es (3 aus 8) Platzkombinationen. Liegen zwei der drei Steine jedoch nebeneinander in der zweiten Reihe und der dritte Stein dann obenauf in der dritten Reihe, ergeben sich noch 7 weitere Möglichkeiten.

---

Dankeschön :-)

Answer 3

Ich vermute, dass es um folgende Möglichkeiten geht:

Untere Reihe: immer 9 Steine

1) zweite Reihe 8 Steine

1a) 9,8,7,6,5,4,3,2,1

1b) 9,8,7,6,5,4,3,2,0

1c) 9,8,7,6,5,4,3,1,0

usw.

2) zweite Reihe von unten: 7 Steine, also eine Lücke; 9,7,.....

Darauf alle möglichen kürzeren Mauern

3) 9,6,...      usw.

Comments

Also @ mathe_was_sonst wäre es dann 9!*8!*7!*6!*5!*4!*3!*2!*1! ?

---

@Emily: Das überblicke ich auch nicht so schnell.

Ich würde von oben anfangen. Wenn ich nur einen Stein hinlege, habe ich eine Möglichkeit.

Bei 2 Steinen kann ich einen oder keinen Stein oben raufpacken → 2 Möglichkeiten.

Bei 3 Steinen in der untersten Reihe gibt es die Möglichkeiten

321, 320, 2 mal 310, 300 → 5 Möglichkeiten

---

@mathe_was_sonst Achso, Okay jetzt verstehe ich es! :)

---

Ich habe mit einem Zeichenprogramm 13 Möglichkeiten bei 4 Basissteinen gefunden.

1 → 1

2 → 2

3 → 5

4 → 13

Daher vermute ich, dass es mit der Fibonacci-Folge zusammenhängt:

1, 1, 2, 3, 5, 8, 13, ...

n → Fib(2n-1)

9 → Fib(17)=1597

---

Vielen Dank für deine Hilfe :-)

---

Hm, stimmt doch nicht. Bei 4 Basissteinen gibt es 14 Möglichkeiten.

---

Ist kein Problem, ich werde es einfach mal aufzeichnen und jede Möglichkeit durchgehen ... Wobei ich mir immer noch nicht ganz sicher bin, ob das von mir verlangt wurde .. ^^'

---

Eine Frage, für den obersten stein gibt es doch 2 Möglichkeiten also entweder wird der Stein mit eingebaut oder nicht, oder? (wegen Lücken)

Dann bei der vorletzten Reihe also 2 Steine, gibt es dann 4 Möglichkeiten, weil 2 1, 2 0, 0 1, 0 0 , oder? weil so hätte ich ohne für die feste Reihe 2^8 Möglichkeiten weil es ja 9 Reihen gibt, aber ohne die unterste wäre es dann 8 Reihen und so dann 256 Möglichkeiten ?

So wie ich es verstehe wenn ich das ganze aufmale, sind die untersten Steine fest, das heißt das ist für die Anzahl der Möglichkeiten irrelevant, weil man sich auf die weiteren Reihen mit Lücken konzentriert oder?

---

Bei der vorletzten Reihe gibt es 5 Möglichkeiten, da der eine Stein links oder rechts liegen kann.

 0      0      0     0     1

00    10    01   11   11

Die unterste Reihe ist fest. Das sehe ich auch so. Die Schwierigkeit fängt ja in der zweituntersten an:

11111111   Keine Lücke

11111110    Die Lücke, also 0, kann an jeder Stelle stehen.

Möglich wäre auch

11000110

oder

10110111

usw.

Leider sehe ich kein System, das ich berechnen kann.

---

Bei der Vorletzten Reihe also vor der dem letzten einen Stein ?

Ich dachte eher 4 Möglichkeiten, weil wenn 2 Steine gebaut werden, dann wäre es 2 1 und wenn nur ein Stein dann entweder 2 0, oder 0 1

Wenn kein Stein also komplette Lücke, dann 0 0 also insgesamt 4 Möglichkeiten

Oder hab Ihren Kommentar falsch verstanden, was die Reihe betrifft ?

---

Ich habe dir doch die 5 Möglichkeiten aufgeschrieben. Wenn nur ein Stein in der zweitobersten Reihe steht, kann er links oder rechts stehen.

---

Ich meine das so, ist das falsch ?

So sieht meine Vorletzte Reihe von oben aus (Reihe 2), wenn der Stein links oder rechts stehen sollte, dann wäre es doch 2 0 oder 0 1 oder nicht ?

Tut mir leid, dass ich mich so dumm anstelle, aber entweder sollte ich jetzt kein Mathe machen oder ich verstehe die Aufgabe einfach nicht. :(

---

Ach so, ich wusste nicht, wie deine Nummerierung gemeint war.

Ich bin auf 5 gekommen, weil über 21 ja entweder 1 oder 0 Steine sein können.

     1        0

    21      21

Es reicht also nicht jede Zeile für sich zu betrachten, weil die höheren berücksichtigt werden müssen.

---

Achso okay :-) Danke für deine Hilfe :-)

Answer 4

So, damit melde ich mich als Aufgabensteller auch mal, nachdem mir der Link geschickt wurde. Ich habe mir die Antworten und Kommentare durchgelesen - mathe_was_sonst hat Recht, für 4 Basissteine gibt es 14 Möglichkeiten. Die anderen Folgenglieder sind korrekt, also $$F(1)=1, F(2)=2, (3)=5, F(4)=14.$$

Diese Folge kennt ihr bereits aus der Vorlesung bzw. dem Buch... ansonsten könnt ihr ja auch mal in der OEIS nachschlagen, dann werdet ihr die Antwort finden. Nur für "die Antwort ist [...]" würde es aber auch keine vollen Punkte geben (falls diese Aufgabe korrigiert wird, das wird noch entschieden) - ihr müsst euch natürlich eine Begründung überlegen.

Comments

Guten sorochan und vielen Dank für deinen Beitrag.

Ich würde gerne wissen, ob meine Überlegungen zur Interpretation der Aufgabe denn nun eher naheliegend oder eher abwegig sind.

---

Du hast natürlich Recht damit, dass nur ein Steintyp verbaut werden soll. Deine anderen Überlegungen sind prinzipiell nicht falsch - ein solches Mauerstück kann in der Tat aus 9 bis 45 Steinen bestehen, aber die Gesamtanzahl interessiert uns hier gar nicht, und wir machen es uns nur schwerer, wenn wir die Fälle danach unterteilen. Viel mehr sollten wir uns überlegen, ob wir nach oben oder nach unten bauen. Mehr kann ich jetzt aber auch nicht verraten, die Abgabe ist erst morgen um 12.^^"

Answer 5

Wie viele Möglichkeiten gibt es, für einen gegebenen Steintypen" da sehe ich nur die eine Möglichkeit.

Ich sehe hier 20! Möglichkeiten, wenn ich annehme, dass die Reihenfolge der zwanzig Steine beim Bauen beliebig gewählt wird. (  ! steht für Fakultät )

Allerdings eine merkwürdige Aufgabe. Frage am besten dort zurück, wo die Frage herkommt.

Comments

Eine Frage, ich habe auch nämlich am Anfang an 20! gedacht, aber dann 20! die Möglichkeit für einen Stein an der ersten Stelle ? und dann hat der 2. Stein die Möglichkeit 19! oder hab ich das falsch verstanden ?

---

Wenn da nur 20 Steine vorhanden sind, hast du zuerst 20 Möglichkeiten und dann 19 Möglichkeiten und dann 18 Möglichkeiten usw.

Das gibt total 20 * 19 * 18 * ... * 1 = 20 ! Möglichkeiten für exakt die gezeichnete Mauerform.

Ich weiss allerdings nicht, ob das so gemeint war. Das musst du selbst entscheiden.

---

Ja genau so meine ich das auch, vielen Dank :)