matematikk.net

Denne oppgaven var en litt vanskeligere oppgavene som ble gitt i elementær diskret matematikk for de som ville bryne seg litt.

Du står foran et hus med 100 etasjer og får utdelt to og bare to identiske
klinkekuler. Vi skal finne ut hva som er den laveste etasje der en klinkekule
knuses hvis den slippes ut av vinduet.

Hva er det minste antall forsøk som trengs for alltid å finne denne kritiske etasjen der kulene knuses?

(Vink: Det kan være nyttig å kjenne til velordningsprinsippet: Enhver ikketom
mengde av naturlige tall inneholder et minste tall.)


(edit, noe av teksten var overflødig og derfor kuttet bort)
(kilde http://www.math.ntnu.no/emner/MA0301/2008v/ )

Feiltolket oppgaven...

Max 19 forsøk.

Hvis man startert fra 10. etg og går ti og ti etasjer inntil den første knuser, deretter begynner man 9 etasjer under denne og slipper den fra en og en etasje oppover inntil den knuser.
Altså testes det fra {10,20,30,40,50,60,70,80,90,100} deretter {x1,x2,x3,x4,x5,x6,x7,x8,x9} avhengig hvor den første knuses.

en formel for utregning av max forsøk [tex] f(n)=\text{floor}(\frac{100}{n}) + n - 1 + n\cdot(\frac{100}{n}-\text{floor}(\frac{100}{n})) [/tex]
der n antal økning i etasjer på første kule.

fyller vi inn funksjonen med tallene{1,2,3,4,5,6,7,8,9,10,11,12}
så får vi resultatet {100,51,36,28,24,25,22,23,20,19,20,23}

Dette er selvfølgelig absolutt max antall forsøk dersom kula knuses fra f.eks. 99.etg. Man kan jo ha flaks at den knuser allerede fra 1. etg.

Det er mulig å gjøre det bedre enn max 19 forsøk.

mrcreosote wrote:Det er mulig å gjøre det bedre enn max 19 forsøk.

Fortell.

Start med å slippe fra 14. etasje, da kan du klare deg med max 14 slipp. Hva er neste trekk?

Flaut. Jeg tenkte litt for linjært.

Neste stepp er 27. etasje. På den måten kan man faktisk sjekke det på et bygg på 105 etasjer med 14 forsøk.

[tex]\sum_{n=1}^{14}\ n[/tex]

Det må da være mulig å gjøre det langt bedre enn på 14 forsøk

Men 14 er absolutt maksimalt da.