Tack till David Nilsson som påminnt mig om en gammal klassiker!
Rekommenderad från: 13 år
En apa är i ett 100-våningshus och vill veta vilken den högsta våningen är som den kan släppa en kokosnöt ifrån utan att den går sönder när det träffar marken. Hur många gånger behöver apan testa att kasta ner en nöt för att garanterat ta reda på det, om den bara har två kokosnötter till godo?
Detta går att göra på 14 försök! Låt apan kasta första nöten från våning 14. Om den går sönder, behövs det maximalt 13 försök till med andra nöten, testa först våning 1, sedan våning 2 och så vidare upp till våning 13 om det behövs. Då vet man exakt när nötter börjar gå sönder.
Om första nöten inte går sönder, har man 13 försök kvar. Testa då första nöten på våning 14+13 = 27. Går den sönder där har man 12 våningar kvar att testa (från 15 till 26) successivt med andra nöten.
Om första nöten inte går sönder, har man 12 försök kvar. Testa då den på våning 14+13+12 = 39. Om den går sönder, behöver man göra max 11 försök med andra nöten på samma sätt som förut.
Algoritmen fortsätter så, sedan skulle man testa första nöten på våning 14+13+12+11=50, om det inte går sönder. Sedan på 14+13+12+11+10 = 60, sedan på 69, sedan på 77, sedan på 84, sedan på 90, sedan på 95, sedan på 14+13+12+11+10+9+8+7+6+5+4 = 99. Och om den inte går sönder då heller, så har man till och med tre försök kvar. Det sista man gör är att slänga första nöten (ifall den inte har gått sönder tidigare förut) på våning 100, för att se om kokosnötter går sönder när man släpper därifrån.
På så vis räcker det med 14 försök hur utfallet än blir!
Antag att det räcker med 13 (eller färre) försök. Då måste första försöker för första nöten ske på våning 13 eller mindre, annars räcker inte försöken till om första nöten går sönder. Om nöten inte går sönder, kan de andra försöket ske på högst våning 13+12, annars räcker inte försöken med andra nöten till om första nöten går sönder. Osv… 13:e försöket med första nöten kan ske på max våning 13+12+…+1 = 91. Om nöten inte går sönder kan inte vi bestämma vilken av de högre våningarna den borde gått sönder på. Därför räcker inte 13 (eller färre) försök.
