Poisonous drinks

и задачки для интервью.
User avatar
Hoochin
Уже с Приветом
Posts: 1031
Joined: 29 Nov 2006 22:09
Location: Si Valley

Poisonous drinks

Post by Hoochin »

You were given 8 wine bottles. It is known that exactly two bottles have a poison that takes 24 hours to kill anybody.
you have exactly 24 hours to find out which bottles are with poison and you only have 5 lab rats to find out which bottles are with poison.

P.S.:
A simpler problem for starters is if there is only one bottle with poison and you have only 3 lab rats for the same other conditions.
User avatar
vm__
Уже с Приветом
Posts: 11756
Joined: 10 Feb 2005 16:08
Location: CMH

Re: Poisonous drinks

Post by vm__ »

Хлебнуть самому?

Если ещё проще - есть 2 бутылки, в одной - отрава. Как узнать в какой?
User avatar
Hoochin
Уже с Приветом
Posts: 1031
Joined: 29 Nov 2006 22:09
Location: Si Valley

Re: Poisonous drinks

Post by Hoochin »

vm__ wrote:Хлебнуть самому?

Если ещё проще - есть 2 бутылки, в одной - отрава. Как узнать в какой?
думать, типа, влом?
User avatar
rzen
Уже с Приветом
Posts: 24375
Joined: 18 Nov 2003 16:42

Re: Poisonous drinks

Post by rzen »

Крыса-бутылки
1-1,2,3
2-4,5,6
3-7,8
4-1,4,7
5-2,5,8
Don't code today what you can't debug tomorrow.
User avatar
Abappy
Уже с Приветом
Posts: 2555
Joined: 26 Sep 2002 15:45
Location: North-East of NA

Re: Poisonous drinks

Post by Abappy »

Если не укладываться в 24 часа можно крысу сэкономить :)
User avatar
rzen
Уже с Приветом
Posts: 24375
Joined: 18 Nov 2003 16:42

Re: Poisonous drinks

Post by rzen »

Ждать пока одна крыса откинется чтобы потом травить другую по условиям задачи не получается.
Don't code today what you can't debug tomorrow.
User avatar
Abappy
Уже с Приветом
Posts: 2555
Joined: 26 Sep 2002 15:45
Location: North-East of NA

Re: Poisonous drinks

Post by Abappy »

rzen wrote:Ждать пока одна крыса откинется чтобы потом травить другую по условиям задачи не получается.
Угу, я заметил :)
User avatar
rzen
Уже с Приветом
Posts: 24375
Joined: 18 Nov 2003 16:42

Re: Poisonous drinks

Post by rzen »

Abappy wrote:Если не укладываться в 24 часа можно крысу сэкономить :)
Гы! А это мысль! Заставить мыша бегать—выше метаболизм, быстрее сработает яд, экономия крыса :)
Don't code today what you can't debug tomorrow.
User avatar
vm__
Уже с Приветом
Posts: 11756
Joined: 10 Feb 2005 16:08
Location: CMH

Re: Poisonous drinks

Post by vm__ »

Hoochin wrote:
vm__ wrote:Хлебнуть самому?
Если ещё проще - есть 2 бутылки, в одной - отрава. Как узнать в какой?
думать, типа, влом?
:pain1: Почему решение не нравится?
В смысле - налить каждой мышке и себе.
В совсем упрощённом варианте с 2 бутылками и без животных - только себе, только из одной бутылки.
User avatar
rzen
Уже с Приветом
Posts: 24375
Joined: 18 Nov 2003 16:42

Re: Poisonous drinks

Post by rzen »

vm__ wrote:
Hoochin wrote:
vm__ wrote:Хлебнуть самому?
Если ещё проще - есть 2 бутылки, в одной - отрава. Как узнать в какой?
думать, типа, влом?
:pain1: Почему решение не нравится?
В смысле - налить каждой мышке и себе.
В совсем упрощённом варианте с 2 бутылками и без животных - только себе, только из одной бутылки.
Ну вообще то остаться в живых и правда приказа небыло :)
Don't code today what you can't debug tomorrow.
User avatar
Hoochin
Уже с Приветом
Posts: 1031
Joined: 29 Nov 2006 22:09
Location: Si Valley

