Re[5]: Отравленное вино - Этюды для программистов

Здравствуйте, HeaveN, Вы писали:

HN>Задачка такая пробежала...

HN>

Вы, правитель империи, решили устроить пир, который состоится ровно через один месяц. Чтобы обеспечить застолье должным количеством вина, вами было приказано от каждой провинции доставить к императорскому двору по одной бочке с вином. В империи 1000 провинций... — 1000 бочек уже стоят в вашем погребе, все прекрасно. Но ваши разведчики внезапно долкладывают вам о том, что в одной из бочек вино отравлено, естесственно неизвестно в какой. Яд действует медленно и коварно — один месяц, и после этого выпивший хотя бы один стакан вина умирает. Нужно точно определить к началу пира в какой бочке яд и не допустить вымирания правящей династии.
HN>Есть 2 постановки вопроса для решения:

HN>1. Какое минимальное число слуг можно задействовать и как?

HN>2. Какое минимальное количество вина можно израсходовать и как?

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

PS если династия большая — то сосчитать необходимое количество бочек...

Пить из каждой бочки меньше стакана и никто не умрет

1000 заходов по полстакана мне бы хватило

Задачка такая пробежала...

Вы, правитель империи, решили устроить пир, который состоится ровно через один месяц. Чтобы обеспечить застолье должным количеством вина, вами было приказано от каждой провинции доставить к императорскому двору по одной бочке с вином. В империи 1000 провинций... — 1000 бочек уже стоят в вашем погребе, все прекрасно. Но ваши разведчики внезапно долкладывают вам о том, что в одной из бочек вино отравлено, естесственно неизвестно в какой. Яд действует медленно и коварно — один месяц, и после этого выпивший хотя бы один стакан вина умирает. Нужно точно определить к началу пира в какой бочке яд и не допустить вымирания правящей династии.
Есть 2 постановки вопроса для решения:

1. Какое минимальное число слуг можно задействовать и как?

2. Какое минимальное количество вина можно израсходовать и как?

... << RSDN@Home 1.1.4 beta 2 rev. 183>>

Здравствуйте, HeaveN, Вы писали:

HN>Задачка такая пробежала...

HN>Вы, правитель империи, решили устроить пир, который состоится ровно через один месяц. Чтобы обеспечить застолье должным количеством вина, вами было приказано от каждой провинции доставить к императорскому двору по одной бочке с вином. В империи 1000 провинций... — 1000 бочек уже стоят в вашем погребе, все прекрасно. Но ваши разведчики внезапно долкладывают вам о том, что в одной из бочек вино отравлено, естесственно неизвестно в какой. Яд действует медленно и коварно — один месяц, и после этого выпивший хотя бы один стакан вина умирает. Нужно точно определить к началу пира в какой бочке яд и не допустить вымирания правящей династии.
HN>Есть 2 постановки вопроса для решения:

HN>1. Какое минимальное число слуг можно задействовать и как?

Представим номера бочек в двоичном виде (0 = дегустатор N не отпивает, 1 = дегустатор N отпивает), для этого понадобиться 10 разрядов-дегустаторов (2^10 = 1024). Чтобы при этом минимизировать кол-во выпитого вина можно похитрить с кодировкой, но экономия будет копеечная.

HN>2. Какое минимальное количество вина можно израсходовать и как?

999 дегустаторов, каждый отпивает по 1 стакану из персональной бочки.

Боюсь что слуга, отвечающий за младший бит не выдержит, ведь ему придется выпить 500 стаканов

Здравствуйте, Блудов Павел, Вы писали:

БП>Если умрет А значит 1-я.
БП>Если умрет В значит 3-я.
БП>Если оба значит 2-я.
БП>Если никто значит 4-я.

БП>Павел.

я точно так же считал

Простое решение:
у меня так же получилось 666 слуг (КС) для 1000 бочек (КБ):

КБ % 3 = 0, КС = (КБ/3) * 2
КБ % 3 = 1, КС = (КБ/3) * 2 //одна пустая бочка
КБ % 3 = 2, КС = (КБ/3) * 2 + 1 //один слуга и пустая бочка

Нестандартное решение:
Свести задачу к минимизации яда. Т.е. для отравления одного человека необходимо и достаточно 1 стакан. Следовательно, необходимо смешать между собой бочки и смесь снова разлить.

Ответ 2 слуг (тоскают бочки), 0 стаканов вина.

... << RSDN@Home 1.1.4 beta 3 rev. 185>>

