LazarusLong
Ирландский доброволец
Проректор
Карма: +181/-7
 Offline
Пол:  Награды: 
Сообщений: 6133
Ukrainian by birth, Irish by the grace of God
|
 |
« : Апрель 25, 2008, 01:50:23 » |
|
Патриций решил устроить праздник и для этого приготовил 240 бочек вина. Однако к нему пробрался недоброжелатель, который подсыпал яд в одну из бочек. Недоброжелателя тут же поймали, дальнейшая его судьба неизвестна.
Про яд известно, что человек, его выпивший, умирает в течение 24 часов. До праздника осталось два дня, то есть 48 часов. У патриция есть пять рабов, которыми он готов пожертвовать, чтобы узнать в какой именно бочке яд. Расскажите каким образом можно это узнать.
Большая просьба не гуглить. Ответ найти можно за пару минут, но ведь может быть интересно людям порешать)))).
|
|
|
|
« Последнее редактирование: Май 13, 2008, 08:31:16 от vimmax »
|
Записан
|
Когда ему нужно - он русский, когда нужно - украинец, а когда ему ни хрена не нужно - он ирландец.
"...Он любил говорить факин щит
Когда что-то не так ему
Принимал он свой самый ирландский вид
И кидался трубкой в жену..."
|
|
|
|
FazU
|
 |