Re: Poisonous drinks

Post by Hoochin »

rzen wrote:
vm__ wrote:
Hoochin wrote:
vm__ wrote:Хлебнуть самому?
Если ещё проще - есть 2 бутылки, в одной - отрава. Как узнать в какой?
думать, типа, влом?
:pain1: Почему решение не нравится?
В смысле - налить каждой мышке и себе.
В совсем упрощённом варианте с 2 бутылками и без животных - только себе, только из одной бутылки.
Ну вообще то остаться в живых и правда приказа небыло :)

a что мы узнаем если умрем вместе с какими-то крысами. каки бутылки были с ядом?
User avatar
vm__
Уже с Приветом
Posts: 11756
Joined: 10 Feb 2005 16:08
Location: CMH

Re: Poisonous drinks

Post by vm__ »

Hoochin wrote: a что мы узнаем если умрем вместе с какими-то крысами. каки бутылки были с ядом?
"— Извините, не нам, а вам.
— Нет, на этот раз именно вам!" (с) Ы

"Is it true that when a person dies in his sleep, he diesn't know about it until he wakes up the next morning?" (c)
User avatar
Ворона
Уже с Приветом
Posts: 1849
Joined: 06 Mar 2006 20:06

Re: Poisonous drinks

Post by Ворона »

Hoochin wrote:P.S.:A simpler problem for starters is if there is only one bottle with poison and you have only 3 lab rats for the same other conditions.
Ща буду позориться, но очень чешется. Запишем номера бутылок в двоичном виде и дадим попробовать из каждой бутылки след пронумерованным крыскам:
Бутылка/2-й вид/Крысы
1 1 1-я
2 10 2-я
3 11 2-я и 1-я
4 100 3-я
5 101 3-я и 1-я
6 110 3-1 и 2-я
7 111 3-я, 2-я и 1-я
8 1000 никто
Вроде получается уникальная комбинация крыс помрет или не помрет (тогда - 8-я бутылка), нет?
User avatar
Hoochin
Уже с Приветом
Posts: 1031
Joined: 29 Nov 2006 22:09
Location: Si Valley

Re: Poisonous drinks

Post by Hoochin »

Ворона wrote:
Hoochin wrote:P.S.:A simpler problem for starters is if there is only one bottle with poison and you have only 3 lab rats for the same other conditions.
Ща буду позориться, но очень чешется. Запишем номера бутылок в двоичном виде и дадим попробовать из каждой бутылки след пронумерованным крыскам:
Бутылка/2-й вид/Крысы
1 1 1-я
2 10 2-я
3 11 2-я и 1-я
4 100 3-я
5 101 3-я и 1-я
6 110 3-1 и 2-я
7 111 3-я, 2-я и 1-я
8 1000 никто
Вроде получается уникальная комбинация крыс помрет или не помрет (тогда - 8-я бутылка), нет?
ugu.
User avatar
Hoochin
Уже с Приветом
Posts: 1031
Joined: 29 Nov 2006 22:09
Location: Si Valley

Re: Poisonous drinks

Post by Hoochin »

rzen wrote:Крыса-бутылки
1-1,2,3
2-4,5,6
3-7,8
4-1,4,7
5-2,5,8
Умерли 1,2,4-ая крысы. "Где будем делать талию?" - 1&4 ор 3&4?
User avatar
Abappy
Уже с Приветом
Posts: 2555
Joined: 26 Sep 2002 15:45
Location: North-East of NA

Re: Poisonous drinks

Post by Abappy »

Hoochin wrote:
rzen wrote:Крыса-бутылки
1-1,2,3
2-4,5,6
3-7,8
4-1,4,7
5-2,5,8
Умерли 1,2,4-ая крысы. "Где будем делать талию?" - 1&4 ор 3&4?
О, а я проверять не стал, думал решили и ладно. Сейчас решим быстренько :)

Итак. бутылок всего было восемь .. восьмую не дадим никому. Остаётся семь бутылок на пять крыс :)

R1 1,2,3
R2 4,5,6
R3 1,3,5
R4 2,4,6
R5 3,4,7

вроде никого не забыл Ж)
User avatar
Hoochin
Уже с Приветом
Posts: 1031
Joined: 29 Nov 2006 22:09
Location: Si Valley

