2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Циничная задача :)
Сообщение06.05.2008, 18:28 
Заслуженный участник
Аватара пользователя


01/08/06
3158
Уфа
Патриций решил устроить праздник и для этого приготовил 240 бочек вина. Однако к нему пробрался недоброжелатель, который подсыпал яд в одну из бочек. Недоброжелателя тут же поймали, дальнейшая его судьба неизвестна.
Про яд известно, что человек, его выпивший, умирает в течение 24 часов. До праздника осталось два дня, то есть 48 часов. У патриция есть пять рабов, которыми он готов пожертвовать, чтобы узнать в какой именно бочке яд. Расскажите каким образом можно это узнать.

Задачка школьная, я бы сказал, с уклоном в сторону Computer Science. Прошу "зубров" в комбинаторике пока воздержаться от выкладывания полного решения и дать порешать другим (хотя, возможно, некоторым из "зубров" она покажется интересной).

 Профиль  
                  
 
 
Сообщение06.05.2008, 18:44 
Аватара пользователя


23/09/07
364
worm2 писал(а):
Про яд известно, что человек, его выпивший, умирает в течение 24 часов

Известно, что человек умрёт ровно через 24 часа, или может пораньше?

 Профиль  
                  
 
 
Сообщение06.05.2008, 19:04 
Заслуженный участник
Аватара пользователя


01/08/06
3158
Уфа
Известно, только, что человек умирает в течение 24 часов.
Проще говоря, у патриция только 2 попытки, всё остальное - это поэзия :)

 Профиль  
                  
 
 
Сообщение06.05.2008, 19:30 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
Если бы было ровно 24 часа, а не в течении двадцати четырёх часов, то задача бы решалась просто. А так...

Делим 240 бочек на 6 частей по 40 бочек. Для каждой части собираем бокал (по несколько капель из каждой бочки, находящейся в данной части) и даём попробовать одному из рабов. Ждём 24 часа.

После этого остаётся 4 раба (возможно, конечно, что и 5, но в худшем случае 4) и 40 бочек, про которые известно, что в одной из них яд. Делим на 5 частей по 8 бочек, повторяем процедуру.

Проходят ещё сутки. Становятся известны 8 бочек, в одной из которых яд. А время вышло. Конечно, с 232 бочками вина уже можно устроить нормальный праздник, но это всё же не решение задачи. А как идентифицировать ту единственную бочку и уложиться в срок? Даже не верится, что это возможно...

Вот такой вопрос по ходу. Время, за которое раб умирает, попробовав отраву: оно фиксировано или может варьироваться? Другими словами, если два раба пробуют отраву одновременно, то они и умирают потом одновременно или могут умереть в разное время?

 Профиль  
                  
 
 
Сообщение06.05.2008, 19:35 
Заслуженный участник
Аватара пользователя


18/12/07
762
На самом деле бочек оказалось 243. Три бочки виногрузчики решили заныкать и стырить - мол всё равно никто считать не будет...
"Ну, в общм, они не сносили голов".

 Профиль  
                  
 
 
Сообщение06.05.2008, 19:38 


17/01/08
110
Пусть k-ый раб отопьет из каждой бочки, у которой в k-ом разряде номера в троичной системе счисления стоит 0. Рассмотрим выживших в первые сутки рабов. Тогда в номере ядовитой бочки в соответствующих разрядах могут стоять только 1 и 2, а в разрядах умерших рабов стоят нули. Зафиксируем нулевые разряды, и во второй день выжившие рабы отопьют из бочек, где на соответствующих разрядах стоят 1. Если раб умер, то в номере ядовитой бочки соответствующий разряд равен 1, иначе 2.

 Профиль  
                  
 
 
Сообщение06.05.2008, 19:41 
Заслуженный участник
Аватара пользователя


01/08/06
3158
Уфа
Профессор Снэйп писал(а):
Время, за которое раб умирает, попробовав отраву: оно фиксировано или может варьироваться? Другими словами, если два раба пробуют отраву одновременно, то они и умирают потом одновременно или могут умереть в разное время?

Могут умереть в любое время независимо от количества выпитого яда, независимо друг от друга. Всего 2 попытки.

Профессор Снэйп писал(а):
А как идентифицировать ту единственную бочку и уложиться в срок? Даже не верится, что это возможно...

Я счастлив, что задача показалась Вам такой нерешаемой :D
А то боялся, что придёт сейчас кто-нибудь и напишет "всё тривиально"...

 Профиль  
                  
 
 
Сообщение06.05.2008, 19:41 


17/01/08
110
Коровьев писал(а):
На самом деле бочек оказалось 243.

Просек фишку : ))

 Профиль  
                  
 
 
Сообщение06.05.2008, 19:58 
Заслуженный участник
Аватара пользователя


18/12/07
762
Kid Kool писал(а):
Коровьев писал(а):
На самом деле бочек оказалось 243.

Просек фишку : ))

Верно.
$243=3^5$

 Профиль  
                  
 
 