Здравствуйте, Tan4ik, Вы писали:

HN>>1. Какое минимальное число слуг можно задействовать и как?

T>Я вот что подумал. Все тут предлагают напоить десятерых слуг и по умершим определить отравленную бочку. Но... А вдруг кто-то из слуг умрет не по вине яда? (а из-за недостаточной моральной стойкости, например). Тогда у нас на пиру будет много трупов. В таком вопросе слуг экономить не надо.

Можно просто перестраховаться — отбраковать максимум 10 бочек, сбрасывая по очереди каждую едничку полученного кода.

T>Вариант решения: напоить два комплекта по 10 слуг и считать бит взведенным, только если слуга умер в обеих комплектах.
T>Вопрос: можно ли уменьшить количество задействованных слуг для определения отравленной бочки при условии возможности не более одной случайной сметри?

Для упрощения предположим что возможна одиночная ошибка не только 0->1, но и 1->0. Тогда одна "полезная" комбинация сделает недопустимыми для использования еще n "страховочных" комбинаций, где n — количество бит. В самом деле, код 1100 запрещает к использованию коды 1000, 0100, 1110, 1101. Получаем формулу 2^n = 1000*(n+1), где 1000 — кол-во полезных комбинаций (бочек). Подбираем ближайшее сверху целое — 14.

Это конечно неточная оценка, во-1х неясно, возможно ли настолько плотно упаковать коды, чтобы на каждую полезную комбинацию приходилось ровно 14 страховочных. Так что реально количество полезных комбинаций может быть меньше. Но с другой стороны по условию нашей задачи ошибка 1->0 невозможна (выпивший отравы не может выжить), так что количество полезных кодов может быть больше. Поскольку ничего лучше придумать не могу, то пусть будет 14 слуг.

Теперь попробуем подобрать коды.
Обозначим кол-во единичек в коде X как 1(X). Код X достижим из кода Y, если X может быть получен из Y установкой одного 0 в 1. Ясно что 1(X xor Y) == 1.
Еще следует опасаться ситуаций, когда из X и Y достижим один и тот же код Z. Ясно что 1(X) == 1(Y) и 1(X xor Y) == 2. С помощью тупого перебора с проверкой этих условий получаем 1051 полезную комбинацию для 14 бит, этого вполне достаточно.

Вряд ли это наилучшее решение, но если мне не изменяет склероз, это не хуже кода Хемминга, в котором 4 полезных бита дополнялись еще 3 избыточными.

Вот код перебора:

#include <stdio.h>

typedef unsigned short ushort;

// кол-во взведенных битов 
ushort bitsAt1(ushort x)
{
  x = (x & 0x5555) + ((x >> 1) & 0x5555);
  x = (x & 0x3333) + ((x >> 2) & 0x3333);
  x = (x & 0x0f0f) + ((x >> 4) & 0x0f0f);
  x = (x & 0x00ff) + ((x >> 8) & 0x00ff);
  return x;
}

bool isConflict(ushort x, ushort y)
{
  ushort diff = bitsAt1( x ^ y );
  if( diff > 2 ) return false;
  if( diff == 2 && bitsAt1(x) != bitsAt1(y) ) return false;
  return true;
}

int main()
{
  enum { Bits = 14 };
  enum { MaxCodes = 1 << Bits };
  ushort codes[MaxCodes]; // массив заведомо больше чем надо
  ushort cnt = 0;
    
  for( ushort n = 0; n < MaxCodes; ++n )
  {
    for( ushort i = 0; i < cnt ; ++i )
      if( isConflict( n, codes[i] ) ) goto ignore;
    codes[cnt++] = n;
    printf("%04x ", n);
ignore: ;
  }
    
  printf("\nCodes count: %u\n", cnt);
}

Привет!

HeaveN wrote:
>
> Задачка такая пробежала...
>
> [q]Вы, правитель империи, решили устроить пир, который состоится ровно через один месяц. Чтобы обеспечить застолье должным количеством вина, вами было приказано от каждой провинции доставить к императорскому двору по одной бочке с вином. В империи 1000 провинций... — 1000 бочек уже стоят в вашем погребе, все прекрасно. Но ваши разведчики внезапно долкладывают вам о том, что в одной из бочек вино отравлено, естесственно неизвестно в какой. Яд действует медленно и коварно — один месяц, и после этого выпивший хотя бы один стакан вина умирает. Нужно точно определить к началу пира в какой бочке яд и не допустить вымирания правящей династии.
> Есть 2 постановки вопроса для решения:
>
> 1. Какое минимальное число слуг можно задействовать и как?

