1162, topping och cupcakes

Fick det till 268. Har du skrivit av facit rätt?

PATENTERAMERA skrev:

Fick det till 268. Har du skrivit av facit rätt?

tindra03 skrev:

Om endast tre toppingar används så kan dessa väljas ut på 4 över 3 sätt (4 olika sätt). För varje kombination toppingar så kan dessa fördelas på cupcakesen på 3 över 10 olika sätt (kombinationer).

"n över k"-beräkningen heter på engelska "n choose k": Utav n element, på hur många sätt kan man välja ut k st av dem? Som i din första mening här. Det finns 4 toppingar, på hur många sätt kan man välja 3 av dem? Jo, 4 över 3 (vilket är 4). Men vad betyder då 3 över 10? Från 3 element, välj 10? Man kan inte plocka ut fler än vad som finns, så om "nämnaren" k är större än n blir "n över k" alltid 0. Kort sagt, det där är inte beräkningen du vill göra.

Kruxet här är att du kan ha olika antal cupcakes med varje topping. Man skulle kunna dela upp fallen i olika sätt att summera fyra heltal till 10. T.ex. 8-1-1-0: 8 av en sort, 1 av två olika sorter, och 0 av sista sorten. Sen för varje sånt val av "gruppstorlekar" räknar man hur många sätt man kan placera de fyra sorterna över de antalen: fyra sorter kan vara 8:an, sen finns 3 olika som kan vara nollan, och de två sista blir ettorna. Så 4*3 sätt. 

Men det blir stökigt och krångligt om man försöker reda ut allt den vägen, och facit visar ett knep för att lösa såna här uppgifter där man ska skapa grupper av (potentiellt) olika storlek, men där totala antalet alltid är samma (10). Metoden brukar kallas stars and bars.

Skaft skrev:

tindra03 skrev:

Om endast tre toppingar används så kan dessa väljas ut på 4 över 3 sätt (4 olika sätt). För varje kombination toppingar så kan dessa fördelas på cupcakesen på 3 över 10 olika sätt (kombinationer).

"n över k"-beräkningen heter på engelska "n choose k": Utav n element, på hur många sätt kan man välja ut k st av dem? Som i din första mening här. Det finns 4 toppingar, på hur många sätt kan man välja 3 av dem? Jo, 4 över 3 (vilket är 4). Men vad betyder då 3 över 10? Från 3 element, välj 10? Man kan inte plocka ut fler än vad som finns, så om "nämnaren" k är större än n blir "n över k" alltid 0. Kort sagt, det där är inte beräkningen du vill göra.

Kruxet här är att du kan ha olika antal cupcakes med varje topping. Man skulle kunna dela upp fallen i olika sätt att summera fyra heltal till 10. T.ex. 8-1-1-0: 8 av en sort, 1 av två olika sorter, och 0 av sista sorten. Sen för varje sånt val av "gruppstorlekar" räknar man hur många sätt man kan placera de fyra sorterna över de antalen: fyra sorter kan vara 8:an, sen finns 3 olika som kan vara nollan, och de två sista blir ettorna. Så 4*3 sätt. 

Men det blir stökigt och krångligt om man försöker reda ut allt den vägen, och facit visar ett knep för att lösa såna här uppgifter där man ska skapa grupper av (potentiellt) olika storlek, men där totala antalet alltid är samma (10). Metoden brukar kallas stars and bars.

Aha! Då förstår jag kanske vad du menar. Jag hittade en liknande tråd här på forumet (sökord 1162). Så varje ”avskiljare” mellan varje sort av dekoration ska räknas som ett objekt? Kommer då exempelvis:

|XXX|XXXXX|XX (dvs 0 av första, 3 av andra, 5 av tredje, osv)

fortfarande bli olika än

XX|XXXXX|XXX| (2 av första, 5 av andra, 3 av tredje, 0 av fjärde)

EDIT: om kakorna toppas från A till D (vänster till höger)

Pinnarnas ”mellanrum” blir densamma, men dess placering i förhållande till X-en blir annorlunda. Det blir fortfarande en kombination, och inte permutation eftersom | och X är skilda objekt, och inte ett ”paket” som ser ut exemeplvis |XXXXX eller |XXX. Men räknar alltså genom denna beräkning på hur många sätt som ”pinnarna” kan placeras  mot x-en? Eller tänker jag fel? Vad skulle isåfall permutationen betyda i detta fallet?

tindra03 skrev:

Kommer då exempelvis:

|XXX|XXXXX|XX (dvs 0 av första, 3 av andra, 5 av tredje, osv)

