Wiskundeforum

Een doos bevat n gekleurde ballen die elk een verschillende kleur hebben. Je neemt telkens 2 gekleurde ballen en verandert de kleur van de tweede bal in de kleur van de eerste bal. Hoeveel keer moet je gemiddeld dit proces herhalen eer alle ballen dezelfde kleur hebben?

wnvl schreef:Een doos bevat n gekleurde ballen die elk een verschillende kleur hebben. Je neemt telkens 2 gekleurde ballen en verandert de kleur van de tweede bal in de kleur van de eerste bal. Hoeveel keer moet je gemiddeld dit proces herhalen eer alle ballen dezelfde kleur hebben?

+20 ballen
bij 24 ballen = 12 kleuren na 1 keer
24 ballen 12 kleuren
optimaal blijven er 6 kleuren over
in slechtste geval blijven er 12 kleuren over
6+12 = 18 , 18/2 = 9
hieruit kan je afleiden dat het steeds 3/4 kleuren gemiddeld overblijven
aangezien het gemiddeld is moet je niet afronden naar volledige getallen.

24 → 12 , 9 , 6,75 , 5,0625 , 3,796875 , 2,84765625 , 2,1357421875 , 1,601806640625 , 1,20135498046875 , 0,90.... = 10 keer bij 24 ballen, bij 32 ballen 11 keer enz....

Mogelijk is de vraag verkeerd begrepen. Na 1 keer zou je vertrekkend van 24 kleuren. 23 kleuren hebben. Van 1 kleur zou je 2 ballen hebben.

Een eerste aanzet.

Ik ga uit van een van de kleuren, zeg wit.
Alle kleuren die niet wit zijn noem ik zwart. (zwart = niet-wit)

Het "spel" kan eindigen (als het al ooit eindigt) in alles wit of alles zwart (=alle witten foetsie).

E(k) is verwachte aantal zetten om k witten te krijgen.

E(k+1) = E(k).k(n-k)/n² + E(k+2).(k+2)(n-k-2)/n²
randvoorwaarden daargelaten.

E(0) en E(n) zouden hieruit berekend kunnen worden.

Het wordt nu iets te heet in de kamer en dus ook in mijn bovenkamer, dus tot zover.

Met simulatie: (n - 1)^2? De resultaten liggen er erg dichtbij.