А сколько вина в состоянии несчастный слуга выпить за один день ? Если
ему споить 1000 стаканов — помрет, даже если не отравлено

--
With best regards,
Pavel Dvorkin

Posted via RSDN NNTP Server 1.8

Здравствуйте, HeaveN, Вы писали:

HN>1. Какое минимальное число слуг можно задействовать и как?

Я вот что подумал. Все тут предлагают напоить десятерых слуг и по умершим определить отравленную бочку. Но... А вдруг кто-то из слуг умрет не по вине яда? (а из-за недостаточной моральной стойкости, например). Тогда у нас на пиру будет много трупов. В таком вопросе слуг экономить не надо.
Вариант решения: напоить два комплекта по 10 слуг и считать бит взведенным, только если слуга умер в обеих комплектах.
Вопрос: можно ли уменьшить количество задействованных слуг для определения отравленной бочки при условии возможности не более одной случайной сметри?

Здравствуйте, sergey_shandar, Вы писали:

_>Здравствуйте, Аноним, Вы писали:

А>>Боюсь что слуга, отвечающий за младший бит не выдержит, ведь ему придется выпить 500 стаканов

_>И остальные тоже, так как практически каждому придеться пить почти 500 стаканов, а не одному!

_>Первый — третий: 500
_>Четвертый: 500 — 8 = 492
_>Пятый — десятый: 500 — 24 = 476
Хорош жрать, мне оставьте

Здравствуйте, Аноним, Вы писали:

F>>Представим номера бочек в двоичном виде (0 = дегустатор N не отпивает, 1 = дегустатор N отпивает), для этого понадобиться 10 разрядов-дегустаторов (2^10 = 1024). Чтобы при этом минимизировать кол-во выпитого вина можно похитрить с кодировкой, но экономия будет копеечная.

А>Так как есть небольшой запас до 1024, то при правильной кодировке выживут не меньше 2-х из 10 слуг, так что будет кому разносить...

пиво

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

Здравствуйте, Bathory, Вы писали:

B>Вот в условиях не сказанно про силу яда,
Какраз сказано.

HN>>Яд действует медленно и коварно — один месяц, и после этого выпивший хотя бы один стакан вина умирает.
Из этого следует, что доза менее одного стакана несмертельна.

Здравствуйте, Gandalf_The_Grey, Вы писали:
G_T>Если для того, чтоб сдохнуть нужно выпить стакан, то просто делаем смесь по ПОЛСТАКАНА из каждой бочки.
G_T>Полученная смесь будет не смертельной и ее хватит, чтоб упиться всем в зюзю.
А ну как вино разных сортов?

Зюзя получится знатная

Д.К. << RSDN@Home 1.1.4 beta 2>> слушаем Nightwish — Ocean Soul

Здравствуйте, conraddk, Вы писали:

C>Здравствуйте, Gandalf_The_Grey, Вы писали:
G_T>>Если для того, чтоб сдохнуть нужно выпить стакан, то просто делаем смесь по ПОЛСТАКАНА из каждой бочки.
G_T>>Полученная смесь будет не смертельной и ее хватит, чтоб упиться всем в зюзю.
C>А ну как вино разных сортов?

Зюзя получится знатная

Ну неужто в 1000 бочках разные сорта вин?

Можно мешать сорта с сортами, а ершики давать желающим.
Наверняка от них отбою не будут, потому что просто вином надо долго догоняться

И все будут рады. никто не помрет

Здравствуйте, HeaveN, Вы писали:

HN>1. Какое минимальное число слуг можно задействовать и как?

Слуг??? Да ни за что. Создатели этого вина надо заставить пробовать свое изделие.

Здравствуйте, HeaveN, Вы писали:

HN>Задачка такая пробежала...

HN>

Вы, правитель империи, решили устроить пир, который состоится ровно через один месяц. Чтобы обеспечить застолье должным количеством вина, вами было приказано от каждой провинции доставить к императорскому двору по одной бочке с вином. В империи 1000 провинций... — 1000 бочек уже стоят в вашем погребе, все прекрасно. Но ваши разведчики внезапно долкладывают вам о том, что в одной из бочек вино отравлено, естесственно неизвестно в какой. Яд действует медленно и коварно — один месяц, и после этого выпивший хотя бы один стакан вина умирает. Нужно точно определить к началу пира в какой бочке яд и не допустить вымирания правящей династии.
HN>Есть 2 постановки вопроса для решения:

HN>1. Какое минимальное число слуг можно задействовать и как?

HN>2. Какое минимальное количество вина можно израсходовать и как?

Раасмотрим общий случай:

Пусть N — количество бочек, а K — количество слуг.

для каждой бочки строим вектор из K элементов: в этом векторе i-ый элемент
равен 1, если слуга номер i выпил стакан из этой бочки. Если не выпил, то 0.
Таким образом, имеем N штук векторов.
Для того, чтобы обнозначно идентифицировать бочку надо, чтобы никакие два
из этих векторов не были идентичны.
Т.е. нам нужно N штук различных двоичных векторов длины K.

отсюда минимальное K = [log2(N)] + 1

То есть в нашем случае минимальное количество слуг — 10.

Если наша задача — минимизировать количество выпитого вина, то тогда решение
тривиально — 999 слуг. Т.к. из 999 бочек нужно выпить как минимум 1 стакан,
чтобы определить отравленную бочку.

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>А сколько вина в состоянии несчастный слуга выпить за один день ? Если
PD>ему споить 1000 стаканов — помрет, даже если не отравлено

Это ничего не даст — по условиям задачи он умрет ровно через месяц. И неизвестно, из-за какого именно стакана.

... << RSDN@Home 1.1.4 beta 2 >>

Здравствуйте, HeaveN, Вы писали:

HN>1. Какое минимальное число слуг можно задействовать и как?
0

HN>2. Какое минимальное количество вина можно израсходовать и как? [/q]
0

как?
пронумеруем бочки от 1 до 1000.
в бочке под номером 666 вино отравлено!

Здравствуйте, HeaveN, Вы писали:

HN>Задачка такая пробежала...

HN>Вы, правитель империи, решили устроить пир, который состоится ровно через один месяц. Чтобы обеспечить застолье должным количеством вина, вами было приказано от каждой провинции доставить к императорскому двору по одной бочке с вином. В империи 1000 провинций... — 1000 бочек уже стоят в вашем погребе, все прекрасно. Но ваши разведчики внезапно долкладывают вам о том, что в одной из бочек вино отравлено, естесственно неизвестно в какой. Яд действует медленно и коварно — один месяц, и после этого выпивший хотя бы один стакан вина умирает. Нужно точно определить к началу пира в какой бочке яд и не допустить вымирания правящей династии.
HN>Есть 2 постановки вопроса для решения:

HN>1. Какое минимальное число слуг можно задействовать и как?

10 слуг. Для примера берем 8 бочек. Составляем таблицу:

01010101
00110011
00001111

Для каждой бочки свой столбец, для каждого слуги — своя строка. Слуга выпивает по стакану в соответствии с таблицей, а через месяц вычисляем бочку.

HN>2. Какое минимальное количество вина можно израсходовать и как?

Берем 1000 слуг и каждый по стакану выпивает из своей бочки. Через месяц смотрим, который из них скопытится.

Еще вариант: смешиваем все вина из всех бочек, и тогда концентрация яда будем несмертельной.

Привет!

Блудов Павел wrote:
>
> Здравствуйте, Pavel Dvorkin, Вы писали:
>
> PD>А сколько вина в состоянии несчастный слуга выпить за один день ? Если
> PD>ему споить 1000 стаканов — помрет, даже если не отравлено

>
> Это ничего не даст — по условиям задачи он умрет ровно через месяц. И неизвестно, из-за какого именно стакана.

Естественно, в таком виде это ничего не даст. Но мой вопрос в другом
заключается — сколько стаканов можно одному дать ?

К примеру, пусть всего 3 бочки

А пьет из 1 и 2
Б пьет из 2 и 3
В пьет из 3 и 1

Умрут А и В — отравлена 1-я, А и Б — вторая и т.д.

Я не говорю, что это хорошее решение, но ИМХО знать, сколько можно
споить каждому, необходимо.

--
With best regards,
Pavel Dvorkin

Posted via RSDN NNTP Server 1.8

Здравствуйте, Аноним, Вы писали:

А>Боюсь что слуга, отвечающий за младший бит не выдержит, ведь ему придется выпить 500 стаканов

Наcколько я понял каждый бит это бочка.

Здравствуйте, HeaveN, Вы писали:

HN>Задачка такая пробежала...

