Вино и кролики

[Legioner93]

По интернету несколько лет гуляет одна забавная задачка. Утверждается, что с собеседования в Яндекс.

Цитата:

У короля есть 1000 бутылок вина одного сорта. Король из соседнего королевства решает убить нашего короля и отправляет убийцу, чтобы отравить один из бутлок с вином. Убийца успел добавить яд в одну из бутылок, но был пойман стражей. Король узнал об этом, решил проверить, какая бутылка был отравлена. Наш король очень умный и поэтому он решает использовать 10 кроликов, чтобы проверить, какая бутылка содержит яд. Из бутылок можно взять немного вина. От яда кролик умирает через 1 день.
Сколько минимально дней потребуется, чтобы определить бутылку с ядом?

Конечно, в такой формулировке она довольно простая, начните с неё как с разминки. Хотя, на других площадках и оригинальная формулировка вызывает довольно бурное обсуждение

Я же предлагаю обобщить на произвольное число кроликов и бутылок:

Цитата:

У короля есть X бутылок вина одного сорта. Король из соседнего королевства решает убить нашего короля и отправляет убийцу, чтобы отравить один из бутлок с вином. Убийца успел добавить яд в одну из бутылок, но был пойман стражей. Король узнал об этом, решил проверить, какая бутылка был отравлена. Наш король очень умный и поэтому он решает использовать Y кроликов, чтобы проверить, какая бутылка содержит яд. Из бутылок можно взять немного вина. От яда кролик умирает через 1 день.
Сколько минимально дней потребуется, чтобы определить бутылку с ядом?

Сложность задачи существенно возрастает. Тем не менее, и такая формулировка подъёмна. Пробуйте!

(Мой ответ (с защитой от случайного открытия спойлера))

00000000: 6365 696c 2858 5e28 312f 5929 2d31 290a

[EUgeneUS]

Legioner93

1. Ответ на оригинальную задачу - за 1 день. Не понимаю, что там может вызвать споры.
2. Если кроликов достаточно, чтобы вообще определить ядовитую бутылку, то определить за 1 день будет можно.

[wrest]

EUgeneUS в сообщении #1235104 писал(а):

Если кроликов достаточно, чтобы вообще определить ядовитую бутылку

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

EUgeneUS в сообщении #1235104 писал(а):

Ответ на оригинальную задачу - за 1 день. Не понимаю, что там может вызвать споры.

А давайте я загадаю номер бутылки от 1 до 1000, пронумеруем кроликов от 1 до 10, вы скажете каким кроликам налить из каких бутылок, я скажу вам какие кролики сдохли, а вы за один раз угадаете номер бутылки :)

[Sender]

wrest в сообщении #1235112 писал(а):

А давайте я загадаю номер бутылки от 1 до 1000, пронумеруем кроликов от 1 до 10, вы скажете каким кроликам налить из каких бутылок, я скажу вам какие кролики сдохли, а вы за один раз угадаете номер бутылки :)

Кстати, не самый удачный контрпример, ибо $2^{10}>1000.$

[Legioner93]

EUgeneUS в сообщении #1235104 писал(а):

2. Если кроликов достаточно, чтобы вообще определить ядовитую бутылку, то определить за 1 день будет можно.

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

[EUgeneUS]

Legioner93
wrest
Да, с общим случаем у меня случилось затмение

-- 21.07.2017, 14:24 --

Минимальное количество дней - минимальное целое решение неравенства:

$N\leqslant (d+1)^k$

$N$ - количество бутылок
$k$ - количество доступных кроликов
$d$ - количество требуемых дней.

-- 21.07.2017, 14:38 --

wrest в сообщении #1235112 писал(а):

А давайте я загадаю номер бутылки от 1 до 1000, пронумеруем кроликов от 1 до 10, вы скажете каким кроликам налить из каких бутылок, я скажу вам какие кролики сдохли, а вы за один раз угадаете номер бутылки :)

Из каждой бутылки наливайте тем кроликам, у которых в номере бутылки бит, который соответствует номеру кролика, не нулевой. Сдохшие кролики сами скажут номер бутылки.

[SomePupil]

Разделяем $1000$ бутылок на $10$ групп по $100$. Поим каждого кролика из бутылок одной группы. После первого дня мы поймем, в какой группе бутылка с ядом.

