Question

На столе лежит 220 внешне одинаковых монет. Известно, что среди них ровно 110 фальшивых. Разрешается указать на любые две монеты и спросить, верно ли, что обе эти монеты фальшивые. За какое наименьшее количество вопросов можно гарантированно получить по крайней мере один ответ «Верно»?

Answer 1

Рассмотрим самый грустный вариант:
Мы постоянно указываем на 1 настоящую монету и на 1 фальшивую, всего мы зададим 110 вопросов.
Тогда у нас получится
Ф + Н
Ф + Н
Не зная, какая из них фальшивая, мы снова наткнемся на случай
Ф1 + Н1
Ф2 + Н2
Потом мы укажем снова на 2 настоящие,
Н+Н
А потом на 2 фальшивые
Ф+Ф
Тогда ответ: 110 + 4 = 114

Answer 2

Задача о фальшивых монетах

Дано: на столе лежит 220 внешне одинаковых монет, среди которых ровно 110 фальшивых. Разрешается указать на любые две монеты и спросить, верно ли, что обе эти монеты фальшивые. Необходимо определить, за какое наименьшее количество вопросов можно гарантированно получить по крайней мере один ответ "Верно".

Решение:

Для решения этой задачи можно использовать стратегию деления монет на группы.

1. Разделим все монеты на две равные группы по 110 монет в каждой. 2. Возьмем любые две монеты из одной из групп и спросим, верно ли, что обе эти монеты фальшивые. - Если ответ "Да", то обе эти монеты являются фальшивыми, и мы получили ответ "Верно" за 1 вопрос. - Если ответ "Нет", то обе эти монеты не являются фальшивыми. Теперь у нас осталось 108 фальшивых монет и 110 настоящих монет. 3. Разделим оставшиеся монеты на две равные группы по 54 монеты в каждой. 4. Возьмем любые две монеты из одной из групп и спросим, верно ли, что обе эти монеты фальшивые. - Если ответ "Да", то обе эти монеты являются фальшивыми, и мы получили ответ "Верно" за 2 вопроса. - Если ответ "Нет", то обе эти монеты не являются фальшивыми. Теперь у нас осталось 54 фальшивых монеты и 54 настоящих монеты. 5. Разделим оставшиеся монеты на две равные группы по 27 монет в каждой. 6. Возьмем любые две монеты из одной из групп и спросим, верно ли, что обе эти монеты фальшивые. - Если ответ "Да", то обе эти монеты являются фальшивыми, и мы получили ответ "Верно" за 3 вопроса. - Если ответ "Нет", то обе эти монеты не являются фальшивыми. Теперь у нас осталось 27 фальшивых монет и 27 настоящих монет. 7. Разделим оставшиеся монеты на две равные группы по 13 монет в каждой. 8. Возьмем любые две монеты из одной из групп и спросим, верно ли, что обе эти монеты фальшивые. - Если ответ "Да", то обе эти монеты являются фальшивыми, и мы получили ответ "Верно" за 4 вопроса. - Если ответ "Нет", то обе эти монеты не являются фальшивыми. Теперь у нас осталось 13 фальшивых монет и 13 настоящих монет. 9. Разделим оставшиеся монеты на две равные группы по 6 монет в каждой. 10. Возьмем любые две монеты из одной из групп и спросим, верно ли, что обе эти монеты фальшивые. - Если ответ "Да", то обе эти монеты являются фальшивыми, и мы получили ответ "Верно" за 5 вопросов. - Если ответ "Нет", то обе эти монеты не являются фальшивыми. Теперь у нас осталось 6 фальшивых монет и 6 настоящих монет. 11. Разделим оставшиеся монеты на две равные группы по 3 монеты в каждой. 12. Возьмем любые две монеты из одной из групп и спросим, верно ли, что обе эти монеты фальшивые. - Если ответ "Да", то обе эти монеты являются фальшивыми, и мы получили ответ "Верно" за 6 вопросов. - Если ответ "Нет", то обе эти монеты не являются фальшивыми. Теперь у нас осталось 3 фальшивых монеты и 3 настоящих монеты. 13. Разделим оставшиеся монеты на две равные группы по 1 монете в каждой. 14. Возьмем любые две монеты из одной из групп и спросим, верно ли, что обе эти монеты фальшивые. - Если ответ "Да", то обе эти монеты являются фальшивыми, и мы получили ответ "Верно" за 7 вопросов. - Если ответ "Нет", то обе эти монеты не являются фальшивыми. Теперь у нас осталось 1 фальшивая монета и 1 настоящая монета. 15. Возьмем оставшиеся две монеты и спросим, верно ли, что обе эти монеты фальшивые. - Если ответ "Да", то обе эти монеты являются фальшивыми, и мы получили ответ "Верно" за 8 вопросов. - Если ответ "Нет", то обе эти монеты не являются фальшивыми, и мы получили ответ "Верно" за 8 вопросов.

Таким образом, за наименьшее количество вопросов можно гарантированно получить по крайней мере один ответ "Верно" за 8 вопросов.