Partner von azubiworld.com - Logo
 
Mathematik online lernen im Mathe-Forum. Nachhilfe online
Startseite » Forum » Kuchenstuecke mit Reihenfolge essen (Kombinatorik)

Kuchenstuecke mit Reihenfolge essen (Kombinatorik)

Schüler

Tags: Kombinatorik, Reihenfolge

 
Antworten Neue Frage stellen Im Forum suchen
Neue Frage
DieNisi

DieNisi aktiv_icon

09:47 Uhr, 31.03.2021

Antworten
Hallo,

ich bin etwas eingerostet in der Kombinatorik aber habe folgende Knobelaufgabe:
Gegeben ist ein Kuchen mit n Stueckchen. k Gaeste sollen davon essen, wobei jeder Gast mindestens ein Stueck bekommen soll. Da man sich fuehlen koennte als wuerde man nicht zwei, sondern nur 1 grosses Stueck bekommen, darf kein Gast 2 aneinander grenzende Stueckchen essen. Wie viele Moeglichkeiten gibt es den Kuchen zu essen?
Gegeben habe ich folgende vorberechnete Angaben:
5 Stueckchen, 4 Gaeste =120 Moeglichkeiten
4 Stueckchen, 1 Gast =0 Moeglichkeiten (wegen angrenzend)
4 Stueckchen, 2 Gaeste =2 Moeglichkeiten

Also die 5 Stueckchen mit 4 Leuten nehme ich jetzt mal fuer meine Ueberlegungen:
Das erste Stueck hat 4 moegliche "Verspeiser" das zweite, dritte, vierte und 5te dann jeweils nur noch 3 moegliche "Verspeiser". Oder schaue ich verkehrt herum? Muss ich sagen 4 Leute essen schon mal ein Stueck also 4! und dann muss das eine Stueck noch 3 Moeglichkeiten haben? Dann komme ich aber nicht auf glatte 120 Moeglichkeiten ...

Interessant waere fuer mich 1) Was schaue ich mir da eigentlich gerade an? Permutation? Variation? Ziehen ohne Zuruecklegen mit Reihenfolge und Nebenbedingungen?
2) Da ich natuerlich mit festen Zahlen nichts anfangen kann fuer n Kuchenstuecke und k Gaeste, brauche ich noch eine Formel...


Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich benötige bitte nur das Ergebnis und keinen längeren Lösungsweg."
Hierzu passend bei OnlineMathe:

Online-Übungen (Übungsaufgaben) bei unterricht.de:
 
Antwort
supporter

supporter aktiv_icon

10:19 Uhr, 31.03.2021

Antworten
"Da man sich fuehlen koennte als wuerde man nicht zwei, sondern nur 1 grosses Stueck bekommen"
Wie meinst du das? Sind die Stücke nicht klar abgegrenzt?
DieNisi

DieNisi aktiv_icon

10:22 Uhr, 31.03.2021

Antworten
Kein Gast darf zwei Stuecke essen die nebeneinander sind?
Also bei 5 Stueckchen Kuchen und 2 Leuten koennen wir den Kuchen nicht essen, weil ein Gast zwei Stueckchen essen muesste, welche nebeneinander liegen.
Warum das so ist weiss ich nicht , vielleicht ist dem Aufgabensteller nichts besseres eingefallen :-)
Antwort
HAL9000

HAL9000 aktiv_icon

10:30 Uhr, 31.03.2021

Antworten
Du hast nicht erwähnt, ob man erstes und letztes Stück als benachbart betrachten soll (wie etwas bei einer kreisrunden Torte) oder nicht.


Für jedes der beiden Probleme

1) jeder soll mindestens ein Stück bekommen,

2) keine zwei benachbarten Stücke bekommt dieselbe Person

hätte ich EINZELN eine Lösung (bei 2) zumindest im Nichtkreis-Fall), aber beides zusammen macht die Sache ziemlich kompliziert.


Zu den Lösungen der Einzelprobleme

1) j=0k(-1)j(kj)(k-j)n, bekanntes Problem und per Siebformel lösbar.

2) k(k-1)n-1 (im Kreisfall ist es nicht so einfach)

