Upuszczenie jajka do 100
Do przetestowania jest nowy typ pojemnika na jedno jajko. Dostajesz pojemnik, dwa jajka i dostęp do stupiętrowego budynku. Chcesz sprawdzić, jak wysoko możesz zrzucić jajko do jednego z tych pojemników, żeby się nie rozbiło.
Można po prostu zrzucić jajko z każdego piętra, zaczynając od parteru, i zobaczyć, gdzie jajko rozbije się za pierwszym razem. Jeśli jednak pojemniki są naprawdę dobre, oznaczałoby to sto zrzuconych jajek. Jak sprawdzić, jak dobry jest pojemnik, mając mniej zrzuconych?

WYZWANIE
Znajdź metodę, która wymaga jak najmniejszej liczby zrzuceń, bez względu na to, jak dobry lub zły jest ten nowy pojemnik, aby odkryć najwyższe piętro w tym stupiętrowym budynku, z którego możesz bezpiecznie zrzucić jajko.
POSZUKIWANIE
Jak zmieniłaby się Twoja strategia, gdybyś miał do dyspozycji trzy jajka?
Komentarz
WYZWANIE
W „Egg Drop – 1” widzieliśmy, że stosowanie równomiernie rozmieszczonych podłóg w pierwszej rundzie testów zmniejszyło całkowitą liczbę upadków.
Na przykład, gdyby pierwsza runda polegała na zrzucaniu z wielokrotności dziesięciu, to w najgorszym przypadku potrzebnych byłoby 19 zrzuceń – 9 do 90. piętra, a następnie pojedyncze zrzucanie pięter aż do 100. piętra.
Znaczna poprawa wynika z decyzji o użyciu kroków o zmiennej długości w pierwszej fazie. Jeśli rozmieścisz je równomiernie, to zanim dotrzesz do szczytu, będziesz mieć wszystkie testy do wykonania, a potem mnóstwo testów jednoetapowych. Kluczem jest zmniejszenie rozmiaru kroku o jeden po każdym teście w pierwszej fazie.
Chociaż można obliczyć pierwszy krok matematycznie, to dość łatwo jest to zrobić metodą prób i błędów. Jeśli zaczniesz od kroku 12 i za każdym razem będziesz zmniejszać go o 1, otrzymasz kroki o rozmiarze 12 + 11 + 10 + …. + 1 = 78, a to oznacza, że nie dotrzesz do szczytu. Musisz zacząć od kroku 14, aby to osiągnąć. W najgorszym przypadku będzie to 14 spadków, co jest znaczną poprawą!
POSZUKIWANIE
Użycie trzech jajek bywa trudne. Za każdym razem, gdy dodajesz nowe jajko, chcesz wykorzystać wiedzę o tym, jak najlepiej wykorzystać jajka z wcześniejszej kolekcji. Na przykład, używając dwóch jajek, wiesz, że po awarii pierwszego, będziesz testować w pojedynczych krokach.
Dokładne obliczenie 3 jajek wymaga od ucznia szkoły podstawowej niewiarygodnej ilości matematyki. Możemy jednak zastąpić to metodą prób i błędów, a i tak uzyskać odpowiedź w miarę szybko.
Zacznijmy od poznania tych sum (nazywanych liczbami trójkątnymi): 1 + 2 = 3, 1 + 2 + 3 = 6, 1 + 2 + 3 + 4 = 10, 1 + 2 + 3 + 4 + 5 = 15, 1 + 2 + 3 + 4 + 5 + 6 = 21, 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 i 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 = 36. Chcemy wykorzystać te sumy do wyboru początkowych testów. Na przykład, jeśli zaczniemy od 28, a następnie użyjemy 28 + 21 = 49, a następnie przejdziemy do 28 + 21 + 15 = 64 i tak dalej, nie dotrzemy do końca.
Zatem nasz pierwszy zestaw testów powinien zostać przeprowadzony na piętrach 36, 36 + 28 = 64, 36 + 28 + 21 = 85, 36 + 28 + 21 + 15 = 100. Oznacza to, że testy przeprowadzimy na piętrach 36, 64 i 85. Niezależnie od wyniku testów, w najgorszym przypadku będziemy potrzebować 9 testów!
Możesz również pokazać swojej klasie poniższy film z TEDED:
https://ed.ted.com/lessons/can-you-solve-the-egg-drop-riddle-yossi-elran