Poisonous drinks
-
- Уже с Приветом
- Posts: 1031
- Joined: 29 Nov 2006 22:09
- Location: Si Valley
Poisonous drinks
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.
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.
-
- Уже с Приветом
- Posts: 11756
- Joined: 10 Feb 2005 16:08
- Location: CMH
Re: Poisonous drinks
Хлебнуть самому?
Если ещё проще - есть 2 бутылки, в одной - отрава. Как узнать в какой?
Если ещё проще - есть 2 бутылки, в одной - отрава. Как узнать в какой?
-
- Уже с Приветом
- Posts: 1031
- Joined: 29 Nov 2006 22:09
- Location: Si Valley
Re: Poisonous drinks
думать, типа, влом?vm__ wrote:Хлебнуть самому?
Если ещё проще - есть 2 бутылки, в одной - отрава. Как узнать в какой?
-
- Уже с Приветом
- Posts: 24375
- Joined: 18 Nov 2003 16:42
Re: Poisonous drinks
Крыса-бутылки
1-1,2,3
2-4,5,6
3-7,8
4-1,4,7
5-2,5,8
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.
-
- Уже с Приветом
- Posts: 2555
- Joined: 26 Sep 2002 15:45
- Location: North-East of NA
Re: Poisonous drinks
Если не укладываться в 24 часа можно крысу сэкономить
-
- Уже с Приветом
- Posts: 24375
- Joined: 18 Nov 2003 16:42
Re: Poisonous drinks
Ждать пока одна крыса откинется чтобы потом травить другую по условиям задачи не получается.
Don't code today what you can't debug tomorrow.
-
- Уже с Приветом
- Posts: 2555
- Joined: 26 Sep 2002 15:45
- Location: North-East of NA
Re: Poisonous drinks
Угу, я заметилrzen wrote:Ждать пока одна крыса откинется чтобы потом травить другую по условиям задачи не получается.
-
- Уже с Приветом
- Posts: 24375
- Joined: 18 Nov 2003 16:42
Re: Poisonous drinks
Гы! А это мысль! Заставить мыша бегать—выше метаболизм, быстрее сработает яд, экономия крысаAbappy wrote:Если не укладываться в 24 часа можно крысу сэкономить
Don't code today what you can't debug tomorrow.
-
- Уже с Приветом
- Posts: 11756
- Joined: 10 Feb 2005 16:08
- Location: CMH
Re: Poisonous drinks
Почему решение не нравится?Hoochin wrote:думать, типа, влом?vm__ wrote:Хлебнуть самому?
Если ещё проще - есть 2 бутылки, в одной - отрава. Как узнать в какой?
В смысле - налить каждой мышке и себе.
В совсем упрощённом варианте с 2 бутылками и без животных - только себе, только из одной бутылки.
-
- Уже с Приветом
- Posts: 24375
- Joined: 18 Nov 2003 16:42
Re: Poisonous drinks
Ну вообще то остаться в живых и правда приказа небылоvm__ wrote:Почему решение не нравится?Hoochin wrote:думать, типа, влом?vm__ wrote:Хлебнуть самому?
Если ещё проще - есть 2 бутылки, в одной - отрава. Как узнать в какой?
В смысле - налить каждой мышке и себе.
В совсем упрощённом варианте с 2 бутылками и без животных - только себе, только из одной бутылки.
Don't code today what you can't debug tomorrow.
-
- Уже с Приветом
- Posts: 1031
- Joined: 29 Nov 2006 22:09
- Location: Si Valley
Re: Poisonous drinks
rzen wrote:Ну вообще то остаться в живых и правда приказа небылоvm__ wrote:Почему решение не нравится?Hoochin wrote:думать, типа, влом?vm__ wrote:Хлебнуть самому?
Если ещё проще - есть 2 бутылки, в одной - отрава. Как узнать в какой?
В смысле - налить каждой мышке и себе.
В совсем упрощённом варианте с 2 бутылками и без животных - только себе, только из одной бутылки.
a что мы узнаем если умрем вместе с какими-то крысами. каки бутылки были с ядом?
-
- Уже с Приветом
- Posts: 11756
- Joined: 10 Feb 2005 16:08
- Location: CMH
Re: Poisonous drinks
"— Извините, не нам, а вам.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)
-
- Уже с Приветом
- Posts: 1849
- Joined: 06 Mar 2006 20:06
Re: Poisonous drinks
Ща буду позориться, но очень чешется. Запишем номера бутылок в двоичном виде и дадим попробовать из каждой бутылки след пронумерованным крыскам: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-я бутылка), нет?
-
- Уже с Приветом
- Posts: 1031
- Joined: 29 Nov 2006 22:09
- Location: Si Valley
Re: Poisonous drinks
ugu.Ворона 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-я бутылка), нет?
-
- Уже с Приветом
- Posts: 1031
- Joined: 29 Nov 2006 22:09
- Location: Si Valley
Re: Poisonous drinks
Умерли 1,2,4-ая крысы. "Где будем делать талию?" - 1&4 ор 3&4?rzen wrote:Крыса-бутылки
1-1,2,3
2-4,5,6
3-7,8
4-1,4,7
5-2,5,8
-
- Уже с Приветом
- Posts: 2555
- Joined: 26 Sep 2002 15:45
- Location: North-East of NA
Re: Poisonous drinks
О, а я проверять не стал, думал решили и ладно. Сейчас решим быстренькоHoochin wrote:Умерли 1,2,4-ая крысы. "Где будем делать талию?" - 1&4 ор 3&4?rzen wrote:Крыса-бутылки
1-1,2,3
2-4,5,6
3-7,8
4-1,4,7
5-2,5,8
Итак. бутылок всего было восемь .. восьмую не дадим никому. Остаётся семь бутылок на пять крыс
R1 1,2,3
R2 4,5,6
R3 1,3,5
R4 2,4,6
R5 3,4,7
вроде никого не забыл Ж)
-
- Уже с Приветом
- Posts: 1031
- Joined: 29 Nov 2006 22:09
- Location: Si Valley
Re: Poisonous drinks
1,2,3,4 откинулись - Б1&Б6 или Б2&Б5?Abappy wrote:О, а я проверять не стал, думал решили и ладно. Сейчас решим быстренькоHoochin wrote:Умерли 1,2,4-ая крысы. "Где будем делать талию?" - 1&4 ор 3&4?rzen wrote:Крыса-бутылки
1-1,2,3
2-4,5,6
3-7,8
4-1,4,7
5-2,5,8
Итак. бутылок всего было восемь .. восьмую не дадим никому. Остаётся семь бутылок на пять крыс
R1 1,2,3
R2 4,5,6
R3 1,3,5
R4 2,4,6
R5 3,4,7
вроде никого не забыл Ж)
BTW, the solution doesn't seem to exist. looks like need rat #6)
-
- Уже с Приветом
- Posts: 24375
- Joined: 18 Nov 2003 16:42
Re: Poisonous drinks
экспериментатор!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.
-
- Уже с Приветом
- Posts: 1849
- Joined: 06 Mar 2006 20:06
Re: Poisonous drinks
?? В голове моей опилки.. Я сижу тут в икселе перевожу комбинации бутылок в двоичную систему и вроде достаточно.. Всего ведь 28 комбинаций из 2-х бутылок, нет?Hoochin wrote:BTW, the solution doesn't seem to exist. looks like need rat #6)
-
- Уже с Приветом
- Posts: 2555
- Joined: 26 Sep 2002 15:45
- Location: North-East of NA
Re: Poisonous drinks
сейчас подумаюHoochin wrote:1,2,3,4 откинулись - Б1&Б6 или Б2&Б5?Abappy wrote: Итак. бутылок всего было восемь .. восьмую не дадим никому. Остаётся семь бутылок на пять крыс
R1 1,2,3
R2 4,5,6
R3 1,3,5
R4 2,4,6
R5 3,4,7
вроде никого не забыл Ж)
-
- Уже с Приветом
- Posts: 1849
- Joined: 06 Mar 2006 20:06
Re: Poisonous drinks
Ну тогда по аналогииHoochin wrote:ugu.Ворона 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-я бутылка), нет?
Бутылки/ 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
-
- Уже с Приветом
- Posts: 1031
- Joined: 29 Nov 2006 22:09
- Location: Si Valley
Re: Poisonous drinks
Проблема в том, что , скажем, если умерли 01111, т.е. все кроме 5-ой,Ворона wrote:Ну тогда по аналогииHoochin wrote:ugu.Ворона 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-я бутылка), нет?
Бутылки/ 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
то значит ли что только Б3 и 4 с ядом?
и более главное - у вас умрут все 5 КРЫС, так как вы их всех попоили по многу раз изо всеx 8-и бутылок...
-
- Уже с Приветом
- Posts: 1849
- Joined: 06 Mar 2006 20:06
Re: Poisonous drinks
Да, недоработочкаHoochin wrote:Проблема в том, что , скажем, если умерли 01111, т.е. все кроме 5-ой,
то значит ли что только Б3 и 4 с ядом? ..
-
- Уже с Приветом
- Posts: 11475
- Joined: 20 Nov 2000 10:01
- Location: Escondido, CA
Re: Poisonous drinks
Подойдем к вопросу систематически.
Каждой бутылке сопоставим 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, но это невозможно, потому что таких неиспользованных кодов осталось всего три.
Задача не имеет решения.
Каждой бутылке сопоставим 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, но это невозможно, потому что таких неиспользованных кодов осталось всего три.
Задача не имеет решения.
Протоукр
-
- Уже с Приветом
- Posts: 2555
- Joined: 26 Sep 2002 15:45
- Location: North-East of NA
Re: Poisonous drinks
Может быть конечно вечер, но я этого момента не понялHamster wrote:На входе ни у одной бутылки не должно быть кода более чем с двумя единицами. (Если у какой-то бутылки есть код с тремя единицами и она отравлена, три крысы умирают, 4 комбинаций оставшихся крыс недостаточно, чтобы найти вторую отравленную бутылку).
Следовательно, на выходе не получится кода 11111.