Re: Poisonous drinks

Post by Hoochin »

Abappy wrote:
Hoochin wrote:
rzen wrote:Крыса-бутылки
1-1,2,3
2-4,5,6
3-7,8
4-1,4,7
5-2,5,8
Умерли 1,2,4-ая крысы. "Где будем делать талию?" - 1&4 ор 3&4?
О, а я проверять не стал, думал решили и ладно. Сейчас решим быстренько :)

Итак. бутылок всего было восемь .. восьмую не дадим никому. Остаётся семь бутылок на пять крыс :)

R1 1,2,3
R2 4,5,6
R3 1,3,5
R4 2,4,6
R5 3,4,7

вроде никого не забыл Ж)
1,2,3,4 откинулись - Б1&Б6 или Б2&Б5?

BTW, the solution doesn't seem to exist. looks like need rat #6)
User avatar
rzen
Уже с Приветом
Posts: 24375
Joined: 18 Nov 2003 16:42

Re: Poisonous drinks

Post by rzen »

Hoochin wrote:BTW, the solution doesn't seem to exist. looks like need rat #6)
экспериментатор!
Don't code today what you can't debug tomorrow.
User avatar
Ворона
Уже с Приветом
Posts: 1849
Joined: 06 Mar 2006 20:06

Re: Poisonous drinks

Post by Ворона »

Hoochin wrote:BTW, the solution doesn't seem to exist. looks like need rat #6)
?? В голове моей опилки.. Я сижу тут в икселе перевожу комбинации бутылок в двоичную систему и вроде достаточно.. Всего ведь 28 комбинаций из 2-х бутылок, нет?
User avatar
Abappy
Уже с Приветом
Posts: 2555
Joined: 26 Sep 2002 15:45
Location: North-East of NA

Re: Poisonous drinks

Post by Abappy »

Hoochin wrote:
Abappy wrote: Итак. бутылок всего было восемь .. восьмую не дадим никому. Остаётся семь бутылок на пять крыс :)

R1 1,2,3
R2 4,5,6
R3 1,3,5
R4 2,4,6
R5 3,4,7

вроде никого не забыл Ж)
1,2,3,4 откинулись - Б1&Б6 или Б2&Б5?
сейчас подумаю :)
User avatar
Ворона
Уже с Приветом
Posts: 1849
Joined: 06 Mar 2006 20:06

Re: Poisonous drinks

Post by Ворона »

Hoochin wrote:
Ворона wrote:
Hoochin wrote:P.S.:A simpler problem for starters is if there is only one bottle with poison and you have only 3 lab rats for the same other conditions.
Ща буду позориться, но очень чешется. Запишем номера бутылок в двоичном виде и дадим попробовать из каждой бутылки след пронумерованным крыскам:
Бутылка/2-й вид/Крысы
1 1 1-я
2 10 2-я
3 11 2-я и 1-я
4 100 3-я
5 101 3-я и 1-я
6 110 3-1 и 2-я
7 111 3-я, 2-я и 1-я
8 1000 никто
Вроде получается уникальная комбинация крыс помрет или не помрет (тогда - 8-я бутылка), нет?
ugu.
Ну тогда по аналогии :oops:
Бутылки/ N коктейля/Двоичый код/Крысы
12 1 00001 1-я
13 2 00010 2-я
14 3 00011 2-я и 1-я
15 4 00100 3-я
16 5 00101 3-я и 1-я
17 6 00110 3-я и 2-я
18 7 00111 3-я, 2-я и 1-я
23 8 01000 4-я
24 9 01001 4 &1
25 10 01010 4 &2
26 11 01011 и тд
27 12 01100
28 13 01101
34 14 01110
35 15 01111
36 16 10000
37 17 10001
38 18 10010
45 19 10011
46 20 10100
47 21 10101
48 22 10110
56 23 10111
57 24 11000
58 25 11001
67 26 11010
68 27 11011
78 28 11100
User avatar
Hoochin
Уже с Приветом
Posts: 1031
Joined: 29 Nov 2006 22:09
Location: Si Valley

Re: Poisonous drinks

Post by Hoochin »

