Известно, что среди 18 шаров два радиоактивных. Можно проверять на радиоактивность кучку из любых шаров. Как за 8 таких проверок наверняка найти оба радиоактивных шара?
Решение этой головоломки основывается на двух простых соображениях:
1. Для того, чтобы среди 2n шаров найти один радиоактивный, достаточно n проверок. Например, чтобы среди 8 шаров обнаружить один радиоактивный, достаточно 3 проверок. Для этого надо действовать методом деления пополам (или дихотомии): исходное количество шаров разделить на 2 одинаковые кучки и проверить одну из них, затем найденную радиоактивную кучку (если проверяемая кучка не радиоактивная, то радиоактивной будет вторая) снова разделить на две равные кучки и проверить одну из них, и так далее. В конце кучка из двух шаров разделяется на две «кучки» из одного шара, и n-й проверкой находится радиоактивный шар.
2. В радиоактивной кучке из 6 шаров за 3 проверки можно найти радиоактивный шар и ещё как минимум для одного шара определить, радиоактивный он или нет. Для этого надо разделить эту кучку на две равные кучки из 3 шаров и проверить одну из них, а в той кучке, которая окажется радиоактивной, по очереди проверить два любых шара.
Объединив эти два соображения, можно получить следующий алгоритм решения:
1. Проверяем на радиоактивность кучку из 6 любых шаров.
2. Если эта кучка радиоактивна, то за 3 проверки мы можем обнаружить радиоактивный шар и ещё для одного шара определить, является ли он радиоактивным (соображение №2). Если этот шар не является радиоактивным, то возвращаем оставшиеся 4 шара к остальным 12 и среди получившихся 16 шаров за 4 оставшиеся проверки находим второй радиоактивный шар (соображение №1).
3. Если эта кучка из 6 шаров не радиоактивна, то разбиваем оставшиеся 12 шаров на 3 кучки по 4 шара и проверяем каждую из них. Если радиоактивной окажутся две кучки, то для каждой из них достаточно двух проверок для нахождения радиоактивного шара. Если радиоактивной окажется одна кучка, то по очереди проверяем все её шары, пока не найдём два радиоактивных.
1. Для того, чтобы среди 2n шаров найти один радиоактивный, достаточно n проверок. Например, чтобы среди 8 шаров обнаружить один радиоактивный, достаточно 3 проверок. Для этого надо действовать методом деления пополам (или дихотомии): исходное количество шаров разделить на 2 одинаковые кучки и проверить одну из них, затем найденную радиоактивную кучку (если проверяемая кучка не радиоактивная, то радиоактивной будет вторая) снова разделить на две равные кучки и проверить одну из них, и так далее. В конце кучка из двух шаров разделяется на две «кучки» из одного шара, и n-й проверкой находится радиоактивный шар.
2. В радиоактивной кучке из 6 шаров за 3 проверки можно найти радиоактивный шар и ещё как минимум для одного шара определить, радиоактивный он или нет. Для этого надо разделить эту кучку на две равные кучки из 3 шаров и проверить одну из них, а в той кучке, которая окажется радиоактивной, по очереди проверить два любых шара.
Объединив эти два соображения, можно получить следующий алгоритм решения:
1. Проверяем на радиоактивность кучку из 6 любых шаров.
2. Если эта кучка радиоактивна, то за 3 проверки мы можем обнаружить радиоактивный шар и ещё для одного шара определить, является ли он радиоактивным (соображение №2). Если этот шар не является радиоактивным, то возвращаем оставшиеся 4 шара к остальным 12 и среди получившихся 16 шаров за 4 оставшиеся проверки находим второй радиоактивный шар (соображение №1).
3. Если эта кучка из 6 шаров не радиоактивна, то разбиваем оставшиеся 12 шаров на 3 кучки по 4 шара и проверяем каждую из них. Если радиоактивной окажутся две кучки, то для каждой из них достаточно двух проверок для нахождения радиоактивного шара. Если радиоактивной окажется одна кучка, то по очереди проверяем все её шары, пока не найдём два радиоактивных.