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.
Börjar man på våning 12 och har max 13 försök på sig, så kan man max komma upp i våning 12+12+11+10+9+8+7+6+5+4+3+2+1 = 90 med första nöten om den aldrig går sönder, och sedan har man inga försök kvar.
Men om man testar 12,24,36 osv och ifall det går sönder testar man varannan. Dvs går sönder på 36 så testar man 26,28,30,32.
Testar man varannan och den andra nöten går sönder på t.ex. 32, så har man inga nötter kvar och kan inte bestämma huruvida 31 eller 32 är gränsen för var de börjar gå sönder.
En enda gång. Han bara släpper kokosnöten från antingen markvåningen eller första våningen (kokosnötterna är hårda).
Ursäkta, men vad menas rent språkligt med frågan? ’100 våningar och 2 nötter tillgodo’? Var anges hur många nötter apan har från början?
snälla kan lösningen komma snart
Nu finns lösningen, ursäkta förseningen!
Hej! 13 borde väl funka om man börjar på v 12?
Börjar man på våning 12 och har max 13 försök på sig, så kan man max komma upp i våning 12+12+11+10+9+8+7+6+5+4+3+2+1 = 90 med första nöten om den aldrig går sönder, och sedan har man inga försök kvar.
Men om man testar 12,24,36 osv och ifall det går sönder testar man varannan. Dvs går sönder på 36 så testar man 26,28,30,32.
Testar man varannan och den andra nöten går sönder på t.ex. 32, så har man inga nötter kvar och kan inte bestämma huruvida 31 eller 32 är gränsen för var de börjar gå sönder.
En enda gång. Han bara släpper kokosnöten från antingen markvåningen eller första våningen (kokosnötterna är hårda).
Ursäkta, men vad menas rent språkligt med frågan? ’100 våningar och 2 nötter tillgodo’? Var anges hur många nötter apan har från början?
Hej Anders!
Apan har två nötter från början.