ballen
HELSINKI - Heerlijk - zaterdag. Deze week was weer bijzonder anstrengend. Ik heb gestreden, ik heb gevochten. Ik heb documenten geschreven - een heleboel. Maar donderdag was er een kick-off meeting voor een project waarin ik een rol speel. En we gingen... bowlen. En eten. De reden voor de foto is dat ik maar liefst 131 punten scoorde -- een persoonlijk record. Ik had geen tijd gehad om te lunchen, dus na een beetje bier was het gauw afgelopen met mijn geluk. En toen ik nog enkele clubspelers zag (met eigen bal!), moest ik toch weer enige bescheidenheid betrachten - die gingen allemaal ver over de 200 punten...

Vrijdag om negen uur had ik afgesproken met Ann-Christin voor de film Match Point van regisseur Woody Allen. De film was erg geslaagd, en verhaalt over een ex-tennisprof uit een arm milieu, die zich omhoog probeert te werken. Een verhaal rond geluk en ongeluk, liefde en leugen. Zeer duidelijk zijn ook de verwijzingen naar Dostojeski's Misdaad en Straf (dat ik drie jaar geleden las -- de tijd vliegt!). Laat ik verder niets zeggen over het plot - maar het was een intrigerende film. Goed genoeg om mijn ogen bij open te houden, op vrijdagavond, en dat zegt wat!

OK, eindelijk het antwoord op het raadsel met de biljartballen uit de vorige aflevering. Ik herhaal het nog eens:

Stel je voor: je hebt 8 biljartballen waarvan een zwaarder is dan alle andere, die hetzelfde gewicht hebben. Om te bepalen wat de zwaarste is, heb je de beschikking over een balans. Hoe vaak moet je wegen om de zwaarste te vinden?

Ik heb verschillende oplossingen gehoord... maar niet het juiste antwoord: 2 maal. Interessant is natuurlijk hoe we tot dat antwoord komen. Een mogelijk antwoord zou kunnen zijn dat we het aantal ballen steeds halveren: je gaat steeds verder met de zwaarste kant van de balans. Dus 4 aan de ene, en vier aan de andere kant, en heb je 8...4...2...1 ballen en moeten we dus driemaal wegen...

Maar - we kunnen nog beter! De 'truc' is dat we de ballen niet in twee groepen, maar in drie groepen verdelen. Groep A en B worden vergeleken op de balans, en als die even zwaar blijken, zit de zwaardere kennelijk in groep C (de ballen die we terzijde gelegd hebben). In dit geval: we nemen twee groepen van drie ballen op de balans, en leggen er twee terzijde. Na eenmaal wegen, weten we of de zwaardere bal in groep A, B of C zat. Als groep C (die met twee ballen) de zwaardere bal bevatte, dan kunnen we die natuurlijk eenvoudig met nog eenmaal wegen vinden. Zat de zware bal in groep A of B, dan voeren we onze 'truc' nog maal uit: leg een bal terzijde en weeg de andere twee. Dus in alle gevallen kunnen we met tweemaal wegen de zware bal vinden. QED ;-)

Meer algemeen, we kunnen de ene zware bal uit n ballen met CEIL(³log n) maal wegen vinden. (Zelfs uit 9 ballen kun je met tweemaal wegen de zwaardere bal vinden!)

-- djcb @ 18:09 | 0 comments