Betragt følgende spil: Man har en krukke med sorte og hvide kugler, dobbelt så mange hvide som sorte. To tilfældige kugler tages op. Hvis de er ens bliver de smidt væk, og man lægger en ny sort kugle ned i krukken. Hvis de er forskellige, smider man den sorte væk og lægger den hvide tilbage.
a) Skriv et iterativt program der indlæser antallet af sorte kugler og derefter simulerer ovennævnte spil indtil der kun er een kugle tilbage.
Hint: Gem de to antal kugler i to heltalsvariable, blacks og whites, som manipuleres på passende vis ved hvert gennemløb af en while-løkke.
Hint: Se afsnit 6.5 i CCJ3 hvor der er beskrevet hvordan man kan generere tilfældige tal.
b) Argumenter for at programmet altid standser.
Hint: Analogt til argumentationen for at Euklids Algoritme standser.
c) Hvad kan man sige om farven på den sidste kugle? Hvorfor det?
Hint: Argumenter omhyggeligt for, at hvis blacks og whites før et gennemløb af while-løkken begge er ikke-negative, og har en ganske bestemt anden egenskab, så er de også ikke-negative bagefter, summen af dem er positiv, og de har desuden stadig den efterlyste egenskab.