Aber beide Bedingungen zusammen? Selbst zum Aufstellen geeigneter Rekursionsgleichungen habe ich (noch) keinen passenden Hebel gefunden. ?(


> Was schaue ich mir da eigentlich gerade an? Permutation? Variation? Ziehen ohne Zuruecklegen mit Reihenfolge und Nebenbedingungen?

Genau genommen Variationen mit Wiederholung, d.h. eine Auswahl von n aus k Elementen mit Berücksichtigung der Auswahlreihenfolge und mit Zurücklegen, aber eben mit den genannten zwei Nebenbedingungen oben, die die Sache so komplizieren.
DieNisi

DieNisi aktiv_icon

10:49 Uhr, 31.03.2021

Antworten
Okay, so habe ich das noch gar nicht gesehen.
Tatsaechlich steht in der Beschreibung nichts davon, ob die letzten Stueckchen auch zaehlen. Ich waere mal davon ausgegangen.

Also gugg ich mal was wir da haben:

Wenn ich jetzt aber mein 5 Stueckchen und 4 Gaeste einsetze, dann haette ich fuer deinen Ansatz
2):

434=325
Macht das Sinn? Ich wollte doch auf 120 rauskommen.

Dann gugge ich das erste an:
1(4!1(4-0))(4-0)5+(-1)(4!1(4-1))(4-1)5+(1)(4!2(4-2))(4-2)5... Mach ich das hier ueberhaupt richtig? Ich bin verwirrt.

Ich hatte irgendwie gehofft, dass man da vorgehen kann wie in diesem Beitrag:
www.onlinemathe.de/forum/Kombinatorik-mit-zusaetzlicher-Bedingung
Antwort
HAL9000

HAL9000 aktiv_icon

10:56 Uhr, 31.03.2021

Antworten
> Macht das Sinn? Ich wollte doch auf 120 rauskommen.

Hast du überhaupt gelesen, was ich geschrieben habe??? Bei 2) EINZELN betrachtet fehlt die Forderung, dass jeder auch ein Stück bekommt, damit ist dieser Anzahlwert natürlich viel zu groß geraten. Ein bisschen Brainstorming wird doch wohl erlaubt sein, ohne dass gleich einer losjammert "kann nicht sein, muss doch 120 rauskommen".

==========================================

Ok, ein möglicher Zugang (orientiert sich an beiden Ideen oben): Wir betrachten die Mengen

Aj ... Menge der Zuteilungen, wo keine zwei benachbarten Stücke an dieselbe Person gehen UND wo Person j kein Stück bekommt

und wenden darauf dann die Siebformel an. Damit bekommt man im Nichtkreisfall die Anzahl

f(n,k):=j=0k-1(-1)j(kj)(k-j)(k-j-1)n-1

an gültigen Kuchenaufteilungen. Da kommt bei n=5,k=4 der Wert 144 raus - offenbar erfüllen dann 24 dieser Variationen wie etwa

23142

nicht die zusätzliche Kreistorten-Bedingung "erster und letzter müssen verschieden sein". Ich überlege gerade noch, ob man den Kreistortenfall einfach mit f(n,k)-f(n-1,k) reparieren kann, oder ob da nicht doch ein Denkfehler vorliegt... (EDIT: Für n=5,k=4 reicht diese Reparatur; i.a. aber nicht.)


Ok, noch ein Versuch für die Anzahlformel im Kreistortenfall:

g(n,k):=j=0k(-1)j(kj)(k-j-1)n für nk .

Sicher bin ich mir bei der auch nicht, aber sie hält zumindest einigen einfachen Beispielen stand. Übrigens, die einzelne Anzahlformel 2) im Kreistortenfall ist nicht etwa (wie man vielleicht meinen könnte) (k-1)n, sondern müsste dort

2) (k-1)n+(-1)n(k-1) für nk2

sein. Aber wieder ohne Gewähr. ;-)




Frage beantwortet
DieNisi

DieNisi aktiv_icon

04:12 Uhr, 01.04.2021

Antworten
Danke fuer deine ausfuerliche Antwort!
Hatte nicht erwartet jemanden zu finden der da ueberhaupt Lust hat sich hinzusetzen und etwas zu schreiben. :-)

Falls ich noch bessere Schluss folgerungen habe, Update ich sie hier, aber ich sehe deine Antwort erst mal als hinreichend an :-)

Danke und liebe Gruesse.
Antwort
Eduard von Nordstadt-Süd

Eduard von Nordstadt-Süd aktiv_icon

10:22 Uhr, 01.04.2021

Antworten
Hallo,

interessanter Thread.
Eine Formel habe ich nicht gefunden,
aber (rekursiv) programmieren kann man es recht gut.
Mein Rechner (lahmes Ding) fängt aber ab 8 Stücke
und 6 Gäste doch an zu stottern. Der Code ist
allerdings auch bestimmt nicht optimal, siehe Anhang...


