Unser Kaffee, wir und die Mathematik
T: “Schreib ‘6 Millionen Sorten Kaffee’ rein.”
T: “Das sind aber mehr.”
T: “9 hoch 12 mal 1716 Aromenkombinationen?”
T: “Da ist die Reihenfolge aber noch mit drin, 12 über 9 wär das sonst. QM2 ist lang her.”…
Wir wissen es nicht. Wie viele Kombinationen von reinem und aromatisierten Kaffee sind bei uns eigentlich möglich?
Sagt es uns bitte. Das ist die Stunde der Mathematiker: Wer uns als erster schlüssig vorrechnen kann, die viele Millionen oder Milliarden Kaffeemischungen wir eigentlich anbieten, dem schenken wir eine davon, frei Haus. Überprüfen können wir die Lösung eh nicht, aber es sollten schon alle Faktoren einbezogen sein.
Wir packen jetzt den Rechenschieber wieder ein und hoffen auf Eure Hilfe.
Tags: Kombinationen, Mathematik, Wettbewerb
May 21st, 2008 at 09:24
Hey Jungs,
so schwere Mathematik ist das doch nicht.
Ihr müsst doch einfach über den Binomialkoeffizenten gehen.
Wenn ich das richtig verstanden habe, habt ihr doch 12 Plätze zu vergeben und die können von allen Sorten eingenommen werden.
Das ist genauso wie damals in der Schule mit dem verdeckten Ziehen aus einer Urne mit Zurücklegen.
Nur doof, dass ich keinen Kaffee trinke.
Habt ihr noch ein anderes Angebot? *g*
Grüße aus Köln,
Cedric
May 21st, 2008 at 09:24
Hallo, man kann maximal “3 aus 13″ Aromakombinationen wählen - also 286 (ähnlich Lotto, also ohne Berücksichtigung der Reihenfolge und ohne(!) Wiederholung, d.h. kein Aroma mehrfach verwenden). Ihr habt 9 Sorten, also sind dies 9*286 = 2574 Möglichkeiten. Jeder dieser Möglichkeiten gibts in einem von 4 Mahlgraden, also sind es 10296 Möglichkeiten für ein Produkt… Sollten es tatsächlich “so wenig” sein? Bin allerdings auch kein Mathematiker… Oliver
May 21st, 2008 at 09:36
Erste Annäherung:
Ihr habt 9 verschiedene Kaffee sorten. Diese Lassen sich auf 2^9 verschiedene arten kombinieren. (Jede Kaffeesorte kann in der Mischung auftauchen (1) oder nicht (0))
Das wären also schon mal 512 Mischungen. (Wenn alle Teile zu jeweils gleichen Teilen gemischt werden).
Dazu kommen noch die von euch erwähnten 1716 Aromakombinationen, und es gibt (in erster Annäherung) 878592 verschiedene Kaffees.
Genau:
Da ihr aber das ganze in 1/12 schritten anbietet, müssen wir etwas anders denken. Wir wählen einfach 12 mal hintereinander eine Kaffeesorte aus. Wiederholungen sind natürlich erlaubt, die Reihenfolge ist aber egal. Das zu wählende “Urnenmodell” ist also “Ungeordnete Ziehung, mit Zurücklegen” ((9 + 12 - 1) über (12)) = 125970
Bei den Aromen können wir 3 Mal (oder 2, oder 1 mal oder kein mal) ungeordnet, ohne zurücklegen aus 13 Aromen wählen, also ((13 über 3) + (13 über 2) + 13 + 1) = 378 Möglichkeiten
Demnach solltet ihr also 47616660 verschiene Kaffees anbieten.
(P.S. verlasst euch nur bedingt auf meine Aussage…ich hatte heute noch kein Koffein
May 21st, 2008 at 09:38
Ich habe natürlich noch die Malgrade vergessen. Die letzte Zahl also bitte noch mit 4 Multiplizieren
May 21st, 2008 at 09:38
@Oliver: Du berücksichtigst nicht, dass (im Gegensatz zum Aroma) Sorten doppelt, dreifach … bis zu 12-fach (weil 12 wählbare Plätze in der Mischungszusammensetzung) genommen werden können. Der Ansatz im Posting mit dem Binomialkoeffizient ist glaub ich gar nicht sooo falsch.
May 21st, 2008 at 09:51
@Cedric: Wir haben keine 12 festen Plätze, sondern bis zu 12. Sonst wär es schon viel einfacher.
@Oliver: 3 aus 13 wären 1716, wie es bei uns auf der Startseite steht. Wie mir gerade aufgefallen ist, wird da die Möglichkeit, nur ein, zwei oder keine Aromen zu nehmen, also Slots leer zu lassen, nicht einbezogen.
Die neun Sorten kannst Du auch noch miteinander kombinieren!
Mahlgrade lassen wir außen vor, bleibt ja dieselbe Mischung.
Das Rätsel ist noch längst nicht gelöst.
May 21st, 2008 at 10:00
@Till: Also ich finde das Rätsel ist gelöst… 47616660
(”Bis zu 12″ ist ja inbegriffen, da du ja einfach 12 mal den selben Kaffee auswählen kannst
May 21st, 2008 at 10:01
Oops, da hab ich ja so einiges übersehen… Ich rechne weiter… Oliver
May 21st, 2008 at 10:02
Es ist auch zu berücksichtigen, dass das Verhältnis 1:1 denselben Kaffee ergibt wie z.B. das Verhältnis 2:2 oder 3:3 (bei der Auswahl der der Kaffeesorten). Und so weiter, 1:1:1 = 2:2:2 = 3:3:3 …
Somit klappt es mit dem einfachen Binominialkoeffizienten erstmal nicht. Aber vermutlich wird der schon irgendwie in der Rechnung auftauchen.
May 21st, 2008 at 10:03
@Till: 3 aus 13 sind nur dann 1716 wenn es wichtig ist in welcher Reihenfolge die Aromen ausgewählt werden….
May 21st, 2008 at 10:07
@Björn: Wenn man gleich 12 Mal hintereinander ziehen lässt kommt diese Frage (praktischer weise) erst gar nicht auf.
May 21st, 2008 at 10:09
@Jan: Es gehen auch Mischungsverhältnisse wie 1:6 oder 2:3, dann haben wir auf einmal Siebtel und Fünftel im Spiel, die Du mit den Zwölfteln nicht abdecken kannst.
Die 3 aus 13 Geschichte verstehe ich noch nicht. Ich werd mir das gleich mal visualisieren, indem ich schnell alle Kombinationen mische.
May 21st, 2008 at 10:10
Schwierig sind nur die Kaffeemischungsverhältnisse. Bei Aromakombinationen komme ich auf 378: 1+13+”2 aus 13″+”3 aus 13″, man muss ja auch die Möglichkeiten zählen, weniger als 3 Aromen zu wählen.
May 21st, 2008 at 10:16
@Jan: doch, Du kannst doch zweimal Kenya Perl und zweimal Peru ziehen.
May 21st, 2008 at 10:22
Hm, Jan, Ich glaube Du hast doch so halb recht: bei fester Zuganzahl sind die Äquivalenzklassen egal (habe es nicht so genau durchgerechnet). Also muss man zur Lösung nur noch die Summe der Möglichkeiten für 1 mal ziehen, 2 mal ziehen, … 12 mal ziehen berechnen.
May 21st, 2008 at 10:24
Ich trinke gerade eine der 3 fantastillionen Möglichen Kaffeemischunen von Sonntagmorgen und genießen ihn ganz ohne Mathe!
Puuh! Glück gehabt!
Grüße aus Bonn, Oli
May 21st, 2008 at 10:24
Mist, nein, wenn man das so macht, hat man ja wieder das Äquivalenzklassenproblem (3 mal Ziehen ergibt teilweise gleiche Kaffeesorten wie 6 mal Ziehen etc.). #Kommentarspam
May 21st, 2008 at 10:38
Ihr benutzt Worte, die ich nicht verstehe. Aber macht ruhig weiter, fühlt Euch wie zuhause.
May 21st, 2008 at 10:43
“A mathematician is a device for turning coffee into theorems” - Paul Erdös (oder Alfréd Rényi, Wikipedia ist sich nicht sicher).
May 21st, 2008 at 11:31
Hey, immer noch nicht weiter?
@Till: Tut mir Leid, dass ich mich nur auf die 12/12 bezogen habe. Natürlich muss man noch die anderen Nenner berücksichtigen und überlappende Ergebnismengen subtrahieren.
Meiner Berechnung zu Folge sollten das dann folgende Daten sein:
288.325 Kaffeekombinationen * 4 Mahlgrade * 377 Aromen = 434.794.100 Kombinationsmöglichkeiten
Ich hoffe mal, dass ich kein Detail vergessen habe.
Schöne Grüße aus Köln,
Cedric
May 21st, 2008 at 11:36
Oh, nein. Ein fataler Fehler:
Ich habe vergessen, dass man kein Aroma aussuchen muss, oder?
Dann sind es 435.947.400 Kombinationsmöglichkeiten.
May 21st, 2008 at 11:46
Klingt gut, bis auf die Mahlgrade, die lassen wir wie gesagt raus. Was sagen die anderen Mathematiker dazu?
Die Zahl der Aromen hab ich immer noch nicht verstanden. Nach meiner Rechnung war es so: entweder keins (1) oder eins von 13 (13) oder eine 2er-Kombination (13*12=156) oder eine Dreier-Kombination (13*12*11=1716). Wo ist der Denkfehler?
May 21st, 2008 at 11:49
Der Denkfehler ist bei den Kombinationen. Bei der Dreier-Kombi hast du nur 286 Möglichkeiten, da du doppelte Ergebnisse weglassen musst.
Da kannst du den Binomialkoeffizienten voll einsetzen, da es hierbei um Ziehen ohne Zurücklegen und ohne Beachtung der Reihenfolge geht.
Falls jemanden die Zwischenergebnisse interessieren: http://www.flickr.com/photos/cedricmay/2510391273/
May 21st, 2008 at 12:19
Wo sind denn bei der Dreierkombination nach meiner Denke noch doppelte Ergebnisse?
Kannst Du vielleicht auch die komplette Rechnung veröffentlichen?
May 21st, 2008 at 12:39
So, also ich versuche es mal. Mangels Ruhe habe ich mich wahrscheinlich grob verrechnet, aber das würde die “Crowd” dann ja hoffentlich fixen.
Die Lösung ist ja mgl. Aromen * mgl. Kaffeemischungen, die Zahl der möglichen Aromen (einschliesslich “kein Aroma”) habe ich ja oben schon zu 378 berechnet.
Bleibt die Zahl der Kaffeemischungen. betrachten wir den Fall “12 mal ziehen aus 9 Sorten mit zurücklegen”. Ich bin gerade zu blöd das auszurechnen und stütze mich daher auf die Formel aus der Wikipedia: http://de.wikipedia.org/wiki/Kombinatorik#Kombination_mit_Zur.C3.BCcklegen_.28Repetition.29
Also (k aus (n+k-1)) oder “12 aus 20″ = 125970.
Nun sind noch die Möglichkeiten zu berücksichtigen, 1 bis 11 mal zu ziehen, wobei die Äquivalenzklassen zu berücksichtigen sind (d.h. 1:1 ist äquivalent zu 2:2 etc.). Wann ist eine Mischung mit weniger “Zügen” schon in unseren Mischungen aus 12 Zügen gezählt? Genau dann, wenn der kleinste gemeinsame Nenner der Anteile ein Teiler von 12 ist! Beispiel: 8 mal Ziehen, man nimmt eine Mischung von 2/4+2/4+2/4+2/4. Dieselbe Mischung liesse sich mit 12 Ziehungen durch 3/4+3/4+3/4+3/4 mischen.
Damit fallen alle Mischungen mit 1, 2, 3, 4 und 6 Ziehungen schon mal komplett weg. 5 Ziehungen entfallen auch, weil sie in den Mischungen aus 10 Ziehungen enthalten sind.
Es bleiben 7, 8, 9, 10 und 11 Ziehungen. Erstmal ohne Duplicate die Möglichkeiten pro Zahl der Züge, nach Wikipedia-Formel:
12: 125970
11: 75582
10: 43758
9: 24310
8: 12870
7: 6435
Summe: 288925
Nun die Doppelten abziehen:
Bei allen ist der Fall “n mal gleiche Sorte” schon mitgezählt, also je 9 Möglichkeiten, insgesamt 45.
Bei 10 sind ausserdem die Fälle schon mitgezählt, in denen jede Sorte als Vielfaches von 5 gezogen wird, das sind genausoviele wie es Möglichkeiten für 2 mal Ziehen gibt: 45
Bei 9 sind zusätzlich die doppelt, bei denen die Anteile ein Vielfaches von 3 sind, davon gibe es “3 über (9+3-1)”, also 165.
Bei 8 sind Vielfache von 2 und von 4 doppelt gezählt, davon gibt es so viele wie bei 4mal Ziehen bzw. 2 mal ziehen, nach Formel 495 und 45
Insgesamt abzuziehen: 45+45+165+495+45 = 795
Zahl der Möglichkeiten für Mischungen insgesamt also: 288925-795 = 288130
Zahl der möglichen Kaffesorten (ohne Mahlgrade): 288130*378 = 108913140
So gaanz sicher bin ich mir aber zugegeben noch nicht, muss ich dann Abends nochmal in Ruhe überdenken…
May 21st, 2008 at 12:40
@Till Wenn Du 3 mal ziehst, also 13*12*11, musst Du das noch durch die Anzahl der Reihenfolgen teilen. Davon gibt es 3*2*1. Das ist genau der Binomialkoeffizient (3 aus 13) = 13!/(10!*3!) = 13*12*11/(3*2*1)
May 21st, 2008 at 12:42
Ich liege ja schon ziemlich nah an Cedric’s Zahlen
May 21st, 2008 at 12:50
Kombinationsmöglichkeiten
1/1: 9!/(1!*8!) = 9
1/2: 10!/(2!*8!) = 45
…
1/12: 20!/(12!*8!) = 125.970
Jetzt muss man alle übereinstimmenden Ergebnismengen subtrahieren, z.B. stimmt 5/10 mit 1/2 überein und muss somit aus der Menge von 1/10 entfernt werden.
Dann kommt man auf die Zahlen, die in der zweiten Spalte auf einem Schreibtisch stehen.
Die muss man dann nur noch addieren und mit dem Aroma multipliziert werden.
Deine Rechnung ist wie gesagt falsch, weil sie doppelte Teilmengen zulässt: z.B. Sorte 1 & Sorte 2, sowie Sorte 2 & Sorte 1.
Du rechnest damit ja nichts anderes als: 13! / 10!
Du solltest jedoch von diesem Ergebnis die doppelten Abziehen und das machst du, indem du die Fakultät der Anzahl der verfügbaren Stellen mit dem Nenner multiplizierst. In diesem Fall 3!
Darauf folgt: 13! / (10! * 3!)
Ich hoffe, das hat das ganze ein Bisschen klarer gemacht. Kann das leider nicht besser erklären, da ich mir das auch nur selbst beigebracht habe.
Schöne Grüße,
Cedric
May 21st, 2008 at 13:02
@Björn Was mich verwundert ist, dass die die vollen Ergebnisse mehrmals abziehst. Wenn Bei 8 zum Beispiel, die Ergebnisse von 4 vorkommen, ist das klar, dass die auch die von 2 Enthalten, weil 4 wiederum eine Potenz von 2 ist. Damit hast du die Ergebnismenge von: 11112222, ja gleich zwei mal abgezogen. Einmal als 1/2 und 1/2 und einmal als 2/4 und 2/4, dabei unterscheiden die sich in der Menge von 8 nicht…
May 21st, 2008 at 13:06
@Björn Du bist freiberuflicher Mathematiker? Krass.
Dann liege ich ja mit meinem Lösungsansatz einigermaßen richtig.
May 21st, 2008 at 13:11
@Cedric: da hast Du wohl Recht, danke! Das betrifft wohl die 2 aus 8, 1 aus 8, 1 aus 9 und 1 aus 10, oder übersehe ich was? Also 45+9+9+9 = 72 zu viel abgezogen. Neue Rechnung: 108940356 = (288130+72)*378
Immer noch nicht das gleiche Ergebnis wie Deins
May 21st, 2008 at 13:12
@Cedric: nein, leider nur freiberuflicher Software-Entwickler. Ich habe Mathematik studiert (hab das Diplom), aber das ist einige Jahre her. Ausserdem verrechnen Mathematiker sich gerne…
May 21st, 2008 at 13:16
@Björn: Ist ja toll.
Ich habe mein Ergebnis noch mal überdacht und komme auf eine kleine Änderung: 288.166 - Die sieht auf jeden Fall schön aus. Und ich meine, dass die sogar stimmen müsste.
May 21st, 2008 at 13:28
Hm, noch mal ein Korrekturvorschlag:
288.202 - jetzt auch mit den richtigen Zahlen im Zwischenspeicher.
1: nichts
2: 1
3: 1
4: 2,1
5: 1
6: 3,2,1
7: 1
8: 4,2,1
9: 3,1
10: 5,2,1
11: 1
12: 6,4,3,2,1
Bitte die Reihenfolge beachten. Das ist eine leichte Fehlerquelle.
Man muss die bereits subtrahierten Werte nutzen, sodass nicht doppelt abgezogen wird.
Grüße Cedric
May 21st, 2008 at 13:29
Ich komme auf 288130 Kaffee Kombinationen.
Der Ansatz:
Ich bleibe bei der Methode “Ungeordnete Ziehung, mit Zurücklegen”, also ((N + k - 1) über k) wobei N die Anzahl der Wahlmöglichkeiten ist und k die Anzahl der gezogenen Werte.
Nun können wir aber nicht nur genau 12 Mal wählen sondern bis zu zwölf mal, was wieder das Äquivalenzproblem erzeugt. Das ist aber sehr viel einfacher zu Lösen als mal gedacht.
Wenn wir x Mal ziehen, generieren wir damit auch alle Lösungen die wir erhalten können wenn wir y mal ziehen, wenn y ein teiler von x ist.
Wir können also bei 12 Mal ziehen anfangen, und notieren uns welche anderen Ziehungen wir schon abgedeckt haben. Sobald wir eine vollständige Abdeckung haben ziehen wir einfach die überschüssigen, also mehr als einmal abgedeckten, wieder ab und erhalten so ein Ergebnis.
Wir interessieren uns also für die folgenden Ziehungen:
12x, 11x, 10x, 9x, 8x, 7x und müssen die folgenden überschüssigen wieder abziehen: 4x, 3x, 2*2x und 5*1x
Diese zahlen setzen wir jetzt jeweils als k in die Formel oben ein(mit N = 9) und erhalten 288130 Kombinationen
Und da es 378 Aromakombinationen gibt, bedeutet das das ihr 108913140 verschiedene Kaffees anbietet.
Oder anders: Wollte man jeden Sonntag Morgen einen anderen probieren, müsste man etwa 2 Millionen Jahre alt werden.
May 21st, 2008 at 13:33
Muss mich leider bis heute Abend (oder eher Nacht) ausklinken, aber hat Spass gemacht bis jetzt!
May 21st, 2008 at 13:35
@Cedric ah, sehe gerade dass wir jetzt beim selben Ergebnis angelangt sind
@Jan: Du hast denke ich noch denselben Fehler drin wie ich zunächst, siehe Cedrics Kommentar dazu.
May 21st, 2008 at 13:35
Wie ich grade sehe stimme ich also (unabhängig) mit Björns erstem Ergebnis überein, mit dem gleichen fehler
(Ziehwerte: 12x, 11x, 10x, 9x, 8x, 7x und wieder abziehen: 4x, 3x, 2x und 2*1x)
Erhalte korrigiert: (wie Cedrik) die 288.202
May 21st, 2008 at 13:37
Yes, yes, yes. Ganz großes Kino.
Die bestätigten Zahlen: http://www.flickr.com/photos/cedricmay/2511358682/
May 21st, 2008 at 13:43
@Cedric: Dein Rechenweg ist mir zwar noch nicht ganz klar, aber nachdem wir jetzt alle 3 auf dasselbe Ergebnis gekommen sind, muss es doch eigentlich richtig sein. Mathe kann doch doch Spass machen, oder nicht?
May 21st, 2008 at 13:44
Die (korrigierte) Zusammenfassung:
SonntagMorgen bietet 108940356 verschiedene Mischungen (in vier Mahlgraden) an.
Tester die jede Woche eine neue Mischung ausprobieren möchten brauchen also wirklich 2 Millionen Jahre.
May 21st, 2008 at 13:54
Stimmt. =)
So, jetzt ist meine Ritter SPORT Neapolitaner Waffel auch aufgefuttert, jetzt kann ich kein Mathe mehr machen. =)
May 21st, 2008 at 14:23
Hätte jemand daran Interesse, wenn ich das filmtechnisch zusammenfasse und erkläre, wie man mathematisch zu dem unglaublichen Ergebnis von 100 Millionen Kombinationsmöglichkeiten kommt?
Grüße aus dem fast sonnigen Köln,
Cedric
May 21st, 2008 at 14:26
Es gibt auf jeden Fall noch nicht genug Mathefilme, also nur zu!
May 21st, 2008 at 20:20
Herzlichen Dank an dieser Stelle an alle, die mitgemacht haben. Cedric ist zuerst auf eine nachher von allen akzeptierte Lösung gekommen, mag aber keinen Kaffee. Daher gehen Preise an Björn und Jan. Herzlichen Glückwunsch!
May 21st, 2008 at 21:03
Glückwunsch an Cedric - und ja, ich will den Mathe-Film!
June 18th, 2008 at 20:40
Na dann mal zum Wohl!
und wie lange dauert es, wenn wir jeden Tag eine Sortenkombi probieren wollen???
June 19th, 2008 at 16:04
298.262 Jahre, 5 Monate und 9 Tage, so ungefähr.