« Ответ #1 : Апрель 25, 2008, 08:47:29 » |
|
1шаг: разделить бочки на 5 рабов поровну. рабы выпивают каждый из своих бочек по глотку. Через 24 часа один клеит ласты.
2 шаг: Те бочки из которых пил умерший раб делят поровну наоставшихся и повторяют процедуру. Через 24 часа умирает еще один раб. А у Патриция будет уверенность в том, что 240*4/5+48*3/4=192+36=228 бочек не отравлены.
***
шаг 3 (злобно уничтожительный):
Оставшиеся 12 бочек патриций тоже использует. Вино из них он подаст своим недоброжелателям. И случай выберет из них кто будет жив, а кто мертв.
***
Не гуглил.
(Отправлено в: 25 Апреля 2008, 08:41:29)
Тут эта если б не было написано, что судьба диверсанта не известна можно было бы предположить, что он тоже может участвовать в "дегустации". И тогда можно было бы уверенно говорить об отсутствии яда в большем количестве бочек.
Повторив описаный алгоритм, но исходя уже из 6 "дегустаторов", получим, что об отсутствии яда известно в 232 бочках, а 8 достанется недоброжелателям.
|
|
|
|
|
Записан
|
|
|
|
broken-wings
wings of empathy
Модератор
Проректор
Карма: +176/-6
Offline
Пол: Награды: ![3 место в фотоконкурсе \](http://kita.org.ua/awards/28bb064b6133ee40d115a5d5cf52c1c1_camera.gif "3 место в фотоконкурсе \") ![За победу в конкурсе футбольных прогнозистов \](http://kita.org.ua/awards/c5aa4bac0dc94f50658923b8d4769aec_ball_prognoz.png "За победу в конкурсе футбольных прогнозистов \")
Сообщений: 4531
Эксперт по какашкам и поиску смыслов
|
|
« Ответ #2 : Апрель 25, 2008, 08:56:05 » |
|
FazU не люблюподобные выводы Вино из них он подаст своим недоброжелателям все же задача не на импровизацию... я все же погуглил, не удержался,так там тоже всяких домыслов полно - в задаче не скахано про то,что у Патрциия только 5 рабов, может у него их как раз 240... и тогда потеря будет всего один раб...ну и так далее...
|
|
|
|
|
Записан
|
кругом одно и то же свинство
но я умею выделять
по незначительным нюансам
спорт журналистику кино
|
|
|
LazarusLong
Ирландский доброволец
Проректор
Карма: +181/-7
Offline
Пол: Награды:
Сообщений: 6133
Ukrainian by birth, Irish by the grace of God
|
|
« Ответ #3 : Апрель 25, 2008, 09:02:03 » |
|
FazU, нет нужно точно идентифицировать бочку с ядом за 48 часов.
Дегустаторов всего 5.
|
|
|
|
|
Записан
|
Когда ему нужно - он русский, когда нужно - украинец, а когда ему ни хрена не нужно - он ирландец.
"...Он любил говорить факин щит
Когда что-то не так ему
Принимал он свой самый ирландский вид
И кидался трубкой в жену..."
|
|
|
broken-wings
wings of empathy
Модератор
Проректор
Карма: +176/-6
Offline
Пол: Награды:
Сообщений: 4531
Эксперт по какашкам и поиску смыслов
|
|
« Ответ #4 : Апрель 25, 2008, 09:06:15 » |
|
LazarusLong и бочка должна быть точно определена. искал решение - но нашел лишь наподобии удачно определить 8 бочек...
Лишь одна?
|
|
|
|
|
Записан
|
кругом одно и то же свинство
но я умею выделять
по незначительным нюансам
спорт журналистику кино
|
|
|
|
FazU
|
|
« Ответ #5 : Апрель 25, 2008, 09:10:22 » |
|
Ну одна определится тогда когда кто-то из недоброжелателей копытнется))
А моя импровизация и мои выводы помоему восприняты слишком сухо и серьёзно. Че вы такие не веселые с утра?
|
|
|
|
|
Записан
|
|
|
|
LazarusLong
Ирландский доброволец
Проректор
Карма: +181/-7
Offline
Пол: Награды:
Сообщений: 6133
Ukrainian by birth, Irish by the grace of God
|
|
« Ответ #6 : Апрель 25, 2008, 09:13:07 » |
|
Нужно ОДНОЗНАЧНО определить бочку с ядом ДО НАЧАЛА праздника. FazU, твой ход мыслей понятен, но это не решение задачи:) Я тоже сперва так думал. Кстати по слухам подобные задачки любят задавать программерам на собеседованиях в Google  . |
|
|
|
|
Записан
|
Когда ему нужно - он русский, когда нужно - украинец, а когда ему ни хрена не нужно - он ирландец.
"...Он любил говорить факин щит
Когда что-то не так ему
Принимал он свой самый ирландский вид
И кидался трубкой в жену..."
|
|
|
|
FazU
|
|
« Ответ #7 : Апрель 25, 2008, 09:14:54 » |
|
Прикольно ))) Саша, респект за ход мысли!!  |
|
|
|
|
Записан
|
|
|
|
grimgav
↑ так меня зовут, а это я говорю →
Просто гламурный
Проректор
Карма: +161/-17
Offline
Пол: Награды:
Сообщений: 4636
не ^i^
|
|
« Ответ #8 : Апрель 25, 2008, 09:36:31 » |
|
Разделить бочки по ровну на 5 рабов. Т.е. по 48 на рыло. Каждые 10 минут (например, лень считать интервалы чтоб уложиться в 48 часов). И засечь через сколько часов после начала распития скопытиться один дегустатор. Соответственно отнять 24 часа и вычислить какая бочка отравлена =)
|
|
|
|
|
Записан
|
· Я русский ·
|
|
|
LazarusLong
Ирландский доброволец
Проректор
Карма: +181/-7
Offline
Пол: Награды:
Сообщений: 6133
Ukrainian by birth, Irish by the grace of God
|
|
« Ответ #9 : Апрель 25, 2008, 09:49:07 » |
|
grimgav, да это был один из моих первых вариантов решения. Но фишка в том, что выпивший вино умрет не ровно через 24 часа, а В ТЕЧЕНИИ 24 часов. То есть может быть и через 10 минут. (Отправлено в: 25 Апреля 2008, 09:38:12)шаг: разделить бочки на 5 рабов поровну. рабы выпивают каждый из своих бочек по глотку. Через 24 часа один клеит ласты. Кстати не приходило в голову, что можно разделить и на 6 частей - каждый раб пьёт из 40 бочек. А из 40 последних бочек - ни пьёт никто. Соответственно если кто-то умер - мы знаем в каких из 40 бочек отрава. А если никто не умер - то яд в одной из бочек из которых никто не пил (это не намек на решение), просто усовершенствование метода предложенного FazU. Таким образом можно локализовать интервал до 8 бочек. Но это тоже не решение.
|
|
|
|
|
Записан
|
Когда ему нужно - он русский, когда нужно - украинец, а когда ему ни хрена не нужно - он ирландец.
"...Он любил говорить факин щит
Когда что-то не так ему
Принимал он свой самый ирландский вид
И кидался трубкой в жену..."
|
|
|
|
NunTerix
|
|
« Ответ #10 : Апрель 25, 2008, 03:09:19 » |
|
Знаю решениЯ, если бы в задаче было указано не 48, а 72 часа ...
|
|
|
|
|
Записан
|
Сердце может прибавить ума, но ум не может прибавить сердца.
|
|
|
LazarusLong
Ирландский доброволец
Проректор
Карма: +181/-7
Offline
Пол: Награды:
Сообщений: 6133
Ukrainian by birth, Irish by the grace of God
|
|
« Ответ #11 : Апрель 25, 2008, 03:36:14 » |
|
Знаю решениЯ, если бы в задаче было указано не 48, а 72 часа ... Увы, нужно решить именно за 48. За 72 задача решается вообще элементарно ))) |
|
|
|
|
Записан
|
Когда ему нужно - он русский, когда нужно - украинец, а когда ему ни хрена не нужно - он ирландец.
"...Он любил говорить факин щит
Когда что-то не так ему
Принимал он свой самый ирландский вид
И кидался трубкой в жену..."
|
|
|
Fr0sT
Очень добрый
Первак
Карма: +3/-0
Offline
Пол:
Сообщений: 45
ИУС 07
|
|
« Ответ #12 : Апрель 25, 2008, 03:45:18 » |
|
Разделим общее кол-во бочек на 16 частей (по 15шт). Первые 5 частей пьют соответственно 1,2,...,5 рабы. Одну часть не пьет никто. Оставшиеся 10 частей пьют сразу 2 раба. (т.е. 1 и 2, 1 и 3 и т.д. Таких сочетаний: С 52=120/12=10). Через 24 умирают либо 2 раба, либо 1, либо 0. Если 0 или 1 - составляем 15 разных групп из 4-5 рабов и через 24 часа узнаем нужную бочку. Если же умерло 2 раба, то аналогично они пробуют по 2 бочки (1 не пробует никто). Дальше  - не хватило рабов(или времени). з.ы. или мозга у меня |
|
|
|
|
Записан
|
Видимо, какая-то постоянная величина оказалась немного переменной... (с) Йон Колфер
|
|
|
LazarusLong
Ирландский доброволец
Проректор
Карма: +181/-7
Offline
Пол: Награды:
Сообщений: 6133
Ukrainian by birth, Irish by the grace of God
|
|
« Ответ #13 : Апрель 25, 2008, 04:06:18 » |
|
Fr0sT, ты на верном пути
|
|
|
|
|
Записан
|
Когда ему нужно - он русский, когда нужно - украинец, а когда ему ни хрена не нужно - он ирландец.
"...Он любил говорить факин щит
Когда что-то не так ему
Принимал он свой самый ирландский вид
И кидался трубкой в жену..."
|
|
|
Fr0sT
Очень добрый
Первак
Карма: +3/-0
Offline
Пол:
Сообщений: 45
ИУС 07
|
|
« Ответ #14 : Апрель 25, 2008, 04:58:57 » |
|
Итоговый вариант
Чтобы определить бочку, необходимо, чтобы на 2ом шаге каждый раб(или их группа) пили только из одной бочки каждый.
Для этого разбиваем кол-во бочек так: 1,2,...,5 пьют из 18 бочек каждый(т.к. 4 оставшихся раба смогут проверить C41+C42+C43+2(1 не пробует никто) бочек), группы по 2 раба пьют из 8 бочек каждая(3 оставшихся могут проверить 8 бочек), группы по 3 раба пьют из 4 бочек.
Тогда 5*18+10*8+10*4+(кол-во пустых бочек)=240
Следовательно, на 1ом шаге необходимо оставить 240-90-80-40=30 бочек.
Если отравленная - среди этих 30, то 5 рабов (никто не умрет) смогут определить нужную.
|
|
|
|
|
Записан
|
Видимо, какая-то постоянная величина оказалась немного переменной... (с) Йон Колфер
|
|
|
LazarusLong
Ирландский доброволец
Проректор
Карма: +181/-7
Offline
Пол: Награды:
Сообщений: 6133
Ukrainian by birth, Irish by the grace of God
|
|
« Ответ #15 : Апрель 25, 2008, 06:29:04 » |
|
Fr0sT, что-то не совсем внятно ты описал кто откуда пьёт.
1,2,3,4,5-й пьют из 18-ти бочек каждый? То есть охватили 72 бочки.
Кстати 4 раба не проверят 18 бочек. Они проверят максимум 16 (16 - 24).
|
|
|
|
|
Записан
|
Когда ему нужно - он русский, когда нужно - украинец, а когда ему ни хрена не нужно - он ирландец.
"...Он любил говорить факин щит
Когда что-то не так ему
Принимал он свой самый ирландский вид
И кидался трубкой в жену..."
|
|
|
Fr0sT
Очень добрый
Первак
Карма: +3/-0
Offline
Пол:
Сообщений: 45
ИУС 07
|
|
« Ответ #16 : Апрель 25, 2008, 06:54:30 » |
|
Кстати 4 раба не проверят 18 бочек. Ошибочка вышла) То есть охватили 72 бочки. А вот этого не понял. Почему не 16*5=80? Получается 16*5+8*10+4*10+2*5=210. Из 30 бочек на 1ом шаге никто не пьет. 5 рабов достаточно |
|
|
|
|
Записан
|
Видимо, какая-то постоянная величина оказалась немного переменной... (с) Йон Колфер
|
|
|
LazarusLong
Ирландский доброволец
Проректор
Карма: +181/-7
Offline
Пол: Награды:
Сообщений: 6133
Ukrainian by birth, Irish by the grace of God
|
|
« Ответ #17 : Апрель 25, 2008, 07:13:45 » |
|
Почему не 16*5=80? Ошибся, с кем не бывает. В общем правильно. +1. Приведу моё решение. Очевидно, что один раб может иметь два состояния - жив и мертв. То есть условно говоря - это один бит информации . Одного раба достаточно для того, что бы проверить две бочки (выпил из одной - если не умер - значит отравлена друга, если умер - значит отравлена та из которой пил). 2 раба могут проверить 4 бочки (1-й выпил из первой бочки, 2-й из второй, из третьей выпили оба из четвертой не пил никто), 3 раба - аналогичным образом проверяют 8 бочек, 4 раба - 16 бочек, 5 рабов - 32 бочки. Таким образом план первой пьянки строим следующим образом: Затем из 10 бочек пьют 5 рабов, причем пьют так, чтобы из каждой бочки выпили только 4 раба. Если отравлена одна из этих 10 - то 4 раба умрут и выживет 1. Он и определит, в какой из двух бочек, из которых не пил, находиться яд. Затем берётся 40 бочек. 5 рабов можно организовать по 3 раба десятью комбинациями. Каждая тройка рабов пьёт из определённых 4 бочек. Если яд будет в одной из этих 40 бочек, тройка умрёт, а оставшиеся 2 раба проверёт доставшиеся им 4 бочки. Затем берётся 80 бочек. 5 рабов можно разбить на пары опять же десятью способами. Если какая-то пара померла, то попробованные ей 8 бочек проверит выжившая тройка. Затем берётся 80 бочек. Каждый раб пьёт из 16ти. Если один умирает, оставшиеся 4 определяют яд в 16ти бочках, опробованных ими. Конец первой пьянки И наконец на вторую попойку можно зарезервировать 32 бочки. Если рабы не умрут, значит яд в этих 32х бочках. За один присест они их проверят. Итак, общее число бочек - 1+10+40+80+80+32 = 243 бочки. Т.е. 5ю рабами можно проверить 243 бочки за два захода |
|
|
|
|
Записан
|
Когда ему нужно - он русский, когда нужно - украинец, а когда ему ни хрена не нужно - он ирландец.
"...Он любил говорить факин щит
Когда что-то не так ему
Принимал он свой самый ирландский вид
И кидался трубкой в жену..."
|
|
|
grimgav
↑ так меня зовут, а это я говорю →
Просто гламурный
Проректор
Карма: +161/-17
Offline
Пол: Награды:
Сообщений: 4636
не ^i^
|
|
« Ответ #18 : Апрель 25, 2008, 08:11:23 » |
|
LazarusLong, а как же 48 часов и смерть в течении 24-х?
|
|
|
|
|
Записан
|
· Я русский ·
|
|
|
LazarusLong
Ирландский доброволец
Проректор
Карма: +181/-7
Offline
Пол: Награды:
Сообщений: 6133
Ukrainian by birth, Irish by the grace of God
|
|
« Ответ #19 : Апрель 25, 2008, 08:21:53 » |
|
grimgav все там соблюдается.
Все действия первой пьянки проводятся сразу.
То есть
1. Все рабы выпили из 1-й бочки.
2. Из 10 бочек пьют 5 рабов, причем пьют так, чтобы из каждой бочки выпили только 4 раба.
3. 40 бочек. Каждая тройка рабов пьёт из определённых 4 бочек.
4. 80 бочек. Из каждой бочки пьет пара рабов.
5. 80 бочек. Каждый раб пьет из 16.
Ждем 24 часа.
Если померли все, значит сработал пункт 1 и ясно какая бочка отравлена.
Если померло только четверо, значит сработал пункт 2. И оставшийся в живых раб может определить из двух бочек из которых он не пил в какой яд.
Если померло трое, значит сработал пункт 3. По тому, какие рабы умерли, мы знаем в каких 4 бочках яд. Оставшиеся 2 рабов определяют в какой конкретно.
Если помрело двое - сработал пункт 4. Оставшиеся трое определяют в какой из 8 бочек был яд.
Если помер 1 - оставшиеся 4 определяют в какой из 16 бочек из которых пил покойник яд.
Если никто не помер - значит яд в одной из оставшихся бочек и 5 рабов легко определяют в какой.
|
|
|
|
|
Записан
|
Когда ему нужно - он русский, когда нужно - украинец, а когда ему ни хрена не нужно - он ирландец.
"...Он любил говорить факин щит
Когда что-то не так ему
Принимал он свой самый ирландский вид
И кидался трубкой в жену..."
|
|
|
Sochin
Злой модератор
Декан
Карма: +108/-6
Offline
Пол:
Сообщений: 1518
|
|
« Ответ #20 : Апрель 25, 2008, 08:42:43 » |
|
А может все-таки электрический вспоминатель недоброжелателю?
|
|
|
|
|
Записан
|
Говорят, когда компьютер сгорает, перед взором микропроцессора за долю секунды проносятся все операции, которые он когда-либо совершил...
壯鎭
|
|
|
Fr0sT
Очень добрый
Первак
Карма: +3/-0
Offline
Пол:
Сообщений: 45
ИУС 07
|
|
« Ответ #21 : Апрель 25, 2008, 08:50:28 » |
|
А если он обманет?
|
|
|
|
|
Записан
|
Видимо, какая-то постоянная величина оказалась немного переменной... (с) Йон Колфер
|
|
|
LazarusLong
Ирландский доброволец
Проректор
Карма: +181/-7
Offline
Пол: Награды:
Сообщений: 6133
Ukrainian by birth, Irish by the grace of God
|
|
« Ответ #22 : Апрель 25, 2008, 08:53:15 » |
|
А может все-таки электрический вспоминатель недоброжелателю? Самое рациональное решение А вообще можно было бы сказать, что задача не имеет решения. Так как патриций вряд ли бы додумался за 48 часов |
|
|
|
|
Записан
|
Когда ему нужно - он русский, когда нужно - украинец, а когда ему ни хрена не нужно - он ирландец.
"...Он любил говорить факин щит
Когда что-то не так ему
Принимал он свой самый ирландский вид
И кидался трубкой в жену..."
|
|
|
|
NunTerix
|
|
« Ответ #23 : Апрель 25, 2008, 09:00:45 » |
|
Я уверен, Решения подобных задач лучше изображать графически, а не письменность ("печатанностью") ... лучше для понимания 
|
|
|
|
|
Записан
|
Сердце может прибавить ума, но ум не может прибавить сердца.
|
|
|
LazarusLong
Ирландский доброволец
Проректор
Карма: +181/-7
Offline
Пол: Награды:
Сообщений: 6133
Ukrainian by birth, Irish by the grace of God
|
|
« Ответ #24 : Апрель 25, 2008, 09:10:44 » |
|
NunTerix, согласен но рисовать сейчас 240 бочек и все варианты как их 5 рабов пьют мнэ.... это несколько трудоемко
|
|
|
|
|
Записан
|
Когда ему нужно - он русский, когда нужно - украинец, а когда ему ни хрена не нужно - он ирландец.
"...Он любил говорить факин щит
Когда что-то не так ему
Принимал он свой самый ирландский вид
И кидался трубкой в жену..."
|
|
|
grimgav
↑ так меня зовут, а это я говорю →
Просто гламурный
Проректор
Карма: +161/-17
Offline
Пол: Награды:
Сообщений: 4636
не ^i^
|
|
« Ответ #25 : Апрель 25, 2008, 10:51:43 » |
|
LazarusLong, просто ВАУ !)
|
|
|
|
|
Записан
|
· Я русский ·
|
|
|
|
