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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Итак, ответы

Да

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

1024 бутылок