След хвърляне на първата топка, винаги има вероятност тя да се счупи, след което, за да сме сигурни че няма да счупим втората топка преди да сме намерили търсения етаж, се налага да я хвърляме последователно от етажа над най-високия "нечупещ", до този, от който сме хвърлили първата топка за последно (по този начин ще счупим втората топка непосредствено над етаж, от който сме проверили че топката издържа).

Стратегията е да се хвърли първата топка от k-тия етаж:

1.а) Ако се счупи от k-тия етаж, знаем че отговорът е между етажи 1 и k, и се налага да хвърлим втората топка най-много k-1 пъти. Намираме етажа в общо не повече от 1+(k-1)=k хвърляния.
1.б) Ако първата топка не се счупи от k-тия етаж, можем да я хвърлим от k-1 етажа по-високо, т.е. от етаж номер k+(k-1)

2.а) Ако се счупи от k+(k-1)-тия етаж, знаем че отговора е между етажи k+1 и k+(k-1), тоест с втората топка имаме още най-много [k+(k-1)]-(k+1)=k-2 хвърляния. Намираме етажа в общо не повече от 1+1+(k-2)=к хвърляния.
2.б) Ако първата топка не се счупи и от k+(k-1)-тия етаж, можем да я хвърлим от k-2 етажа по-високо, т.е. от етаж номер k+(k-1)+(k-2)...

И така, докато покрием всички 100 етажа.

Тоест, търсим най-малкото естествено к, за което к+(к-1)+(к-2)+...+(k-(k-1))>100

Забелязваме, че к+(к-1)+(к-2)+...+(k-(k-1)) е сумата на естествените числа от 1 до к, а тя е к(к+1)/2.

Значи, търсим най-малкото естествено к, за което к(к+1)/2>100.

kmin=14.

Be free, not cheap.

Редактирано от heptagram на 29.01.15 15:01.