HN>[q]Вы, правитель империи, решили устроить пир, который состоится ровно через один месяц. Чтобы обеспечить застолье должным количеством вина, вами было приказано от каждой провинции доставить к императорскому двору по одной бочке с вином. В империи 1000 провинций... — 1000 бочек уже стоят в вашем погребе, все прекрасно. Но ваши разведчики внезапно долкладывают вам о том, что в одной из бочек вино отравлено, естесственно неизвестно в какой. Яд действует медленно и коварно — один месяц, и после этого выпивший хотя бы один стакан вина умирает. Нужно точно определить к началу пира в какой бочке яд и не допустить вымирания правящей династии.
HN>Есть 2 постановки вопроса для решения:

HN>1. Какое минимальное число слуг можно задействовать и как?

Ставим бочки в виде матрицы 10 x 10 x 10 — при это нам потребуется 10 + 10 + 10 = 30 слуг, чтобы первые 10 слуг попробовали все бочки в соответсвующих строках (номер слуги = номер строки), вторые 10 — все бочки в столбцах, а третьи — по вертикали. Т.е. каждый слуга попробует "слой" из 100 бочек. При это умрут 3 слуги на, на пересечении номеров которых и находилась бочка с ядом.

Если пробовать 100 бочек силы нет, то можно ограничиться двумерной матрицей 32 x 32 = 1024 при этом 24 места оставим пустыми, и умрут только 2 слуги, а на каждого из 32 + 32 — 24 = 40 слуг придется по 32 бочки. Здесь нужно 64 слуги

Ты понял неправильно

И остальные тоже, так как практически каждому придеться пить почти 500 стаканов, а не одному!

Первый — третий: 500
Четвертый: 500 — 8 = 492
Пятый — десятый: 500 — 24 = 476

Здравствуйте, Socrat, Вы писали:

S>...

Все правильно, только это уже было: Решение folk.

S>Еще вариант: смешиваем все вина из всех бочек, и тогда концентрация яда будем несмертельной.

И это было (немного в другом виде): Решение анонима.

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Естественно, в таком виде это ничего не даст. Но мой вопрос в другом
PD>заключается — сколько стаканов можно одному дать ?

Ну литров 10 в день сможет любой. Если это вино — Сангрия. Если наливать по 20 грам, то будет 500 порций.

PD>К примеру, пусть всего 3 бочки

PD>А пьет из 1 и 2
PD>Б пьет из 2 и 3
PD>В пьет из 3 и 1

PD>Умрут А и В — отравлена 1-я, А и Б — вторая и т.д.

Тут хватит двух слуг:
PD>А пьет из 1 и 2
PD>Б пьет из 2 и 3

Если умрет А значит 1-я.
Если умрет В значит 3-я.
Если оба значит 2-я.
Если никто значит 4-я.

Павел.

... << RSDN@Home 1.1.4 beta 2 >>

Здравствуйте, <Аноним>, Вы писали:

А>Хорош жрать, мне оставьте

А отравиться не боишся?

... << RSDN@Home 1.1.4 beta 2 >>

Здравствуйте, folk, Вы писали:

F>Представим номера бочек в двоичном виде (0 = дегустатор N не отпивает, 1 = дегустатор N отпивает), для этого понадобиться 10 разрядов-дегустаторов (2^10 = 1024). Чтобы при этом минимизировать кол-во выпитого вина можно похитрить с кодировкой, но экономия будет копеечная.

Так как есть небольшой запас до 1024, то при правильной кодировке выживут не меньше 2-х из 10 слуг, так что будет кому разносить...

пиво

Здравствуйте, 0rc, Вы писали:

10 слуг, все правильно

... << RSDN@Home 1.1.4 beta 3 rev. 185>>

Здравствуйте, HeaveN, Вы писали:

HN>Задачка такая пробежала...

HN>

Вы, правитель империи, решили устроить пир, который состоится ровно через один месяц. Чтобы обеспечить застолье должным количеством вина, вами было приказано от каждой провинции доставить к императорскому двору по одной бочке с вином. В империи 1000 провинций... — 1000 бочек уже стоят в вашем погребе, все прекрасно. Но ваши разведчики внезапно долкладывают вам о том, что в одной из бочек вино отравлено, естесственно неизвестно в какой. Яд действует медленно и коварно — один месяц, и после этого выпивший хотя бы один стакан вина умирает. Нужно точно определить к началу пира в какой бочке яд и не допустить вымирания правящей династии.
HN>Есть 2 постановки вопроса для решения:

HN>1. Какое минимальное число слуг можно задействовать и как?

HN>2. Какое минимальное количество вина можно израсходовать и как?