Ворона wrote:
Hoochin wrote:
Ворона wrote:
Hoochin wrote:P.S.:A simpler problem for starters is if there is only one bottle with poison and you have only 3 lab rats for the same other conditions.
Ща буду позориться, но очень чешется. Запишем номера бутылок в двоичном виде и дадим попробовать из каждой бутылки след пронумерованным крыскам:
Бутылка/2-й вид/Крысы
1 1 1-я
2 10 2-я
3 11 2-я и 1-я
4 100 3-я
5 101 3-я и 1-я
6 110 3-1 и 2-я
7 111 3-я, 2-я и 1-я
8 1000 никто
Вроде получается уникальная комбинация крыс помрет или не помрет (тогда - 8-я бутылка), нет?
ugu.
Ну тогда по аналогии :oops:
Бутылки/ N коктейля/Двоичый код/Крысы
12 1 00001 1-я
13 2 00010 2-я
14 3 00011 2-я и 1-я
15 4 00100 3-я
16 5 00101 3-я и 1-я
17 6 00110 3-я и 2-я
18 7 00111 3-я, 2-я и 1-я
23 8 01000 4-я
24 9 01001 4 &1
25 10 01010 4 &2
26 11 01011 и тд
27 12 01100
28 13 01101
34 14 01110
35 15 01111
36 16 10000
37 17 10001
38 18 10010
45 19 10011
46 20 10100
47 21 10101
48 22 10110
56 23 10111
57 24 11000
58 25 11001
67 26 11010
68 27 11011
78 28 11100
Проблема в том, что , скажем, если умерли 01111, т.е. все кроме 5-ой,
то значит ли что только Б3 и 4 с ядом?
и более главное - у вас умрут все 5 КРЫС, так как вы их всех попоили по многу раз изо всеx 8-и бутылок...
User avatar
Ворона
Уже с Приветом
Posts: 1849
Joined: 06 Mar 2006 20:06

Re: Poisonous drinks

Post by Ворона »

Hoochin wrote:Проблема в том, что , скажем, если умерли 01111, т.е. все кроме 5-ой,
то значит ли что только Б3 и 4 с ядом? ..
Да, недоработочка :D :oops:
Hamster
Уже с Приветом
Posts: 11475
Joined: 20 Nov 2000 10:01
Location: Escondido, CA

Re: Poisonous drinks

Post by Hamster »

Подойдем к вопросу систематически.

Каждой бутылке сопоставим 5-значный бинарный код B(n), n=1..8. Все коды должны отличаться друг от друга.

У нас есть 28 возможных пар бутылок. Каждая пара дает нам новый 5-значный код B(x) | B(y). Для правильного решения все 28 пар должны давать разные коды.

На выходе не должно получаться комбинации 00000 (максимум одну бутылку не пьет никто).

На входе ни у одной бутылки не должно быть кода более чем с двумя единицами. (Если у какой-то бутылки есть код с тремя единицами и она отравлена, три крысы умирают, 4 комбинаций оставшихся крыс недостаточно, чтобы найти вторую отравленную бутылку).

Следовательно, на выходе не получится кода 11111.

Должны реализоваться 28 комбинаций из 30 оставшихся. Значит, на выходе должно получаться как минимум три из пяти комбинаций 00001, 00010, 00100, 01000, 10000. Можно без потери общности принять, что реализуются 00001, 00010, 00100, это значит, что на входе есть коды 00000, 00001, 00010, 00100.

Заметим, что, если на входе есть коды (00000, 00001), это исключает наличие кодов (xxxx1) для любых значений x, потому что мы не можем различить (00000 | xxxx1) и (00001 | xxxx1).

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

Задача не имеет решения.
Протоукр
User avatar
Abappy
Уже с Приветом
Posts: 2555
Joined: 26 Sep 2002 15:45
Location: North-East of NA

Re: Poisonous drinks

Post by Abappy »

Hamster wrote:На входе ни у одной бутылки не должно быть кода более чем с двумя единицами. (Если у какой-то бутылки есть код с тремя единицами и она отравлена, три крысы умирают, 4 комбинаций оставшихся крыс недостаточно, чтобы найти вторую отравленную бутылку).

Следовательно, на выходе не получится кода 11111.
Может быть конечно вечер, но я этого момента не понял :(

Return to “Головоломки”