fortfarande bli olika än

XX|XXXXX|XXX| (2 av första, 5 av andra, 3 av tredje, 0 av fjärde)

Ja, de är olika. Man bestämmer att första gruppen är dekoration A, andra B osv. Så de där uppsättningarna skiljer sig åt, det är ju skillnad på att ha 0 A eller ha 2 A t.ex. =) Varje sätt att placera pinnarna på beskriver exakt ett sätt att fördela dekorationerna på. Det blir inga upprepningar, och inga fall missas heller. Det är alltså helt likvärdigt att räkna dekorationsfördelningar, som att räkna "på hur många sätt kan jag placera de 3 pinnarna?" Och att räkna det är som att välja "på hur många sätt kan jag välja 3 platser av 13", för de 3 platserna sätter du pinnar på.

Pinnarnas ”mellanrum” blir densamma, men dess placering i förhållande till X-en blir annorlunda. Det blir fortfarande en kombination, och inte permutation eftersom | och X är skilda objekt, och inte ett ”paket” som ser ut exemeplvis |XXXXX eller |XXX. Men räknar alltså genom denna beräkning på hur många sätt som ”pinnarna” kan placeras  mot x-en? Eller tänker jag fel? Vad skulle isåfall permutationen betyda i detta fallet?

Jag tänker på det som att man har 13 platser: -------------

3 av dessa ska bli pinnar, resten ska bli cupcakes. Eller vad man nu räknar på. Stjärnor, enligt det klassiska exemplet. Så jag väljer 3 platser, omvandlar dem till pinnar: ----|---|--|-

Och övriga platser omvandlas till stjärnor: ****|***|**|*

På så sätt har man bildat ett möjligt sätt att dekorera. 4 av första sorten, 3 av nästa osv. Permutationer är inget du vill blanda in här. Om du börjar permutera pinnarna t.ex. börjar du räkna om samma saker fast i en annan ordning. "4 A, 3 B, 2 C, 1 D" är ju fortfarande samma dekorationsfördelning som "2 C, 1 D, 4 A, 3 B". Det är bara ordningen man nämner dem som varierar då, och såna upprepningar vill vi inte få in.

Skaft skrev:

tindra03 skrev:

Kommer då exempelvis:

|XXX|XXXXX|XX (dvs 0 av första, 3 av andra, 5 av tredje, osv)

fortfarande bli olika än

XX|XXXXX|XXX| (2 av första, 5 av andra, 3 av tredje, 0 av fjärde)

Ja, de är olika. Man bestämmer att första gruppen är dekoration A, andra B osv. Så de där uppsättningarna skiljer sig åt, det är ju skillnad på att ha 0 A eller ha 2 A t.ex. =) Varje sätt att placera pinnarna på beskriver exakt ett sätt att fördela dekorationerna på. Det blir inga upprepningar, och inga fall missas heller. Det är alltså helt likvärdigt att räkna dekorationsfördelningar, som att räkna "på hur många sätt kan jag placera de 3 pinnarna?" Och att räkna det är som att välja "på hur många sätt kan jag välja 3 platser av 13", för de 3 platserna sätter du pinnar på.

Pinnarnas ”mellanrum” blir densamma, men dess placering i förhållande till X-en blir annorlunda. Det blir fortfarande en kombination, och inte permutation eftersom | och X är skilda objekt, och inte ett ”paket” som ser ut exemeplvis |XXXXX eller |XXX. Men räknar alltså genom denna beräkning på hur många sätt som ”pinnarna” kan placeras  mot x-en? Eller tänker jag fel? Vad skulle isåfall permutationen betyda i detta fallet?

Jag tänker på det som att man har 13 platser: -------------

3 av dessa ska bli pinnar, resten ska bli cupcakes. Eller vad man nu räknar på. Stjärnor, enligt det klassiska exemplet. Så jag väljer 3 platser, omvandlar dem till pinnar: ----|---|--|-

Och övriga platser omvandlas till stjärnor: ****|***|**|*

På så sätt har man bildat ett möjligt sätt att dekorera. 4 av första sorten, 3 av nästa osv. Permutationer är inget du vill blanda in här. Om du börjar permutera pinnarna t.ex. börjar du räkna om samma saker fast i en annan ordning. "4 A, 3 B, 2 C, 1 D" är ju fortfarande samma dekorationsfördelning som "2 C, 1 D, 4 A, 3 B". Det är bara ordningen man nämner dem som varierar då, och såna upprepningar vill vi inte få in.

Aha! Då förstår jag!