Question

имеется 100 образцов, среди которых ровно 2 радиоктивны. Есть прибор, в которых можно положить не более 10 образцов и прибор покажет, есть ли среди них радиоктивные. Как составить список из 20 проверок, проведя которые и проанализировав полученные результаты, можно указать не более четырех образцов, среди которых будут оба радиоктивных? Менять список проверок в зависимости от получаемых результатов нельзя

Answer 1

Пронумеруем все образцы номерами от 1 до 100. В первых десяти проверках будут участвовать образцы 1-10, 11-20 ... 91-100. Во вторых 10 проверках будут участвовать группы образцов: (1, 11, ... 91), (2, 12, ... 92) и т.д.

Докажем, что такими проверками можно указать не более 4 образцов так, что среди них будут оба радиоактивных. Поймем, что каждый образец проверяется по два раза. Они пронумерованы таким образом, что 1 цифра обозначает номер первого испытания, вторая цифра обозначает номер второго испытания. Пусть на первом испытании "засветились" образцы с 1 цифрой x и y, на втором испытании "засветились образцы" со второй цифрой a и b, тогда радиоактивными могут быть 2 из следующих образцов: xa, xb, ya, yb.

Answer 2

Для решения этой задачи можно использовать метод комбинаторики и бинарного кода. Давайте создадим список из 20 проверок, где каждая проверка представляет собой группу образцов, которые будут помещены в прибор. При этом мы учитываем, что каждая группа должна содержать не более 10 образцов.

Шаг 1: Создание списка проверок Мы будем использовать бинарное кодирование для создания всех возможных комбинаций. Представим образцы в виде двоичных чисел от 1 до 100 (например, первый образец - 0000000001, второй - 0000000010 и т.д.). Затем создадим список проверок, используя бинарные числа с шестью битами (от 000000 до 111111), чтобы получить все возможные комбинации из 6 образцов.

1. 000000 (Образцы: 1, 2, 3, 4, 5, 6)
2. 000001 (Образцы: 1, 2, 3, 4, 5, 7)
3. 000010 (Образцы: 1, 2, 3, 4, 5, 8) ...
4. 111110 (Образцы: 95, 96, 97, 98, 99, 100)
5. 111111 (Образцы: 1, 2, 3, 4, 5, 6, 95, 96, 97, 98, 99, 100)

Шаг 2: Анализ результатов Теперь проведем все 20 проверок и запишем результаты. По результатам проверок мы можем определить следующее:

• Если в проверке есть хотя бы один образец, который был включен в каждую из 10 проверок, в которых были обнаружены радиоактивные образцы, то этот образец является радиоактивным. Для этого нам нужно отметить образцы, которые присутствуют в проверках 1, 2, 3, ..., 10.

Например, если после проведения всех 20 проверок мы выяснили, что образцы 3, 5, 8 и 10 присутствуют в каждой из первых 10 проверок, где были обнаружены радиоактивные образцы, то это означает, что образцы 3, 5, 8 и 10 являются радиоактивными, и два радиоактивных образца уже идентифицированы.

• Если у нас есть образцы, которые присутствуют в проверках с 11 по 20 и в каждой из них были обнаружены радиоактивные образцы, то это также могут быть радиоактивные образцы.

Продолжаем анализ до тех пор, пока не определим оба радиоактивных образца.