Вот в условиях не сказанно про силу яда, а допустим он был такой силы, что вино из отравленной бочки можно разбавить в 500 раз и оно останется смертельным. Тогда наворачивается следующие решение :
Возьмем по ложке вина из 500 бочек и нальем в стакан. Слуга выпивает. Умирет — отравленное вино в 1й из этих 500 бочек, иначе в оставшихся, продолжаем рекурсивно. В итоге если слугам хронически не везло, то их умрет 10, однако вероятность этого ничтожно мала = 0.5^10, самое вероятное число откинувшихся слуг можно посчитать найдя максимум ф-лы Бернулли, лень считать...

Здравствуйте, HeaveN, Вы писали:

HN>Задачка такая пробежала...

HN>

Вы, правитель империи, решили устроить пир, который состоится ровно через один месяц. Чтобы обеспечить застолье должным количеством вина, вами было приказано от каждой провинции доставить к императорскому двору по одной бочке с вином. В империи 1000 провинций... — 1000 бочек уже стоят в вашем погребе, все прекрасно. Но ваши разведчики внезапно долкладывают вам о том, что в одной из бочек вино отравлено, естесственно неизвестно в какой. Яд действует медленно и коварно — один месяц, и после этого выпивший хотя бы один стакан вина умирает. Нужно точно определить к началу пира в какой бочке яд и не допустить вымирания правящей династии.
HN>Есть 2 постановки вопроса для решения:

HN>1. Какое минимальное число слуг можно задействовать и как?

HN>2. Какое минимальное количество вина можно израсходовать и как?

Решение намного проще чем вы думаете.
Количество слуг, которое должно помереть — 0
минимальное кол-во вина для проверки на смерть — 0

Если для того, чтоб сдохнуть нужно выпить стакан, то просто делаем смесь по ПОЛСТАКАНА из каждой бочки.
Полученная смесь будет не смертельной и ее хватит, чтоб упиться всем в зюзю.

Ну и количество таких смесей будет зависить от размера стакана и бочки. При грамотном делении хватит всем

Здравствуйте, sadomovalex, Вы писали:

S>Здравствуйте, HeaveN, Вы писали:

HN>>Задачка такая пробежала...

HN>>[q]Вы, правитель империи, решили устроить пир, который состоится ровно через один месяц. Чтобы обеспечить застолье должным количеством вина, вами было приказано от каждой провинции доставить к императорскому двору по одной бочке с вином. В империи 1000 провинций... — 1000 бочек уже стоят в вашем погребе, все прекрасно. Но ваши разведчики внезапно долкладывают вам о том, что в одной из бочек вино отравлено, естесственно неизвестно в какой. Яд действует медленно и коварно — один месяц, и после этого выпивший хотя бы один стакан вина умирает. Нужно точно определить к началу пира в какой бочке яд и не допустить вымирания правящей династии.
HN>>Есть 2 постановки вопроса для решения:

HN>>1. Какое минимальное число слуг можно задействовать и как?

Можно рассмотреть более общий случай — нумеруем бочки, каждой из них ставим в соответствие 10-и мерный вектор (a1, a2, ..., a10) — двоичное представление порядкового номера. Берем 20 слуг. Каждый слуга фиксирует одну координату вектора: первый — (0, a2,...,a10) и пробует все оставшиеся 2^9=512 бочек с нулевой первой координатой; второй: (1, a2,...,a10); третий: (a1, 0,...,a10), и т.д. При этом умрут 10 человек, на пересечении которых и будет отравленная бочка

Здравствуйте, folk, Вы писали:

HN>>>1. Какое минимальное число слуг можно задействовать и как?

T>>Вариант решения: напоить два комплекта по 10 слуг и считать бит взведенным, только если слуга умер в обеих комплектах.
T>>Вопрос: можно ли уменьшить количество задействованных слуг для определения отравленной бочки при условии возможности не более одной случайной сметри?

F>С помощью тупого перебора с проверкой этих условий получаем 1051 полезную комбинацию для 14 бит, этого вполне достаточно.
Осталось доказать, что для 13ти нельзя найти 1000 комбинаций (ну или найти эти комбинации).

F>Вряд ли это наилучшее решение, но если мне не изменяет склероз, это не хуже кода Хемминга, в котором 4 полезных бита дополнялись еще 3 избыточными.
Врят ли наилучшее. Задача свялась к нахождению максимальной покраски графа(NP — полная задача, но у нас гарф специфический... может и полиномиально решается). Может попробовать уже готовые переборные решения?

