Question

Прибор умеет определять, чётное или нечётное количество золотых монет находится на его чашке. Из 6 монет 4 - золотые. Можно ли с помощью 4 измерений этим прибором найти все золотые монеты?

Answer 1

Сперва поделим монеты на три кучки по две монеты в каждой. Первыми двумя вопросами проверяем чётность монет в каких-то двух кучках. Чётность монет в третей кучке устанавливается автоматически. Вариантов результата лишь два:

"0-0-0": Узнаем чётность, взяв по монете из кучек 1 и 2, а потом взяв по монете из кучек 2 и 3. Если у обоих чётность 1, то в 1-ой и 3-ей кучках золотые монеты. Если у одной чётность 0, то в кучках, откуда брали монеты, монеты золотые.

"0-1-1": В кучке 0 точно золотые монеты, узнаем чётность одной из монет из другой кучки, если 1 - золотая, если 0 - золотая оставшаяся монета в кучке (2 раза для двух кучек).

Ответ: можно.

Answer 2

Да, с помощью 4 измерений этим прибором можно определить все золотые монеты. Возможностей определения состояний четности и нечетности у нас всего две, так как прибору доступны два варианта ответа: "четное" или "нечетное".

Рассмотрим различные сценарии для 4 измерений:

1. Мы можем разделить 6 монет на две группы по 3 монеты каждая и измерить четность/нечетность монет в каждой группе. Это даст нам два измерения. Например, результаты измерения могут быть такими: Группа 1: Нечетное количество золотых монет Группа 2: Четное количество золотых монет

2. Теперь возьмем каждую группу с нечетным количеством золотых монет (в данном случае это Группа 1) и разделим ее на две подгруппы по 2 монеты в каждой. Измерим четность/нечетность монет в каждой из этих подгрупп. Это даст нам еще два измерения. Например: Подгруппа 1: Нечетное количество золотых монет Подгруппа 2: Четное количество золотых монет

Теперь у нас есть 4 измерения:

1. Группа 1: Нечетное количество золотых монет
2. Группа 2: Четное количество золотых монет
3. Подгруппа 1: Нечетное количество золотых монет
4. Подгруппа 2: Четное количество золотых монет

Теперь мы можем объединить информацию из всех измерений:

• В Группе 1 есть нечетное количество золотых монет, что означает, что в ней может быть либо 1 золотая монета, либо 3 золотых монеты.
• В Группе 2 есть четное количество золотых монет, значит, в ней либо 0, либо 2 золотых монеты.

Для каждой из возможных комбинаций значений в обеих группах, у нас остаются две подгруппы. Исходя из измерений в подгруппах, мы можем определить количество золотых монет в каждой из них.

Таким образом, с помощью 4 измерений этим прибором можно однозначно определить количество золотых монет среди 6 монет.