Strona główna » Algorytmy » Artykuły » Pudełka Niespodzianki
 

Pudełka Niespodzianki



Zagadka

W sklepie przygotowano 200 pudełek niespodzianek. Nikt nie wie co się w nich znajduje. Cena jednego pudełka jest bardzo niska. Każdy kolejny klient widząc zadowolone miny poprzednich klientów kupuje więcej pudełek niż oni. Ile maksymalnie osób mogło dokonać zakupu?

Rozwiązanie

Odpowiedź

Pudełka niespodzianki zakupi pierwszych 19 klientów.

Wyjaśnienie

Na początku należy ustalić reguła zakupów klientów tak, aby jak najwięcej osób mogło dokonać zakupu. Pierwszy klient musi kupić jak najmniejszą ilość produktu tj. jedno pudełko, a każdy następny więcej niż poprzednio, ale zarazem tak mało, aby zostało jak najwięcej pudełek. Innymi słowy będzie kupował o jedno pudełko więcej.

Rozwiązanie 1

Zadanie sprowadza się do sprawdzenia, który klient nie będzie mógł już kupić produktów, ponieważ będzie ich niewystarczająca ilość. Oznacza to, że można wypisać wszystkich klientów po kolei i ile pudełek zostało w sklepie.

PudełekKupionych
2001
1992
1973
1944
1905
1856
1797
1728
1649
15510
PudełekKupionych
14511
13412
12213
10914
9515
8016
6417
4718
2919
10-

Klient, który przyszedł jako 20 chciały zakupić 20 pudełek niespodzianek, ale nie może, ponieważ zostało ich zaledwie 10, więc rezygnuje z zakupu.

Rozwiązanie 2

Poprzedni sposób na rozwiązanie metodą "na piechotę" wymaga nieco liczenia. Na szczęście istnieje możliwość uproszczenia tego procesu używając funkcji kwadratowej. Korzystając ze wzoru na sumę kolejnych liczb naturalnych otrzymujemy:

Teraz taki wzór należy przekształcić tak, aby obliczyć n:

Wiadomo, że rozwiązanie jest w przedziale [1, 19], ponieważ n należy do zbioru liczb naturalnych. Z tego wynika, że tylko sumując pierwsze 19 wyrazów otrzymamy wartość mniejszą, równą od 20.