[b][color=#8400BD]op=op[/color][/b] schreef:...(als het al ooit eindigt)...

Ik denk dat het te bewijzen is met een Markovketen dat het proces ooit eindigt.

De toestanden zijn de partities van n.
Dus als n = 5 zijn de toestanden:
5, 1 + 4, 2 + 3, 1 + 1 + 3, 1 + 2 + 2, 1 + 1 + 1 + 2, 1 + 1 + 1 + 1 + 1. (7 toestanden).
Elke term stelt een andere kleur voor. De waarde van de term zegt hoe vaak een kleur voorkomt.
Een 'stap' die wnvl hierboven beschreef is hier als volgt:
Kies twee verschillende termen (onthoud volgorde). Trek van de eerste term 1 af. Tel bij de tweede term 1 op. Als de eerste term nul is, neem het niet mee in de som.

Op deze manier kan een transitiematrix worden opgesteld met op de diagonaal een 1 (voor partitie 'n'). Daarmee is bewezen dat het proces eindigt.

Die opgave dateert al van bijna 3 jaar geleden en intussen ben ik zelf vergeten wat de oplossingsstrategie was. Ik herinner me wel dat er een hele mooie oplossing was. Ik zoek zelf ook terug verder.

Het was een licht aangepaste variant op een bestaand probleem uit de literatuur. Ik was er opgekomen in het kader van een poging om een Project Euler probleem te verzinnen.

David schreef:
[b][color=#8400BD]op=op[/color][/b] schreef:...(als het al ooit eindigt)...
Ik denk dat het te bewijzen is met een Markovketen dat het proces ooit eindigt.

Het proces hoeft niet te eindigen, het verwacht aantal trekkingen zal wel eindig zijn.

Het is inderdaad een Markov proces, Maar alle toestanden uitwerken is niet doenbaar.

David schreef:Met simulatie: (n - 1)^2? De resultaten liggen er erg dichtbij.

Zou heel goed kunnen dat dit juist is. De oplossing was relatief eenvoudig.

[color=#8400BD][b]wnvl[/b][/color] schreef:Ik herinner me wel dat er een hele mooie oplossing was.

Het is ook een mooi probleem!

[color=#8400BD][b]wnvl[/b][/color] schreef:Het proces hoeft niet te eindigen...

De kans dat het niet eindigt is 0, dus we kunnen toch zeggen dat het eindigt? Het is als de vraag:
(Veronderstel onbeperkt leven, energie en doorzettingsvermogen etc.) Gooi een dobbelsteen tot je 6 gooit. Stop je ooit? Ik denk 'ja'.

[color=#8400BD][b]wnvl[/b][/color] schreef:...Maar alle toestanden uitwerken is niet doenbaar.

Er zijn evenveel toestanden als partities van n, waarvan een tabel hier staat.

[color=#8400BD][b]wnvl[/b][/color] schreef:De oplossing was relatief eenvoudig.

Stel R(n) is het verwachte aantal stappen uit de oplossing. Is het misschien op te lossen door te kijken naar n kleuren waarvan een kleur twee keer voorkomt? Die toestand is na een stap vanaf n + 1 verschillende kleurende ballen die elk een keer voorkomen.

[color=#8400BD][b]wnvl[/b][/color] schreef:Het was een licht aangepaste variant op een bestaand probleem uit de literatuur. Ik was er opgekomen in het kader van een poging om een Project Euler probleem te verzinnen.

Heb je hier (na die tijd) nog links voor?

Ik schreef: Er zijn evenveel toestanden als partities van n, waarvan een tabel hier staat.

Zonder onderzoek naar de praktijk, kan dit probleem worden gesplitst in het verwachte aantal stappen om een kleur kwijt te raken. Dit geeft n - 1 transitiematrices met stadia partities van k en k + 1 met 1 <= k <= n-1, maar veel minder velden per matrix en in het totaal. (Zie rij http://oeis.org/A008284)

David schreef:
Zonder onderzoek naar de praktijk, kan dit probleem worden gesplitst in het verwachte aantal stappen om een kleur kwijt te raken.

Met partities werken wordt veel te ingewikkeld. Wat me wel bekoort is na te gaan in hoeveel stappen een kleur verdwijnt.
Laten we zeggen kleur wit.
Het doet er dan niet toe hoe de anderen gekleurd zijn. Je hoeft je allleen maar te concentreren op het aantal witten.
Dit lijkt me uit te rekenen.

De vraagt die dan volgt is, wat is het aantal stappen opdat 2 kleuren verdwijnen.
In dat geval mogen de twee kleuren 1 naam geven, zeg wit en de overigen afdoen met kleur zwart.

enz.

[color=#8400BD][b]op=op[/b][/color] schreef:Met partities werken wordt veel te ingewikkeld.

Waarschijnlijk wel, maar ik zie even geen andere manier (en het geeft me wat oefening).

[color=#8400BD][b]op=op[/b][/color] schreef:Het doet er dan niet toe hoe de anderen gekleurd zijn.

Reductie naar twee kleuren kan een mooie vereenvoudiging zijn, maar hoe zit het als wit niet verdwijnt maar als laatst overblijft? Het lijkt me dat als je een kleur kiest waar je bijhoudt hoe lang het duurt voor die verdwijnt, je een ander resultaat krijgt dan als je wacht tot er een willekeurige kleur verdwijnt.

Weer een simulatie gedraaid, dit keer om te bepalen hoeveel stappen het duurt om met n ballen van k naar k - 1 verschillende kleuren te gaan. Het lijkt erop dat dat naar verwachting gebeurt in $\frac{{n \choose 2}}{{k \choose 2}}$ stappen met 2 <= k <= n.

Hieronder is de code, voor PARI/gp: http://pari.math.u-bordeaux.fr/, voor wie wil herproduceren/inspecteren o.i.d.

Code: Selecteer alles

addhelp(mainstep, "Matrix met in de m-de rij 'gemstep' voor m + 1 ballen.")
mainstep(n) = {
m=matrix(n-1,n-1);
for(i=2,n,
	r=gemstep(i,1e5);for(j=1,#r,m[i-1,j]=r[j])
);m
}

addhelp(gemstep, "Voor n elementen. Het 1e element geeft het gemiddeld aantal stappen om de eerste kleur te verliezen, het tweede element (if there) de tweede kleur etc.")
gemstep(n,{q=10000}) = 1.*sum(i=1,q,boxstep(n))/q

addhelp(boxstep,"box met n verschillende kleuren. Resultaat: vector met aantal stappen om een 1..n-1 kleuren te verliezen")
boxstep(n) = {my(v=vector(n,i,i),t,r=vector(n-1),q=n);
while(#Set(v)>1,
	v = iteratie(v);t++;
	if(#Set(v)<q,r[n+1-q]=t;t=0;q--)
);r
}
addhelp(iteratie,"uit de 'bak met ballen', pak twee (verschillende!) ballen, en geef het eerste de kleur van het tweede.")
iteratie(v) = {
my(i1 = random(#v)+1,
   i2 = random(#v)+1);

while(i1==i2,
	i2=random(#v)+1;
);

v[i1]=v[i2];v
}

(mainstep(3) duurde ongeveer 3 seconden, mainstep(20) ongeveer 70 minuten.)

Bovenstaande is equivalent met:

$\sum_{k=2}^{n} \frac{{n \choose 2}}{{k \choose 2}} = (n-1)^2$
(voor n > 0).
Het bewijs van gelijkheid is denk ik tweeledig. We kunnen ${n \choose 2}$ buiten de som halen, en kijken wat $\sum_{k=2}^{n} \frac{1}{{k \choose 2}}$ geeft.
Inspectie doet vermoeden: $\frac{2n - 2}{n}$ .

Met inductie:
Voor n = 1 hebben we in het linkerlid de lege som, ofwel 0. Rechts hebben we (2 * 1 - 2)/1 = 0. Dus waar voor n = 1.

$\sum_{k=2}^{n+1} \frac{1}{{k \choose 2}} \\\\ = \frac{1}{{n+1 \choose 2}} + \sum_{k=2}^{n} \frac{1}{{k \choose 2}} \\\\ = \frac{2}{n(n+1)} + \frac{2n - 2}{n} = \frac{2}{n(n+1)} + \frac{(2n - 2)(n+1)}{n(n+1)} \\\\ = \frac{2}{n(n+1)} + \frac{(2n - 2)(n+1)}{n(n+1)} \\\\ = \frac{2n^2 - 2n + 2n - 2 + 2}{n(n+1)} \\\\ = \frac{2n}{n + 1} = \frac{2(n + 1) - 2}{n+1}$
Dat voor het eerste deel.

Nu, $\sum_{k=2}^{n} \frac{{n \choose 2}}{{k \choose 2}} = {n \choose 2} \cdot \frac{2n - 2}{n} = \frac{n(n-1)}{2} \cdot \frac{2n-2}{n} = (n-1)^2$ .
Dat was te bewijzen.

De gevonden resultaten spreken elkaar in ieder geval niet tegen.

Wiskundeforum

gekleurde ballen [20+]

gekleurde ballen [20+]

Re: gekleurde ballen [20+]

Re: gekleurde ballen [20+]

Re: gekleurde ballen [20+]

Re: gekleurde ballen [20+]

Re: gekleurde ballen [20+]

Re: gekleurde ballen [20+]

Re: gekleurde ballen [20+]

Re: gekleurde ballen [20+]

Re: gekleurde ballen [20+]

Re: gekleurde ballen [20+]

Re: gekleurde ballen [20+]

Re: gekleurde ballen [20+]

Re: gekleurde ballen [20+]

Re: gekleurde ballen [20+]