Kuchen mampfen
Frage beantwortet
DieNisi

DieNisi aktiv_icon

11:45 Uhr, 01.04.2021

Antworten
Wow , das ist klasse!
Ich fuerchte nur, dass ich um das genau verstehen zu koennen alle Variablen umbenennen muss. Ich war bei z3 bis 6 und dann z4 bis z3 und dann dann ... dann bin ich verloren gewesen.
Du lagst aber schon ganz richtig , es ist eine Knobelaufgabe zum programmieren. Ich dachte nur ich poste es hier, weil es mit dem Bereich Kombinatorik natuerlich eher in den Bereich Oberstufe / Untere Semester faellt :-)

Antwort
Eduard von Nordstadt-Süd

Eduard von Nordstadt-Süd aktiv_icon

12:13 Uhr, 01.04.2021

Antworten
Der Code ist gruselig,
jeder Informatiker schlägt die Hände über dem Kopf zusammen,
wenn er das sieht.
Die z's (wie Zähler) sind Ackergaule, sie werden für dieses
oder jenes verwendet, schöner ist es natürlich,
wenn die Variablen auch namentlich an ihren
Zweck erinnern...
Ich hab ganz vergessen, praxisnahe Beispiele
zu rechnen - so einen Kuchen, den zerlegt man
doch in ca. 10-12 Stücke, oder ? Und ein
Kaffekränzchen, das sind doch so ungefähr 3 Leute,
selten mehr...

Du programmierst ?
Wir könnten das auch noch elaborieren...

Antwort
Eduard von Nordstadt-Süd

Eduard von Nordstadt-Süd aktiv_icon

12:39 Uhr, 01.04.2021

Antworten
z3 zählt Kuchenstücke, quasi n
z4 zählt Gäste, quasi k (deswegen bis z3,
weil sonst nicht jeder ein Stück kriegen kann).
Für jedes Tupel (z3,z4) werden dann von
"R_Kuchen" die Verzehrmöglichkeiten ermittelt.
Der erste Aufruf R_Kuchen(1) erfolgt immer aus der
z3,z4-Schleife und R_Kuchen wuselt sich dann
rekursiv immer wieder bis R_Kuchen(z3), also dem letzten Stück
durch. Eine Kontrollschleife am Ende (dieser akz-Klotz)
testet dann, ob eine gültige Verteilung (jeder wenigstens
ein Stück) vorliegt und erhöht gegebenenfalls z5,
die Anzahl der Möglichkeiten...
Antwort
HAL9000

HAL9000 aktiv_icon

13:15 Uhr, 01.04.2021

Antworten
@Eduard

Genausowas hatte ich mir gewünscht, war nämlich zu faul das zu programmieren. Mit einer gewissen Genugtuung stelle ich fest, dass deine angegebenen Anzahlwerte für 6n8 und zugehörigem 5kn sämtlich mit meiner oben angegebenen Formel g(n,k) übereinstimmen. Das ist zwar kein Beweis der Formel, aber schon mal ein ganz gutes Indiz für deren Richtigkeit. ;-)

P.S.: Den Gültigkeitsbereich der obigen Formel muss ich auf nk2 einschränken, denn für k=1 haut sie tatsächlich nicht hin. Aber wer braucht für diesen Trivialfall schon diese Formel. ;-)
Antwort
Eduard von Nordstadt-Süd

Eduard von Nordstadt-Süd aktiv_icon

13:25 Uhr, 01.04.2021

Antworten
HAL, Deine letzte Formel (die ohne Gewähr bzw. der Part nach "23142") habe ich noch nicht auf
dem Schirm, die davor schon. Ich ruhe gerade, werde aber noch
mal darüber sinnieren...
Antwort
Eduard von Nordstadt-Süd

Eduard von Nordstadt-Süd aktiv_icon

13:53 Uhr, 01.04.2021

Antworten
Ich habe gegooglet - einen Kuchen pflegt man zu zwölfteln...
Hier noch mehr Werte, 12 Stücke, 5 Gäste hat auch schon
ca. 30 Sekunden Rechenzeit benötigt.

Kuchen mampfen 2
Antwort
HAL9000

HAL9000 aktiv_icon

14:02 Uhr, 01.04.2021

Antworten
Na dann, ein paar Werte zum Vergleichen:

12, 2, 2
12, 3, 4092
12, 4, 515064
12, 5, 14160960
12, 6, 151367040
12, 7, 801662400
12, 8, 2360413440
12, 9, 4051555200
12, 10, 4031596800
12, 11, 2155507200
12, 12, 479001600

