2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

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

(Оффтоп)

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

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

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

 
 
 
 Re: Платный тест на радиоактивность
Сообщение28.12.2010, 21:11 
5 шариков проверяем 3
1)повезло
проверяем 2
а) повезло проверяем 1
потратили 20+20+30(неповезло в конце)=70
б) не повезло
потратили 20+30=50
2)не повезло проверяем 1
потратили 30+30 =60

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

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

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

 
 
 
 Re: Платный тест на радиоактивность
Сообщение28.12.2010, 21:30 
Аватара пользователя
Null в сообщении #392947 писал(а):
5 шариков проверяем 3
1)повезло
проверяем 2


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

 
 
 
 Re: Платный тест на радиоактивность
Сообщение28.12.2010, 21:44 
Эх у меня все наоборот :oops:
Но за 70 можно

 
 
 
 Re: Платный тест на радиоактивность
Сообщение28.12.2010, 21:57 
Аватара пользователя
Null
Если не сложно, можете написать худший случай для 5 шариков? (Желательно со знаками препинания.) Или скажите, где у меня ошибка.

 
 
 
 Re: Платный тест на радиоактивность
Сообщение28.12.2010, 22:01 
проверили 2 нет радиации проверили 1 из оставшихся нет радиации проверили любой из оставшихся есть радиация

 
 
 
 Re: Платный тест на радиоактивность
Сообщение28.12.2010, 22:08 
Аватара пользователя
Ясно. Спасибо.

 
 
 [ Сообщений: 8 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group