задачка про вино

[avva]

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

У вас есть 240 бочек вина, ровно в одной из них вино отравлено. Любой, кто выпивает отравленное вино, умирает в течение 24 часов. У вас есть пять рабов, которыми вы готовы пожертвовать, чтобы определить, какая бочка отравлена. Определите отравленную бочку, уложившись в 48 часов.

P.S. Я постараюсь скрывать правильные ответы поначалу, но не обещаю. Так что не заглядывайте в комментарии, если хотите сами решить.

P.P.S. OK, уже очень много правильных ответов. Я раскрываю все скрытые до сих пор правильные. Теперь точно не заглядывайте, если хотите сами :)

Comments

[(Anonymous)]

В америке за такие задачки в тюрьму посадили бы

[luar-soll.livejournal.com]

А "в течение" - это значит, что может и раньше, чем через 24?

[avva.livejournal.com]

Да.

[buddha239.livejournal.com]

А, 3 в пятой?:) Мне кажется, можно усовершенствовать метод, если поить вином постепенно.

[buddha239.livejournal.com]

А нет, нельзя вроде; все равно глупые рабы могу помирать в конце суток.:)

[avva.livejournal.com]

Да :) я скрою ваш комментарий пока что.

Тут такое усовершенствование не пройдет, т.к. есть только 48 часов.

[arpad.livejournal.com]

"У вас есть 240 бочек вина"

Поскольку я еврейский рабовладелец - травить рабов мне запрещено :P

[buddha239.livejournal.com]

Кстати, зачем тут бумага-то; в степень возводить?:)

[buddha239.livejournal.com]

Ну, Вы же могли не знать, что вино отравлено.:)

[avva.livejournal.com]

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

[abu-daud.livejournal.com]

Тогда изменим условие - есть 5 добровольцев, которые ради науки готовыпожертвовать жизнью.

[(Anonymous)]

пронумеруем бочки 5-разрядными троичными числами, а рабов просто пронумеруем
дадим рабу номер i в начале испытания вино из всех бочек с номерами, в i-м разряде которых 0
и еще через 24 часа, если не умер — вино из всех бочек с номерами, в i-м разряде которых 1
через 48 часов разложим рабов по порядку
на рабах, умерших в первые 24 часа, напишем 0
на рабах, умерших в следующие 24 часа, напишем 1
на живых рабах напишем 2
получим номер отравленной бочки
правильно?

1016

[xygou.livejournal.com]

max

[muchacho.livejournal.com]

нашел решение для 243 бочек вина, правда не в уме

[tygdym.livejournal.com]

А порция вина из отравленной бочки, разбавленная вином из, скажем, 47 других бочек, всё равно убивает?

[b-a-t.livejournal.com]

Да

[avva.livejournal.com]

да, все верно :)

[avva.livejournal.com]

видимо, правильное :)

[avva.livejournal.com]

Конечно.

[aldragon.net (from livejournal.com)]

Первый раб сначала пьет "коктейль" из всех бочек с номерами N такими, что (N mod 3)=1. Если через 24 часа он жив - из всех бочек с (N mod 3)=2.

По результатам мы знаем, равно ли (N mod 3) 0,1 или 2.

Для второго раба группируем бочки по три (т.е. смешиваем вино из них)- получаем 80 троек. Сначала он выпивает "коктейль" из 26 троек с номерами М такими, что (M mod 3)=1, если остается жив - с (M mod 3)=2.

Для третьего - группируем бочки по девять, действуем аналогично. Четверому и пятому - группируем бочки по двадцать семь и восемьдесят штук.

Зная пять остатков от деления на три, однозначно определяем отравленную бочку.

[avva.livejournal.com]

да, работает.

[talgaton.livejournal.com]

давай не 5 рабов - а 5 тестеров :) - а то в друг запретят въезд в сша :(.
частичное решение - но мне кажется - путь к правильному:
1. смешиваем вино из первых 120 бочек - даем попробовать 1 тесеру.
2. смешиваем вино из всех нечетных бочек - даем поробовать второму тестеру
черех 24 часа можем вычислить 60 отравленых бочек - и точно определить что в 180 бочках вино не отравлено.

[drw.livejournal.com]

А вроде бы у вас уже была такая же или похожая задача.

[talgaton.livejournal.com]

через 24 часа у нас с весьма возможно есть 4 работающих тесетра (но может и 3).
и 60 бочек с вопросом.
(но бухать уже можно)
все повторяем еще раз.

[p_govorun.livejournal.com]

Действуем двоичным делением.

В первый день делим бочки на 32 группы, нумеруем группы в двоичной системе и даём каждому из пяти рабов попробовать из тех бочек, у которых "его" бит равен единице. (Естественно, пробовать надо все бочки из группы.) Посмотрев, кто из рабов помер, определяем, в какой группе отравленная бочка. На следующий день повторяем эксперимент с этой группой бочек и оставшимися рабами.

Теперь статистика.

Группу 00000 не будет пробовать никто. Если яд там, то на следующий день у нас будет 5 рабов. Значит, в эту группу можно включить 32 бочки.

Группы 00001, 00010, 00100, 01000 и 10000 будут пробовать по одному рабу. Если яд там -- останется 4 раба. В эти группы можно включить по 16 бочек.

Продолжая рассуждать так же, получаем: 10 групп по 8 бочек, 10 групп по 4 бочки, 5 групп по 2 бочки и одну группу из одной бочки.

Итого мы можем проверить 32+5*16+10*8+10*4+5*2+1=243 бочки. Получилось даже больше, чем 240.

(Интересно было бы доказать, что это максимум.)