Für die Torte mit 24 Stücken und 18 Gästen

24, 18, 310816489035833816555520000

wird dein Simulationsprogramm vermutlich in die Knie gehen... :-D)
Antwort
Eduard von Nordstadt-Süd

Eduard von Nordstadt-Süd aktiv_icon

14:18 Uhr, 01.04.2021

Antworten
Du gewinnen !
Wie gerechnet ? Nasa-Rechenzentrum ?
Oder Deine Formel ?
Antwort
HAL9000

HAL9000 aktiv_icon

14:57 Uhr, 01.04.2021

Antworten
Na klar die Formel. So einen Supercomputer, der das einzeln durchzählen kann, habe ich sicher nicht.
Frage beantwortet
DieNisi

DieNisi aktiv_icon

15:24 Uhr, 01.04.2021

Antworten
Hut ab, mega ambitioniert ihr 2.
Danke für beide eingereichten Antworten, ihr habt mich beide ein Stück schlauer und ideenreicher gemacht.
Danke auf jeden Fall! Hat mich riesig gefreut!
Frage beantwortet
DieNisi

DieNisi aktiv_icon

15:24 Uhr, 01.04.2021

Antworten
Hut ab, mega ambitioniert ihr 2.
Danke für beide eingereichten Antworten, ihr habt mich beide ein Stück schlauer und ideenreicher gemacht.
Danke auf jeden Fall! Hat mich riesig gefreut!
Frage beantwortet
DieNisi

DieNisi aktiv_icon

15:24 Uhr, 01.04.2021

Antworten
Hut ab, mega ambitioniert ihr 2.
Danke für beide eingereichten Antworten, ihr habt mich beide ein Stück schlauer und ideenreicher gemacht.
Danke auf jeden Fall! Hat mich riesig gefreut!
Antwort
HAL9000

HAL9000 aktiv_icon

16:18 Uhr, 01.04.2021

Antworten
Hab dann doch auch noch ein kleines C++-Progrämmchen zum Zählen der Varianten geschrieben. Ist nicht besonders effizient, weil es alle kn Variationen durchgeht, und dann die gültigen zählt.

EDIT: Verdammt, offenbar kann man hier kein Text-Files anhängen. Und die zip-Variante kann man zwar anfügen, aber dann nicht wieder downloaden... Tja, dann eben auch nur als Bild.

Kuchenstuecke
Antwort
Eduard von Nordstadt-Süd

Eduard von Nordstadt-Süd aktiv_icon

04:35 Uhr, 02.04.2021

Antworten
HAL,

hier ein Beweis für die zuletzt von Dir angegebene
Formel für die 2. Bedingung "keine doppelten Nachbarn", also

(IV)

s(n,k):=(k-1)n+(-1)n(k-1)    n,kN:n>1,k>2

(IA)

s(2,k)=k(k-1)=(k-1)2+(k-1),

s(3,k)=k(k-1)(k-2)=(k-1)(k2-2k)
=(k-1)(k2-2k+1)-(k-1)=(k-1)3-(k-1).

Für den Induktionsschritt nutzen wir die Rekursionsformel

s(n,k)=s(n-1,k)(k-2)+s(n-2,k)(k-1),

die man folgendermaßen erklären kann:

Betrachte einen bis auf ein letztes Stück verteilten bzw. zugeordneten Kuchen.
Sind die zwei Nachbarstücke des letzten Stücks verschiedenen Gästen zugeordnet,
so ist der Kuchen ohne dieses Stück ein vollständig verteilter Kuchen aus n-1 Stücken
und für das letzte Stück gibt es k-2 Möglichkeiten, an den Mann zu kommen.
Das ist dann also der Summand s(n-1,k)(k-2).
Sind die zwei Nachbarstücke des letzten Stücks demselben Gast zugeordnet,
so ist der Kuchen ohne dieses Stück und ohne eines der Nachbarstücke
(OBdA z.B. das "linke", vorletzte) ein vollständig verteilter Kuchen aus n-2 Stücken
und für das letzte Stück gibt es k-1 Möglichkeiten, an den Mann zu kommen.
Das ist dann also der Summand s(n-2,k)(k-1).
Nun gelingt

(IS)

s(n,k)=s(n-1,k)(k-2)+s(n-2,k)(k-1)

=((k-1)n-1+(-1)n-1(k-1))(k-2)+((k-1)n-2+(-1)n-2(k-1))(k-1)

