Сегодня была олимпиада на diofant.ru. Одну задачку так и не смог решить (правильно). Подскажите, пожалуйста, где ошибка в моих рассуждениях. (Хоть олимпиада и закончилась, но задачку могут оставить на сайте в списке обычных задачек. Поэтому, пожалуйста, не пишите подсказок или тем более решений. Просто скажите, где я не прав.) Вот задача:
У Вас есть 200 одинаковых на вид, вес и ощупь шариков, ровно один из которых радиоактивен. Ещё имеется автомат, в который можно засунуть сколько угодно шариков, бросить 30 рублей и нажать кнопку. Если радиактивности нет, то загорается зелёная лампочка и автомат выдаёт 10 рублей сдачи. Если же обнаруживается радиоактивность, то загорается красная лампочка и никакой сдачи не выдаётся. Какой наименьшей суммой в рублях Вы должны располагать, чтобы гарантированно (т.е. при полном отсутствии везения) найти радиоактивный шарик?Я думал так. При полном отсутствии везения, ни одна проверка не возвратит мне 10 руб,
(Оффтоп)
Если, конечно, я не специально положу шарики, о которых я знаю, что они не радиоактивные. Но, как я подумал, толку от такого действия нет: ведь в любом случае деньги я потеряю (20 руб), а никакой полезной информации я не получу.
поэтому каждая проверка мне будет обходится в 30 руб (т. е. в автомате всегда будет оказываться радиоактивный шарик). Разумней всего (по-моему) искать шарик методом дихотомии, т. е. сначала кладу в автомат половину шариков, проверяю, ненужную половину отсеиваю и т. д. Типа двоичный поиск. Ну а при двоичном поиске я в худшем случае найду шарик через
шагов. Как уже говорил, из-за полного невезения при каждой проверке я буду терять 30 руб. Итого мне нужно
руб для нахождения шарика.
Но это не верно -- сайт такой ответ не принимает. Значит, как-то можно быстрее найти.