*Szklana kula zrzucona z jakiegoś piętra \(\displaystyle{ n}\) piętrowego wieżowca może się rozbić. Zależy to nie od kuli, lecz od wysokości. Mamy \(\displaystyle{ k}\) takich kul. Należy ustalić minimalna ilość prób , które trzeba wykonać, zrzucając kule z pięter, aby zawsze wykryć numer najwyższego pietra, z którego zrzucona kula nie rozbije się.
Niech \(\displaystyle{ f(n, k)=m}\) to będzie szukaną ilością prób.
Jeśli jest tylko jedna kula, to należy sprawdzać czy się nie rozbije ostrożnie, tj. „od dołu” (przy „maksymalnym pechu” rozbije się ona dopiero rzucona z ostatniego piętra); tj. mamy \(\displaystyle{ f(n, 1) = n}\).
\(\displaystyle{ k=2}\)
Przykład
Obliczyć \(\displaystyle{ f(6,2)}\)
Jedna próba to za mało, ale dwie także (\(\displaystyle{ f(3,2)= 2}\)). Wystarczą jednak trzy próby (można zacząć od trzeciego piętra: jeśli kula się nie rozbije: to rzucić ją z piątego piętra...), tj. \(\displaystyle{ f(6,2)=3}\).
Można udowodnić, że \(\displaystyle{ f(n,2)= \rfloor \frac{\sqrt{8n+1}-1}{2} \lfloor}\)
gdzie \(\displaystyle{ \rfloor x \lfloor}\) oznacza najmniejszą liczbą całkowitą która jest nie mniejsza niż \(\displaystyle{ x}\).
Np. \(\displaystyle{ f(100, 2) = 14}\). Należy sprawdzać piętra: \(\displaystyle{ 14, \ 27, \ 39, \ 50, \ 60, \ 69, \ 77, \ 84, \ 90, \ 95 , \ 99, \ 100}\). np. jeśli po raz pierwszy kula rozbije się rzucona z 60-tego piętra (tj. po piątej próbie), to jest do sprawdzenia 9 pięter (od 51 do 59) itd.
Algorytm jest bowiem taki: zaczynamy od piętra o numerze \(\displaystyle{ m}\), potem z piętrem o numerze \(\displaystyle{ m + (m-1)=2m-1}\), potem z piętrem o numerze \(\displaystyle{ m + (m-1)+ (m-2)=3m-3}\) itd. z coraz mniejszymi o jeden skokami.
\(\displaystyle{ k=3}\)
Przykłady
Tu także obliczanie \(\displaystyle{ f}\) dla małych \(\displaystyle{ n}\) nie jest zbyt trudne i może być rozwijające. Mamy np. \(\displaystyle{ f(6,3)=f(7, 3)= 3}\) ale \(\displaystyle{ f(8,3)= 4}\) itd.
Okazuje się, że \(\displaystyle{ f(100, 3) = 9}\). Zacząć należy wpierw od pięter:
\(\displaystyle{ 37, \ 66, \ 88, \ 100}\)
W przypadku trzech kul pierwszą próbę należy wykonać z piętra \(\displaystyle{ \frac{(m-1)m}{2} + 1}\), kolejną z piętra \(\displaystyle{ \frac{(m-1)m}{2} + 1 +\frac{(m-2)(m-1)}{2}+1}\) itd.
Daje to wynik \(\displaystyle{ \frac{m(m^2+5)}{6} \geq n}\)
(przy \(\displaystyle{ m}\) tej próbie jesteśmy na ostatnim piętrze bądź „w chmurach”).
Co nie daje się tak łatwo „rozwikłać” jak dla dwóch kul. (\(\displaystyle{ \frac{m(m+1)}{2} \geq n}\)).
Zakończenie
W cytowanym artykule autor gustownie formułuje zagadnienie, wyprowadza wzory na dla \(\displaystyle{ k \in \{ 1, 2, 3 \}}\), nie zajmując się sytuacją \(\displaystyle{ k>3}\) oraz podaje wartości \(\displaystyle{ f}\) dla niektórych małych \(\displaystyle{ n}\) i \(\displaystyle{ k}\). Oblicza też wreszcie \(\displaystyle{ f(100,2)}\) i \(\displaystyle{ f(100, 3)}\).
Problemy
■ Jakie jest najmniejsze, a jakie największe \(\displaystyle{ n}\) takie, że \(\displaystyle{ f(n,2)=14}\) ?
■ Jak się stabilizuje (maleje) \(\displaystyle{ f}\) gdy wzrasta \(\displaystyle{ k}\), zaś \(\displaystyle{ n}\) jest ustalone; obliczyć \(\displaystyle{ f(100, k)}\) dla \(\displaystyle{ k> 3}\)
■ Być może nie istnieje wieżowiec z \(\displaystyle{ n> 206}\) pięter, ale istnieje gdy n=206 (tzw. Burdż Chalifa, ZEA); obliczyć \(\displaystyle{ f(206, 4)}\); zbadać głębiej sytuację z \(\displaystyle{ k=4}\)
■ pomijając realia z wieżowcami - czy można efektywnie obliczać \(\displaystyle{ f(n, k)}\) dla dużych wartości \(\displaystyle{ n}\) i \(\displaystyle{ k}\) ?
■ kontynuować własne badania nad własnościami funkcji \(\displaystyle{ f(n,k)}\)
*
Ukryta treść: