Задача про «Новичок»
В трюме матросы находят 10 мышей, которых они решают использовать для проверки бутылок.
На корабле находится 1000 бутылок с питьевой водой. После отплытия корабля террористы сообщают на борт о том, что одна бутылка с водой отравлена боевым ядом «Новичок».
Хватит ли им 10 мышей, чтобы среди 1000 бутылок определить ту, которая отравлена?
Какое максимальное количество бутылок можно проверить, используя 10 мышей?
Допустим, у нас есть всего 2 мыши и 4 бутылки, среди которых одна отравлена.
Проверку можно организовать следующим образом:
из 1-й бутылки не пьет ни одна мышь,
из 2-й бутылки пьет первая мышь,
из 3-й – вторая,
из 4-й – пьют обе.
из 1-й бутылки не пьет ни одна мышь,
из 2-й бутылки пьет первая мышь,
из 3-й – вторая,
из 4-й – пьют обе.
Соответственно, имеем 4 возможных состояния «системы»:
обе мыши живы – яд в бутылке 1, мертва первая мышь – яд в бутылке 2, мертва вторая мышь – яд в бутылке 3, мертвы обе мыши – яд в бутылке 4.
обе мыши живы – яд в бутылке 1, мертва первая мышь – яд в бутылке 2, мертва вторая мышь – яд в бутылке 3, мертвы обе мыши – яд в бутылке 4.
Тогда поим мышей по следующей схеме:
Немного усложним задачу: пускай теперь у нас 8 бутылок, среди которых одна отравлена, и 3 мыши
По тому, мыши из какого подмножества оказались мертвы, однозначно определяем бутылку с ядом.
В общем случае n мышей надо разбивать на подмножества (которых, как мы помним, всегда 2ⁿ штук) и поить водой из i-ой бутылки тех мышей, которые находятся в i-ом подмножестве.
В предыдущем варианте с тремя мышами A, B и C реализовалась следующая схема:
Но вообще, способов, которыми можно установить
взаимно-однозначное соответствие между бутылками с водой и подмножествами мышей, существует n!
взаимно-однозначное соответствие между бутылками с водой и подмножествами мышей, существует n!
Итак, десяти мышей хватает, чтобы отыскать отравленную бутылку среди 2¹⁰ = 1024 бутылок.
Читается n факториал. Равен произведению всех натуральных чисел от 1 до n, т. е. n! = 1 ∙ 2 ∙ 3 ∙ ... ∙ n
Чем больше в категории возможно операций, тем богаче и просторнее для мысли оказывается тот универсум, который формализует данная категория.
Хватит ли им 10 мышей, чтобы среди 1000 бутылок определить ту, которая отравлена?
Какое максимальное количество бутылок можно проверить, используя 10 мышей?
Да
1024 бутылок
Итак, ответы
