Submitted by Jens H. on
Ben De Bondt werd de winnaar van de laatste breinbreker van 2011-2012. Als prijs ontvangt hij een jaarabonnement op het tijdschrift Pythagoras en op het tijdschrijft Wiskunde & Onderwijs. Proficiat en veel leesplezier!
We kregen ook nog juiste inzendingen van Wouter van de Vijver, Jeroen Demeyer, Annelies Cuvelier, Thomas Cnops, Jasmine Maes, Stijn Cambie, Yannick Neyt en Reinout D'Haene.
Oplossing
Je hebt minimaal 10 worpen nodig.
Antwoord
Veronderstel dat we 1 bol hebben. Dan moeten we beginnen op het gelijkvloers en telkens 1 verdiep omhoog gaan: Slaan we een verdiep over en de bol breekt, dan kunnen we onmogelijk uitmaken of het dit verdiep of het verdiep eronder is, waar de bol eerst breekt. Hebben we een gebouw met n verdiepen, dan hebben we ook n worpen nodig.
Stel we hebben nu twee bollen. We stellen het minimaal aantal worpen gelijk aan $d$. Als eerste verdiep kiezen we verdiep $d$. Stonden we hoger en de bal brak, dan hebben we meer dan $d-1$ worpen nodig om alle verdiepen eronder te controleren (met 1 bol) of in het totaal meer dan $d$ worpen wat in contradictie is met het gestelde. Elk verdiep lager die we kiezen voor de eerste worp is minder efficiënt: we zouden dan nog worpen 'over' hebben. Als de bal breekt, gebruiken we onze 1-bal methode om de $d-1$ verdiepen eronder te controleren. Als de bal niet breekt, hebben we nog $d-1$ worpen over. Met dezelfde redenering gaan we nu $d-1$ verdiepen omhoog en komen op het $2d-1$ 'ste verdiep te staan. Op deze manier gaan we verder. Zo vinden we na sommatie dat we met d worpen, $\frac{d(d+1)}{2}$ verdiepen kunnen checken.
We hebben nu drie ballen. Opnieuw stellen we dat het minimaal aantal worpen d is. We kiezen nu onze eerste worp. Stel dat de bal breekt na 1 worp dan hebben we nog $d-1$ worpen en $2$ ballen. Hiermee kunen we $\frac{d(d-1)}{2}$ verdiepen controleren, dit volgt namelijk uit de situatie voor 2 bollen. We gaan dus op het $\frac{d(d-1)}{2}+1$ 'ste verdiep staan voor onze eerste worp. Breekt de bal niet, dan hebben we nog $d-1$ worpen over. Met dezelfde redenering gaan we nu $\frac{(d-1)(d-2)}{2}+1$ verdiepen omhoog. enzovoort. Met d worpen kunnen we, na alle stappen gesommeerd te hebben, $d+\frac{d(d-1)(d+1)}{6}$ verdiepen controleren. Het gebouw in kwestie heeft 162 verdiepen. Zodoende komen we met een minimaal aantal worpen van $d = 10$ toe om alle verdiepen te testen.