Итак, на второй день у нас останется $100$ "подозреваемых" бутылок. Разделяем их на $9$ групп $100 = 11 \times 8 + 12$ и поступаем аналогично предыдущему. В худшем случае останемся с $12$ подозрительными бутылками.

После третьей итерации останемся с $2$ бутылками.

После четвертого дня определим бутылку с ядом.

[wrest]

Sender в сообщении #1235117 писал(а):

Кстати, не самый удачный контрпример, ибо $2^{10}>1000.$

Мне тоже пришла в голову формула $\dfrac{X}{2^Y-1}$ с округлением до большего целого, и для 1000 бутылок и 10 кроликов вроде как 1 день, но когда я начал писать конкретно для 4 бутылок и 2 кроликов, то чего-то не сложилось.

-- 21.07.2017, 15:00 --

EUgeneUS в сообщении #1235124 писал(а):

Из каждой бутылки наливайте тем кроликам, у которых в номере бутылки бит, который соответствует номеру кролика, не нулевой. Сдохшие кролики сами скажут номер бутылки.

Да, спасибо что сформулировали, а то я сам не смог. Вопрос снимаю.

[12d3]

Ну и для полноты картины доказательство.
1) Докажем сначала, что из $(d+1)^k$ бутылок за $d$ дней $k$ кроликов выяснят, какая же бутылка отравленная. Занумеруем бутылки в $(d+1)$-ичной системе счисления, начиная с нуля. Пусть $i$-ый ($0\le i < k$) кролик в $j$-ый ($1 \le j \le d$) день пьет из тех бутылок, в номерах которых в $i$-м разряде стоит $j$. Если $i$-ый кролик помирает в $j$-ый день, значит, в $i$-м разряде стоит $j$, а если не помирает вообще, то там стоит 0. Если кролик помер, дальше мы его использовать не можем, да и не нужно, раз мы соответствующий ему разряд узнали. Таким образом за $d$ дней узнаем все разряды номера бутылки.
2) Докажем, что из $(d+1)^k + 1$ бутылок за $d$ дней $k$ кроликов не могут выяснить, какая бутылка отравленная, по индукции по $d$. База $d=0$: дву бутылки и 0 дней. Очевидно, определить нельзя. Переход от $d-1$ к $d$. Пусть у нас $(d+1)^k+1$ бутылка и $k$ кроликов. Нарисуем на каждой бутылке число в двоичной системе счисления, в котором в $i$-ом разряде стоит 0, если $i$-ый кролик пьет из этой бутылки, иначе 1. Обозначим количество бутылок, на которых написано число $M$ через $f(M)$, а количество единичек в числе $M$ через $g(M)$. Если предположить, что для каждого $M$ $f(M) \le d^{g(M)}$, то $(d+1)^k + 1 = \sum\limits_{M=0}^{2^k-1}f(M) \le \sum\limits_{M=0}^{2^k-1} d^{g(M)} = \sum\limits_{l=0}^{k}C_k^ld^l = (d+1)^k$. Противоречие. Значит, существует такое число $M$, что количество бутылок с этим числом больше, чем $d^{g(M)}$. В худшем случае, отравленная бутылка окажется среди этих, и тогда у нас останется $d-1$ день, $g(M)$ живых кроликов и не менее $d^{g(M)} + 1$ бутылок, а по предположению индукции, столько дней не хватит для определения отравленной бутылки. Конец доказательства.

[Legioner93]

EUgeneUS
12d3
Всё правильно!

[EUgeneUS]

12d3 в сообщении #1235141 писал(а):

2) Докажем, что из $(d+1)^k + 1$ бутылок за $d$ дней $k$ кроликов не могут выяснить, какая бутылка отравленная, по индукции по $d$.

Зачем по индукции? Это автоматом получается по построению. У кролика есть $d+1$ состояний (сдох в один из дней или выжил). Есть k различных кроликов. Всего возможных различных состояний $(d+1)^k$, не больше.

Еще усложним задачу.
А теперь у нас кролики сидят в одной клетке. Но есть серые и белые, самки и самцы.
То есть четыре группы ($m$ групп), количество кроликов в разных группах различаются не более чем на 1. Кролики в группе неразличимы.
Вопросы - те же.