В трюме матросы находят 10 мышей, которых они решают использовать для проверки бутылок.

На корабле находится 1000 бутылок с питьевой водой. После отплытия корабля террористы сообщают на борт о том, что одна бутылка с водой отравлена боевым ядом «Новичок».

Хватит ли им 10 мышей, чтобы среди 1000 бутылок определить ту, которая отравлена?

Какое максимальное количество бутылок можно проверить, используя 10 мышей?

Допустим, у нас есть всего 2 мыши и 4 бутылки, среди которых одна отравлена.

Проверку можно организовать следующим образом:

из 1-й бутылки не пьет ни одна мышь,
из 2-й бутылки пьет первая мышь,
из 3-й – вторая,
из 4-й – пьют обе.

Соответственно, имеем 4 возможных состояния «системы»:

обе мыши живы – яд в бутылке 1, мертва первая мышь – яд в бутылке 2, мертва вторая мышь – яд в бутылке 3, мертвы обе мыши – яд в бутылке 4.

Тогда поим мышей по следующей схеме:

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

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

В общем случае n мышей надо разбивать на подмножества (которых, как мы помним, всегда 2ⁿ штук) и поить водой из i-ой бутылки тех мышей, которые находятся в i-ом подмножестве.

В предыдущем варианте с тремя мышами A, B и C реализовалась следующая схема:

Но вообще, способов, которыми можно установить
взаимно-однозначное соответствие между бутылками с водой и подмножествами мышей, существует n!

Итак, десяти мышей хватает, чтобы отыскать отравленную бутылку среди 2¹⁰ = 1024 бутылок.

Хватит ли им 10 мышей, чтобы среди 1000 бутылок определить ту, которая отравлена?

Какое максимальное количество бутылок можно проверить, используя 10 мышей?

Да

1024 бутылок

Итак, ответы