=(k-1)n-1(k-2+1)+(-1)n-1(k-1)(k-2)+(-1)n-2(k-1)2

=(k-1)n+(-1)n-1(k-1)((k-2)-(k-1))

=(k-1)n+(-1)n-1(k-1)(-1)

=(k-1)n+(-1)n(k-1).


Antwort
HAL9000

HAL9000 aktiv_icon

08:48 Uhr, 02.04.2021

Antworten
Vielen Dank für die Mühe! Damit ist der letzte Baustein abgesichert, denn mit dieser bewiesenen Anzahl

h(n,k)=(k-1)n+(-1)n(k-1) für nk2

sowie dem durch Siebformel begründbarem

g(n,k)=j=0k-2(-1)j(kj)h(n,k-j) ebenfalls für nk2

folgt die obige Formel g(n,k)=j=0k(-1)j(kj)(k-j-1)n .

Antwort
Eduard von Nordstadt-Süd

Eduard von Nordstadt-Süd aktiv_icon

09:06 Uhr, 02.04.2021

Antworten
Und jetzt noch der Beweis für HAL's Tortenformel selbst !
Gibt aber 'ne Menge Tamtam rund um den Binomialkoeffizienten, Warnung !
Daher habe ich alles sehr kleinschrittig aufgeschrieben.

Also, sei n,kN:nk3.

Wir nutzen das Inklusions-Exklusions-Prinzip, um auch noch die Bedingung 1
"jeder wenigstens ein Stück" zu verwirklichen, gibt

g(n,k)=l=0k(-1)l(kk-l)s(n,k-l)

=l=0k(-1)l(kk-l)((k-1-l)n+(-1)n(k-1-l))

=l=0k-2(-1)l(kk-l)((k-1-l)n+(-1)n(k-1-l))

=l=0k-2(-1)l(kk-l)(k-1-l)n+l=0k-2(-1)n+l(kk-l)(k-1-l)

=l=0k-2(-1)l(kk-l)(k-1-l)n+l=0k-2(-1)n+k-(l+2)(kl+2)(l+1)

=l=0k-2(-1)l(kk-l)(k-1-l)n+l=2k(-1)n+k-l(kl)(l-1)

=l=0k-2(-1)l(kk-l)(k-1-l)n+(-1)n+kl=2k(-1)l(kl)(l-1)

=l=0k-2(-1)l(kk-l)(k-1-l)n
+(-1)n+kl=2k(-1)l(kl)l
-(-1)n+kl=2k(-1)l(kl)

=l=0k-2(-1)l(kk-l)(k-1-l)n
+(-1)n+kkl=2k(-1)l(k-1l-1)
-(-1)n+kl=2k(-1)l(kl)

=l=0k-2(-1)l(kk-l)(k-1-l)n
-(-1)n+kkl=1k-1(-1)l(k-1l)
-(-1)n+k(-1+k+l=0k(-1)l(kl))

=l=0k-2(-1)l(kk-l)(k-1-l)n
-(-1)n+kk(-1+l=0k-1(-1)l(k-1l))
-(-1)n+k(-1+k+l=0k(-1)l(kl))

=l=0k-2(-1)l(kk-l)(k-1-l)n
-(-1)n+kk(-1+0)
-(-1)n+k(-1+k+0)

=l=0k-2(-1)l(kk-l)(k-1-l)n
+(-1)n+k

=l=0k(-1)l(kk-l)(k-1-l)n.





Antwort
Eduard von Nordstadt-Süd

Eduard von Nordstadt-Süd aktiv_icon

09:14 Uhr, 02.04.2021

Antworten
Eine Sache noch. Für s habe ich zu vorsichtig
k>2 definiert, k2 klappt aber auch noch,
was sogar elementar wichtig für den g-Beweis ist !
k kann für s übrigens auch größer als n sein,
was die Formel dann zwar für das Kuchenproblem unbrauchbar macht,
aber nicht falsch bezüglich Bedingung 2.
Für g kann dann also auch nk2 sein
und nicht bloß nk3, sorry.
Ich werde diesen ganzen Thread aber auch noch zusammenschnibbeln
und als jpg hier einpflegen.


Antwort
Eduard von Nordstadt-Süd

Eduard von Nordstadt-Süd aktiv_icon

00:47 Uhr, 03.04.2021

Antworten
So, hier, ausgebeult und zurechtgestutzt der Thread.
Ging leider nur als Zweiteiler hoch.
Dank an HAL für die Steilvorlage,
die ich nur noch nachvollziehen musste.


Kuchen mampfen 1
Kuchen mampfen 2