/Konkursy/Zadania testowe

Zadanie nr 1028479

Automat matematyczny działa na następującej zasadzie: do danej liczby dodaje 1 lub ją podwaja. Do automatu wprowadzono liczbę 0. Ten po wykonaniu pewnej liczby operacji otrzymał liczbę 100. Jaka jest najmniejsza liczba operacji, którą musi wykonać automat, żeby otrzymać taki wynik?
A) 8 B) 9 C) 10 D) 28 E) 43

Wersja PDF

Rozwiązanie

Chwilę kombinując można wymyślić następujący ciąg operacji

0 → 1 → 2 → 3 → 6 → 12 → 24 → 25 → 50 → 100 .

Najłatwiej jest go wymyślić rozkładając liczbę 100 od końca.

Spróbujmy jakoś się przekonać, że nie da się tego zrobić przy pomocy 8 operacji. Na pewno pierwszą opercją musi być dodanie jedynki. Oprócz tego muszą być jeszcze co najmniej dwie operacje dodawania jedynki – tak jest, bo gdyby była jeszcze tylko jedna taka operacja, to 100 byłoby wielokrotnością 3, 9, 17 lub 33, co nie zachodzi. Gdybyśmy na początku nie zrobili 3, czyli mieli sekwencję 0 → 1 → 2 → 4 to maksymalna liczba jaką otrzymamy w 8 krokach to

0 → 1 → 2 → 4 → 5 → 10 → 20 → 40 → 80.

Zatem na początku musimy zrobić 3. Teraz łatwo już zobaczyć, że jedyną możliwością wstawienia 3 jedynki jest krok 24 → 25 .  
Odpowiedź: B

Wersja PDF
spinner