Сообщение06.05.2008, 20:01 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
Да, я тоже просёк. Правда, только после того, как увидел подсказку насчёт числа $243$.

 Профиль  
                  
 
 
Сообщение06.05.2008, 20:13 
Заслуженный участник
Аватара пользователя


01/08/06
3158
Уфа
А я, если честно, когда решал, фишку так и не просёк, и 243 получил честно как сумму
$$\sum\limits_{i=0}^{5}C_5^i 2^i$$
:lol:

Добавлено спустя 2 минуты 18 секунд:

Т.е. у меня было более сложное решение с разбором шести различных вариантов.

 Профиль  
                  
 
 
Сообщение22.10.2008, 17:01 


22/10/08
2
есть единственно правильное решение ;)
друг мой один решил вот так.
_______________________________________
Выкидываем в первый день обследования сразу 30 бочек. Их мы оставим на завтра, если никто не умрёт через 24 часа. :)

остаётся 240-30 = 210 бочек. Занумеруем рабов по порядку от 1 до 5 (на то они и рабы. Составим график пития для бочек: :)
1 - 16
2 - 16
3 - 16
4 - 16
5 - 16
1-2 - 8
1-3 - 8
1-4 - 8
1-5 - 8
2-3 - 8
2-4 - 8
2-5 - 8
3-4 - 8
3-5 - 8
4-5 - 8
1-2-3 - 4
1-2-4 - 4
1-2-5 - 4
1-3-4 - 4
1-3-5 - 4
1-4-5 - 4
2-3-4 - 4
2-3-5 - 4
2-4-5 - 4
3-4-5 - 4
1-2-3-4 - 2
1-2-3-5 - 2
1-2-4-5 - 2
1-3-4-5 - 2
2-3-4-5 - 2
----------------
итого: 16*5 + 8*10 + 4*10 + 2*5 = 210 бочек :)

Поим засранцев и смотрим на результат:
Никто не умер: 30 бочек и 5 живчиков :)
Умер один раб:отравленная бочка в одной из 16, которую он пил один. Осталось 4 раба, ищется элементарно :)
умерло двое: отравленная бочка в одной из 8-ми, которые они распивали вместе. На троих найдут в следующие сутки.
умерло трое: осталось два раба и 4 бочки. Ерунда :)
умерло четверо: остался один раб - и две бочки.

That's all! :)
ЗЫ. В задачу можно смело ещё три бочки запихать. Алгоритм тот же :)

 Профиль  
                  
 
 
Сообщение23.10.2008, 09:32 
Заслуженный участник
Аватара пользователя


23/08/07
5512
Нов-ск
worm2 писал(а):
Профессор Снэйп писал(а):
А как идентифицировать ту единственную бочку и уложиться в срок? Даже не верится, что это возможно...

Я счастлив, что задача показалась Вам такой нерешаемой :D
А то боялся, что придёт сейчас кто-нибудь и напишет "всё тривиально"...

Задача и есть нерешаемая. Из того что раб остался жив, конечно, следует, что он не пил яда. Но из того что раб сдох, не следует, что он яд пил. Рабы дохнут и от других причин. Все ваши рассуждения рушатся, приглашенные на праздник гости в опастности.

 Профиль  
                  
 
 
Сообщение23.10.2008, 09:55 


22/10/08
2
TOTAL писал(а):
worm2 писал(а):
Профессор Снэйп писал(а):
А как идентифицировать ту единственную бочку и уложиться в срок? Даже не верится, что это возможно...

Я счастлив, что задача показалась Вам такой нерешаемой :D
А то боялся, что придёт сейчас кто-нибудь и напишет "всё тривиально"...

Задача и есть нерешаемая. Из того что раб остался жив, конечно, следует, что он не пил яда. Но из того что раб сдох, не следует, что он яд пил. Рабы дохнут и от других причин. Все ваши рассуждения рушатся, приглашенные на праздник гости в опастности.


нет на этом свете не решаемых задач ;)

 Профиль  
                  
 
 
Сообщение24.10.2008, 11:16 
Заблокирован


16/03/06

932
TOTAL в сообщении #152709 писал(а):
Задача и есть нерешаемая. Из того что раб остался жив, конечно, следует, что он не пил яда. Но из того что раб сдох, не следует, что он яд пил. Рабы дохнут и от других причин. Все ваши рассуждения рушатся, приглашенные на праздник гости в опастности.

Согласен с такими утверждениями. Как только в задачу засовываются житейские подробности, так сразу возникают дополнительные условия, игнорировать которые нельзя по негласному соглашению: "все условия задачи должны быть соблюдены". От себя добавлю: гости в любом случае в опасности.
1. Судьба злоумышленника не известна ( может еще подсыпать).
2. Гости могут умереть и не от яду (как и рабы). Знаем случаи смерти и от перепою (вино в некотором смысле тоже яд, тока разбавленный).
Sanya в сообщении #152715 писал(а):
нет на этом свете не решаемых задач

Согласен. Решить можно любую задачу. Тока кто будет за это отвечать? Рабы, как всегда? :lol:

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 16 ]  На страницу 1, 2  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: Dmitriy40


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group