У бедного мальчика Саши всего 300 монет, и к тому же ровно одна из них фальшивая (легче настоящей). У жадного мальчика Кости есть весы, но за каждое взвешивание он берет с Саши плату: 200 (бумажных) рублей, если перевесила левая чашка, и 100 (бумажных) рублей при любом другом исходе. Какую наименьшую сумму должен приготовить Саша, чтобы заведомо определить фальшивую монету с помощью Костиных весов?


+ -

Ответ

Решение задачи

Ваши ответы на задачу

ответов: 18

R-2 2015-10-15 01:39:34 пишет:

733
Нет, чесно, 733.
Когда мы взвешиваем три кучки, то равновероятны все 3 варианта. Два дешевых, по 100 рублей. И один дорогой - за 200. Так что одно тройное взвешивание нам обойдется в 133р 33к.
И тогда двойное взвешивание за 100р становится не чуть-чуть менее выгодным.
0) одна из 300 монет
1) 100 монет 133р
2) 34 монеты 133р
3) 12 монет 133р
4) 4 монета 133р
5) 2 монеты 100р
6) 1 монета 100р

Админ: всё логично, но выборка маловата, чтобы рассчитывать на среднее. Надо исходить из того, что каждое взвешивание будет самым дорогим - только так можно выполнить условие "заведомо", т.е. гарантировать что денег хватит при любом невезении.

KoKos 2013-11-20 22:35:12 пишет:

:) Ну, на самом деле в таких задачах наиболее быстрым является тернарный поиск. Но тут он еще и сам по себе "взвешенный" по цене. Так что бинарный может оказаться дольше, зато выгоднее... Посмотрим. ;) Первое взвешивание у нас всегда наугад, - то бишь 200р. на худший случай. Но после него мы уже точно имеем эталон, который позволяет делать полубинарный-полутернарный поиск "по дешевке". XD XD XD Общая идея проста. Имея две "неопознанных" и одну "эталонную", мы одну неизвестную откладываем в сторону, эталонную кладем строго на правую чашку (и имеем уверенность в том, что левая не перевесит, ни за какие коврижки 8))). Итак, первое действие тернарное - все равно терять нечего... Остальные - бинарные против эталона. Такие "бинарные" дают сужение круга поиска вчетверо за ту же сумму, за которую тернарные всего втрое. ;)) Считаем: 1+2+4+8+16+32+64+128-300 = 7 плюсов, 1 минус = 900р.

Админ:

ZAX 2013-11-20 09:42:35 пишет:

"...плату: 200 (бумажных) рублей, если перевесила левая чашка, и 100 (бумажных) рублей при любом другом исходе....".
В этом условии "И" делает: в любом случае 100 р., а при перевесе на левой чаше ЕЩЁ 200 р.
Условие должно быть в виде:
"...плату: если перевесила левая чаша, то 200 (бумажных) рублей, а при любом другом исходе взвешивания 100 (бумажных) рублей ....".

Админ: можете решить исходя из такого понимания задачи.

я 2011-09-30 20:56:23 пишет:

хотя я нашёл один подвох "У БЕДНОГО мальчика Саши" откуда у него столько денег??

я 2011-09-30 20:54:21 пишет:

P.S. я это не Я

я 2011-09-30 20:52:59 пишет:

сначала взвешиваем 100 и 100 если в какой-то кучке есть фальшивая монета взвешиваем 50 50 (соответственно если в другой сотне также) потом взвешиваем 10 и 10 если в одной из этих куч то двойками максимум получится 5 взвешиваний ну а потом 1 1 и всё
Итого:при наилучшем раскладе 900 лучше я не придумал

azon 2011-04-13 12:41:24 пишет:

минимальный ответ 200 будет,если очень повезет,а другие нет смысла считать

azon 2011-04-13 12:40:45 пишет:

Тогда и 900 тоже не верны будут т.к. в 1 случае вы надеетесь,что весы влево не перевесят и вы не узнаете сколько весят кучки,которые вы разделили и получается при взвешивании 200 рублей отдали,потому еще 200 и т.д. до конца потому что вы не можете даже если взвесите 1 кучку и поймете,что именно там фальшивка в не сможете разделить так,чтобы слева было меньше чем справа-шанс 1к2

Очевидность 2011-03-24 13:08:52 пишет:

Думаю, вариант, когда Саша может взять у Кости сколько угодно обычных монет, отпадает?

Очевидность 2011-03-24 09:46:42 пишет:

Вот мой вариант:
взвешиваем 100 и 100 - 200 руб. мы знаем, в какой куче фальшивая монета и делим эту кучу пополам.кучи, где заведомо фальшивая монета, всё время ложим на левую чашу весов, чтобы не перевесила. 50 монет, среди которых может быть заведомо фальшивая, на л.ч.в, 50 монет, где заведомо нет фальшивой монеты, на правой.т.о. взвешиваем 50 и 50, 25 и 25, 12 и 12, 6 и 6, 3 и 3, 1 и 1(в последнем взвешивании опять отдаем 200 руб.) получается 900

Админ:

Ubori 2011-03-23 21:50:38 пишет:

Например такой вариант:

1. 120vs120 Нашли: 120 монет среди которых фальшивая за 200р.
2. На левую чашу кладем любые 60 из этих 120монет,а на правую заведомо не фальшивые 60монет. Нашли: 60 монет среди которых фальшивая за 100р
Далее каждый раз на правую чашу кладем заведомо не фальшивые деньги, а на левую половину из числа где лежит фальшивая.
3. 30vs30 (100р)
4. 15vs15 (100р)
5. 8vs8 (100р)
6. 4vs4 (100р)
7. 2vs2 (100р)
8. 1vs1 (100р)
Получаем 900р.

Админ: верно - 900 р. Кто меньше? :)

батенька 2011-03-17 23:55:57 пишет:

1100

Админ: Решили поугадывать? Решение - в студию :)

батенька 2011-03-17 23:48:53 пишет:

1200

Админ:

батенька 2011-03-17 23:36:35 пишет:

1800

Админ:

Очевидность 2011-03-17 12:36:12 пишет:

ах да, как всегда второпях прочитал задачу. но все же есть решение с меньшей суммой

Админ: так приведите его :)

Очевидность 2011-03-17 11:38:45 пишет:

Наименьшая сумма - это идеальный вариант, когда в последнем взвешивании фальшивая монета будет на левой чаше. А в первых пяти взвешиваниях весы будут все время в равновесии.Получится 600 бумажных рублей

Админ: не соглашусь. Надо найти "наименьшую сумму, чтобы заведомо определить"... заведомо - то есть гарантированно. Если Саша приготовит 600 рублей, то он определит фальшивую монету лишь в случае удачного стечения обстоятельств. Тогда ему достаточно всего 100 рублей - взять наугад две монеты и взвесить: повезет - узнает какая монета фальшивая.

Очевидность 2011-03-16 15:07:23 пишет:

а у меня получилось 600

Админ: O! крайне интересно. Мы с пользователем Я делили каждым взвешиванием монеты на 3 части. А как решали вы?

Я 2011-03-16 08:06:02 пишет:

1100

Админ: у меня получилось также :)

Добавьте комментарий:

© 2009-201x Логические задачи