Здравствуйте, folk, Вы писали:

F>Вряд ли это наилучшее решение, но если мне не изменяет склероз, это не хуже кода Хемминга, в котором 4 полезных бита дополнялись еще 3 избыточными.

Код Хемминга требует дописывания ceil(log2(n)) бит. В итоге он тоже дает 14 слуг.

Другое дело, что у нас есть некоторая изначальная избыточность по слугам (1000 < 2^10) и ошибка 1->0 невозможна.
Т.ч. может действительно стоит поискать более короткие коды.

если предположить что все вино по качеству
одинаковое и не пострадает при смешивании,
либо организаторам пьянки пофигу, потеряет ли
оно качество, то выход такой :

смешать содержимое всех бочек,
тогда смертельная доза — 1000 стаканов,
вряд ли кто-то столько выпьет

Здравствуйте, folk, Вы писали:

F>Здравствуйте, Tan4ik, Вы писали:

F>Для упрощения предположим что возможна одиночная ошибка не только 0->1, но и 1->0. Тогда одна "полезная" комбинация сделает недопустимыми для использования еще n "страховочных" комбинаций, где n — количество бит. В самом деле, код 1100 запрещает к использованию коды 1000, 0100, 1110, 1101. Получаем формулу 2^n = 1000*(n+1), где 1000 — кол-во полезных комбинаций (бочек). Подбираем ближайшее сверху целое — 14.

F>Это конечно неточная оценка, во-1х неясно, возможно ли настолько плотно упаковать коды, чтобы на каждую полезную комбинацию приходилось ровно 14 страховочных. Так что реально количество полезных комбинаций может быть меньше. Но с другой стороны по условию нашей задачи ошибка 1->0 невозможна (выпивший отравы не может выжить), так что количество полезных кодов может быть больше. Поскольку ничего лучше придумать не могу, то пусть будет 14 слуг.

F>Теперь попробуем подобрать коды.
F>Обозначим кол-во единичек в коде X как 1(X). Код X достижим из кода Y, если X может быть получен из Y установкой одного 0 в 1. Ясно что 1(X xor Y) == 1.
F>Еще следует опасаться ситуаций, когда из X и Y достижим один и тот же код Z. Ясно что 1(X) == 1(Y) и 1(X xor Y) == 2.

Невозможность ошибки 1->0 ничего нового не дает, т.к. легко разобраться, что в обоих "критических" случаях, приведенных folk-ом, всегда существует "парный" переход 0->1 (или в другом направлении, или к другому, но общему, числу).

Т.ч. 14 слуг, похоже, можно считать доказанным.

Но тут возникает интересная обратная задача:

Сколько максимум бочек вина можно проверить с 14-ю слугами, если считать, что один из них может умереть во время эксперимента по естественным причинам?

Используя формулу folk-а можно получить, что с 14-ю слугами можно проверить не больше 1092 бочки вина.
Мой рекорд пока — 1062.

Здравствуйте, MichaelP, Вы писали:

F>>Для упрощения предположим что возможна одиночная ошибка не только 0->1, но и 1->0. Тогда одна "полезная" комбинация сделает недопустимыми для использования еще n "страховочных" комбинаций, где n — количество бит. В самом деле, код 1100 запрещает к использованию коды 1000, 0100, 1110, 1101. Получаем формулу 2^n = 1000*(n+1), где 1000 — кол-во полезных комбинаций (бочек). Подбираем ближайшее сверху целое — 14.

F>>Это конечно неточная оценка, во-1х неясно, возможно ли настолько плотно упаковать коды, чтобы на каждую полезную комбинацию приходилось ровно 14 страховочных. Так что реально количество полезных комбинаций может быть меньше. Но с другой стороны по условию нашей задачи ошибка 1->0 невозможна (выпивший отравы не может выжить), так что количество полезных кодов может быть больше. Поскольку ничего лучше придумать не могу, то пусть будет 14 слуг.

F>>Теперь попробуем подобрать коды.
F>>Обозначим кол-во единичек в коде X как 1(X). Код X достижим из кода Y, если X может быть получен из Y установкой одного 0 в 1. Ясно что 1(X xor Y) == 1.
F>>Еще следует опасаться ситуаций, когда из X и Y достижим один и тот же код Z. Ясно что 1(X) == 1(Y) и 1(X xor Y) == 2.

