Платный тест на радиоактивность

[caxap]

Сегодня была олимпиада на diofant.ru. Одну задачку так и не смог решить (правильно). Подскажите, пожалуйста, где ошибка в моих рассуждениях. (Хоть олимпиада и закончилась, но задачку могут оставить на сайте в списке обычных задачек. Поэтому, пожалуйста, не пишите подсказок или тем более решений. Просто скажите, где я не прав.) Вот задача:

У Вас есть 200 одинаковых на вид, вес и ощупь шариков, ровно один из которых радиоактивен. Ещё имеется автомат, в который можно засунуть сколько угодно шариков, бросить 30 рублей и нажать кнопку. Если радиактивности нет, то загорается зелёная лампочка и автомат выдаёт 10 рублей сдачи. Если же обнаруживается радиоактивность, то загорается красная лампочка и никакой сдачи не выдаётся. Какой наименьшей суммой в рублях Вы должны располагать, чтобы гарантированно (т.е. при полном отсутствии везения) найти радиоактивный шарик?

Я думал так. При полном отсутствии везения, ни одна проверка не возвратит мне 10 руб,

(Оффтоп)

Если, конечно, я не специально положу шарики, о которых я знаю, что они не радиоактивные. Но, как я подумал, толку от такого действия нет: ведь в любом случае деньги я потеряю (20 руб), а никакой полезной информации я не получу.

поэтому каждая проверка мне будет обходится в 30 руб (т. е. в автомате всегда будет оказываться радиоактивный шарик). Разумней всего (по-моему) искать шарик методом дихотомии, т. е. сначала кладу в автомат половину шариков, проверяю, ненужную половину отсеиваю и т. д. Типа двоичный поиск. Ну а при двоичном поиске я в худшем случае найду шарик через $\lceil\log_2 200\rceil=8$ шагов. Как уже говорил, из-за полного невезения при каждой проверке я буду терять 30 руб. Итого мне нужно $30\cdot 8=240$ руб для нахождения шарика.

Но это не верно -- сайт такой ответ не принимает. Значит, как-то можно быстрее найти.

[Null]

5 шариков проверяем 3
1)повезло
проверяем 2
а) повезло проверяем 1
потратили 20+20+30(неповезло в конце)=70
б) не повезло
потратили 20+30=50
2)не повезло проверяем 1
потратили 30+30 =60

Итого потратили 70.

[caxap]

Null
Что-то не понял. Вы первый раз положили 3 шарика в автомат.
Если повезло, значит радиоактивного там не было -- он среди двух непроверенных. Проверяем их и теряем всего $20+30=50$ руб.
Если не повезло, то теряем 30 руб и остаётся 3 шарика. В худшем случае для их проверки требуется 60 руб.

То есть получается в худшем случае $30+60=90$ руб (как у вас 70 получилось, я что-то не въехал...). В моём решении как раз 90 и получается: $30\cdot\lceil\log_2 5\rceil=90$.

[Dan B-Yallay]

Null в сообщении #392947 писал(а):

5 шариков проверяем 3
1)повезло
проверяем 2

Зачем 2? Можно и один шарик положить.

[Null]

Эх у меня все наоборот
Но за 70 можно

[caxap]

Null
Если не сложно, можете написать худший случай для 5 шариков? (Желательно со знаками препинания.) Или скажите, где у меня ошибка.

[Null]

проверили 2 нет радиации проверили 1 из оставшихся нет радиации проверили любой из оставшихся есть радиация

[caxap]

Ясно. Спасибо.