SpinnenwebIn de lessen over telproblemen gaat het meestal over kiezen, bijvoorbeeld: ”Op hoeveel manieren kunnen we \(p\) objecten kiezen uit een voorraad van \(n\)?”. In iets minder klassieke vraagstellingen gaat het over het verdelen van \(p\) objecten over \(n\) locaties, bijvoorbeeld: ”Op hoeveel manieren kunnen we vijf muntstukken verdelen over drie spaarvarkens?”.
De context van de muntstukken en de spaarvarkens is nogal oubollig. Moderne (groot)ouders werken wellicht al met bitcoins of schrijven zakgeld over van bankrekening naar bankrekening. De vraag wordt hierdoor zeker niet minder interessant. In dit spinnenwebartikel interpreteren we het vraagstuk van de spaarvarkens namelijk op vier verschillende manieren en komen we tot vier verschillende antwoorden. Sommige berekeningen zijn triviaal, andere uiterst moeilijk. Kleine nuanceringen in een vraagstuk kunnen dus grote verschillen teweegbrengen. Het is aan ons om de leerlingen alert te maken voor deze subtiele inhoudelijke verschillen in de interpretatie van een telprobleem.
Concreet: zonder bijkomende informatie over de muntstukken en de spaarvarkens is deze telvraag niet eenduidig te beantwoorden. Uit de formulering hierboven is immers niet duidelijk af te leiden of de muntstukken verschillend zijn, bijvoorbeeld eentje van €2, eentje van €1, eentje van 50 cent, eentje van 20 cent en een van 10 cent. En ook niet of de spaarvarkens onderling verschillen (van kleur, van vorm, van eigenaar ….). Zo ontstaan er vier interpretaties: gelijke munten en gelijke varkens, gelijke munten en ongelijke varkens, ongelijke munten en gelijke varkens, ongelijke munten en ongelijke varkens.
Vijf verschillende munten verdelen over drie verschillende varkens
Dit is de eenvoudigste variant op het vraagstuk. De munt van €2 kan in elk van de drie varkens belanden. De munt van €1 kan ook in elk van de drie varkens gestopt worden, … De productregel leert ons dat er voor de vijf munten \(3 \times 3 \times 3 \times 3 \times 3\) of 243 mogelijkheden zijn om ze in de spaarvarkens te droppen.
Figuur 1 Verschillende munten en verschillende spaarvarkens (AI-afbeelding)
Met één enkele formule zijn we klaar, die van de herhalingsvariatie:
\(\overline{V}_3^5=3^5=243.\)
Vijf identieke munten verdelen over drie verschillende varkens
Deze situatie associeer ik daarom blindelings met het berekenen van herhalingscombinaties.
\(\overline{C}_3^5=21\)
Figuur 2 Identieke munten en verschillende spaarvarkens (AI-afbeelding)
Voor wie het begrip herhalingscombinatie niet kent, is de situatie iets moeilijker te modelleren. We kunnen dan teruggevallen op gewone combinaties. Hiervoor kan het volgende kneepje gebruikt worden. Zet vijf stippen en twee verticale balkjes in een bepaalde volgorde op een rij om de munten te verdelen.
De stippen stellen de identieke munten voor. De stippen aan de linkerkant van het linkse verticale balkje corresponderen met de munten voor spaarvarken 1. De stippen aan de rechterkant van het rechtse verticale balkje corresponderen met de munten voor spaarvarken 3. En de munten tussen de twee verticale balkjes komen toe aan het middelste spaarvarken.
Figuur 3 Symbolische verdeling van de munten over de spaarvarkens
Een handige manier om een verdeling van de munten vast te leggen is door het kiezen van de posities van de twee verticale balkjes. Voor elk van de twee balkjes zijn er 7 posities beschikbaar. De balkjes mogen niet dezelfde positie innemen, ze mogen wel onmiddellijk naast elkaar staan. De volgorde van het kiezen van de balken heeft niet het minste belang. Zo is het duidelijk dat het aantal mogelijkheden voor de posities van de twee balkjes berekend wordt met de formule voor combinaties:
Vijf verschillende munten verdelen over drie identieke varkens
Figuur 4 Verschillende munten verdelen over identieke spaarvarkens (AI-afbeelding)
We stappen nu over naar de moeilijkste variant: verschillende munten en gelijke spaarvarkens. Deze vraag is niet ogenblikkelijk op te lossen met een gekende combinatorische formule. Als je leerlingen een uitdaging aankunnen, laat ze dan een nachtje denken over dit probleem. Er zijn meerdere denkpistes mogelijk om tot een correct antwoord te komen. Ik stel er twee voor.
Eerste methode
Stel dat we de eerste munt en de tweede munt niet in hetzelfde spaarvarken stoppen. Dan ziet de situatie er uit als in Figuur 5.
Figuur 5 Situatie 1
Hoewel de varkens oorspronkelijk gelijk waren (even dik, even zwart, dezelfde krul in de staart) zijn ze nu verschillend. Eentje heeft een nummer 1, de volgende draagt nummer 2 en de laatste is ongenummerd. Er blijven nu drie verschillende munten over en die moeten verdeeld worden over drie ”verschillende” varkens. Zoals we eerder opmerkten kan dat op \(\overline{V}_3^3=3^3=27\) manieren.
Stel dat de eerste en de tweede munt wel in hetzelfde spaarvarken belanden en dat de derde munt niet in dit spaarvarken gestopt wordt. Dan wordt de situatie beschreven zoals in de figuur hieronder.
Figuur 6 Situatie 2
De spaarvarkens verschillen ook ditmaal onderling door rijkdom aan bijeengespaarde munten. Er moeten nu nog twee verschillende munten in de gleuf van drie verschillende spaarvarkens gestopt worden. Dat kan op \(\overline{V}_3^2=3^2=9\) manieren.
Situatie 3 is die waarbij de eerste, tweede en derde munt in hetzelfde spaarvarken verdwijnen en de vierde in een ander, zie Figuur 7. En zo gaat het door tot en met de situatie waarbij alle munten in hetzelfde varken verdwijnen.
Figuur 7 Situatie 3
We berekenen het antwoord op deze verdelingsvraag door de antwoorden van vijf situaties te sommeren. Er zijn dus \(27+9+3+1+1=41\) muntverdelingen van 5 verschillende munten over 3 gelijke varkens.
Tweede methode
De methode hierboven eindigde met (op de laatste term na) een som van opeenvolgende termen van een meetkundige rij. Er bestaat een compacte formule om deze som snel uit te rekenen. Vermoedelijk bestaat er dan ook een compacte redenering om het antwoord op deze vraag sneller te achterhalen. We proberen hier dus een handige redenering uit die geen gebruik maakt van de somformule.
Stel dat we eventjes halt houden nadat de eerste munt in een spaarvarken is gestopt. Een van de varkens onderscheidt zich dan duidelijk door zijn inhoud. De twee andere zijn identiek. Hieraan kunnen we verhelpen door een van beide dubbelgangers tijdelijk wit te kalken zoals op Figuur varkens8}. Na een korte redenering hieronder moet dit varkentje gewassen worden zodat alle varkens weer zwart zijn.
Figuur 8 Het rechtse varken is witgekalkt
Nu de drie varkens verschillend zijn, vinden we het aantal manieren om de vier overblijvende munten te verdelen met de formule
\(\overline{V}_3^4=3^4=81\).
Figuur 9 Twee muntverdelingen die identiek worden nadat het witgekalkte varkentje gewassen is
Als het witgekalkte varkentje weer zwart gemaakt wordt, zijn deze twee situaties identiek. Dit voorbeeld suggereert dat we alle muntverdelingen twee keer geteld hebben en dat we het antwoord 81 nog moeten delen door twee. ”Klopt niet”, merk je op, ”want 81 is oneven”. En gelijk heb je. Er is één situatie die niet dubbel geteld is bij het zwartmaken van het witte varkentje. Dat is degene waarbij alle munten in het linkervarken zitten.
Om het juiste antwoord te vinden, haal je deze muntverdeling van de 81 af, deel je door twee en stop je deze speciale muntverdeling er weer bij. In totaal heb je dan 41 manieren om 5 verschillende munten over drie identieke varkens te verdelen. Misschien vind je deze redenering iets lastiger. Maar je zal moeten toegeven dat er nu minder gerekend moet worden.
Deze benadering maakt het ook mogelijk om een formule te vinden voor het aantal verdelingen van \(n\) verschillende munten over drie identieke spaarvarkens. Dit aantal is \(\frac{3^{n-1}+1}{2}\). Vergis je echter niet in de moeilijkheidsgraad van zulke uitbreidingen. Als je een gelijkaardige vraag wil oplossen met vier identieke spaarvarkens, ben je er nog lang niet uit. Geef een seintje als je hiervoor een snedige redenering hebt gevonden.
Vijf gelijke munten verdelen over drie identieke varkens
Deze situatie kan je gewoon uittellen zonder formules te gebruiken. Er zijn 5 manieren om 5 identieke munten over 3 identieke spaarvarkens te verdelen. Maar een veralgemening van dit vraagstuk naar hogere aantallen munten en varkens loopt niet van een leien dakje.
Figuur 10 Identieke munten en identieke spaarvarkens (AI-afbeelding)
Er is in de literatuur wel wat bekend over het aantal manieren voor het verspreiden van \(n\) identieke munten over \(n\) identieke spaarvarkens. Dit aantal noemen we het aantal partities \(p(n)\) van \(n\).
We kunnen \(p(n)\) ook omschrijven al het aantal manieren waarop \(n\) als een som van gehele getallen kunnen schrijven. Het getal 5 kunnen we bijvoorbeeld op 7 manieren als een som schrijven:
Dus: \(p(5)=7\). Er zijn 7 manieren om 5 identieke munten over vijf identieke varkens te verspreiden. Van deze 7 manieren kunnen we er maar 5 gebruiken in een context met 5 munten en 3 spaarvarkens. De sommen 2+1+1+1 en 1+1+1+1+1 hebben meer dan drie termen en zijn dus niet geschikt voor een muntverdeling met 3 varkens. Dieper zullen we niet ingaan op partities van gehele getallen. Dit onderwerp laten we beter over aan universiteitsstudenten …
Verband tussen de vier problemen
[(*)] Je kiest 3 munten uit 5 zoals bij de lotto. Het maakt alleen niet uit welke je kiest en welke niet. Dat kan dus op \({5 \choose 3}=10 \) manieren. Die 3 munten stop je in een van de spaarpotten. De overige stop je in een andere spaarpot.
[(**)] Je kiest een varken waarin je 3 gelijke munten stopt. Dit kan op 3 manieren. Daarna kies je een ander varken om de twee overige munten in te stoppen. Daarvoor heb je telkens 2 mogelijkheden. In totaal heb je voor deze verdeling dus 6 mogelijkheden.
[(***)] Je kiest eerst 3 munten uit de 5. Dat kan op 10 manieren. Nu moet je de groepjes munten nog verdelen over de spaarpotten. Je kiest een eerste spaarpot voor het groepje van de drie munten (3 mogelijkheden), dan een tweede voor de eerste aparte munt (2 mogelijkheden) en de laatste munt gaat in de overblijvende spaarpot. Zo komen we aan \(10 \cdot 3 \cdot 2=60\) mogelijkheden.
[(****)] We starten weer met het kiezen van groepjes. Voor de keuze van 2 uit 5 vinden we 10 mogelijkheden en voor de keuze van 2 uit de overblijvende 3 vinden we 3 mogelijkheden. We zouden dan 30 mogelijkheden hebben maar we hebben elke verdeling in groepjes twee keer geteld. Er zijn dus 15 manieren om 5 munten in groepjes van 2, 2 en 1 te verdelen. Tot slot moeten de groepjes over de drie varkens verdeeld worden. Dat kan op \(3!=6\) manieren. Voor dit geval vinden we dus \(15 \cdot 6=90\) mogelijkheden.
Onder de loep