MP>Невозможность ошибки 1->0 ничего нового не дает, т.к. легко разобраться, что в обоих "критических" случаях, приведенных folk-ом, всегда существует "парный" переход 0->1 (или в другом направлении, или к другому, но общему, числу).

MP>Т.ч. 14 слуг, похоже, можно считать доказанным.

В этом рассуждении есть ошибка. Проведем опыт — будем считать для n бит макс. кол-во полезных комбинаций по формуле и параллельно запускать мою программку перебора.

n  2^n/(n+1) перебор
2  1       < 2    
3  2       = 2    
4  3       < 4    
5  5       < 6        
6  9       < 12    
7  16      = 16
8  28      = 28
9  51      > 48
10 93      > 91
11 170     > 165
12 315     > 309
13 585     > 566
14 1092    > 1051
15 2048    > 1900
16 3855    > 3498

На большой разрядности перебор сдает потому что там меньше вероятность попасть в наилучшую раскладку методом тыка. А для малой разрядности получаем прецеденты более экономного кода.

Разберем простейший случай с 2 битами.
Если возможны ошибки 0->1 и 1->0 то для двух битов уже недопустимы одновременно коды 00 и 11, т.к. из них обоих достижимы комбинации 01 и 10.
А если ошибка 1->0 невозможна, то коды 00 и 11 одновременно допустимы, т.к. из 11 недостижимы коды 01 и 10.

Так что невозможность закодировать 13 слугами еще не доказана.

MP>Но тут возникает интересная обратная задача:

MP>Сколько максимум бочек вина можно проверить с 14-ю слугами, если считать, что один из них может умереть во время эксперимента по естественным причинам?

MP>Используя формулу folk-а можно получить, что с 14-ю слугами можно проверить не больше 1092 бочки вина.
MP>Мой рекорд пока — 1062.

Опять же получается что возможно более 1092 комбинаций.

Здравствуйте, 0rc, Вы писали:

0rc> Нестандартное решение:
0rc> Свести задачу к минимизации яда. Т.е. для отравления одного человека необходимо и достаточно 1 стакан. Следовательно, необходимо смешать между собой бочки и смесь снова разлить.
Точнее надо слить из всех бочек по 1 стакану, а все остальное перемешать. Тогда если ни один гость не будет пить больше 1 бочки

, то никто не отравится.

Здравствуйте, pivoo, Вы писали:

P>если предположить что все вино по качеству
P>одинаковое и не пострадает при смешивании,
P>либо организаторам пьянки пофигу, потеряет ли
P>оно качество, то выход такой :

P>смешать содержимое всех бочек,
P>тогда смертельная доза — 1000 стаканов,
P>вряд ли кто-то столько выпьет

нет, ну тут нужна гарантия))
а вдруг у правящей династии слабое здоровье и им полстакана хватит.

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

всего 2 шага
1) выяснить сколько бочек вина могут влить в себя царственные алкоголики — например N.
2) взять N бочек и N слуг — и пусть каждый выпьет из своей бочки.
3) ежели через месяц не помрут, то пусть венценосные смело надираются из опробованных бочек, нет — пусть берут другую партию. Отравленная бочка точно им не достанется. А на гостей точно можно наплевать — одно разорение, пущай их

	От:	MasterSav
	Дата:	15.09.04 07:19
	Оценка:	38 (6) +1

	От:	Аноним
	Дата:	15.09.04 09:23
	Оценка:	32 (5)

	От:	HeaveN
	Дата:	14.09.04 23:28
	Оценка:	20 (4)

	От:	folk
	Дата:	15.09.04 00:43
	Оценка:	17 (4)

	От:	Аноним
	Дата:	15.09.04 10:10
	Оценка:

	От:	Pavel Dvorkin
	Дата:	15.09.04 07:37
	Оценка:	5 (1)

	От:	Gandalf_The_Grey
	Дата:	22.09.04 20:51
	Оценка:

От:	sergey_shandar	http://getboost.codeplex.com/
Дата:	15.09.04 00:12
Оценка:

	От:	Блудов Павел
	Дата:	15.09.04 09:45
	Оценка:

От:	sadomovalex	http://sadomovalex.blogspot.com
Дата:	15.09.04 10:26
Оценка:

	От:	0rc
	Дата:	16.09.04 12:26
	Оценка:	21 (2)

	От:	sba
	Дата:	19.09.04 22:22
	Оценка:	+1

	От:	conraddk
	Дата:	21.09.04 08:35
	Оценка:

	От:	0rc
	Дата:	17.09.04 06:28
	Оценка: