На столе лежит 160 внешне одинаковых монет. известно, что среди них ровно 80 фальшивых. разрешается указать на любые две монеты и спросить, верно ли, что обе эти монеты фальшивые. за какое наименьшее количество вопросов можно гарантированно получить по крайней мере один ответ «верно»?
Т.к. нужно получить гарантированный ответ "Верно", то будем рассматривать наихудший сценарий, когда во всех 80 парах оказалось по одной фальшивой и настоящей монете. Если вдруг на каком-то этапе в паре окажутся две настоящие монеты, то, по крайней мере, на последний 80-й вопрос мы получим ответ "Верно". Поэтому 80-й вопрос задавать всё равно придётся. Если, как мы предположили, фальшивые с настоящими монетами разбились на пары, то и на 80-й вопрос получим ответ "Неверно".
Далее берём две пары монет, в которых мы уже знаем, что там по фальшивой и настоящей монете. Отмечаем ещё раз, что проверка в парах уже была. Пусть первая пара содержит монеты №1 (фальшивая) и №2 (настоящая), а вторая пара - монеты №3 (фальшивая) и №4 (настоящая).
Берём из первой пары монету №1, а из второй пары монету №3. Оказались обе фальшивые, ответ "Верно". Более плохой вариант, если сначала из второй группы выбрали монету №4, тогда бы пришлось задавать ещё один вопрос о монетах №1 и №3. Итак, этот вариант даёт 2 дополнительных вопроса.
Ситуация хуже, а именно её мы ищем, если бы из первой пары мы выбрали монету № 2 (настоящая), то с обоими монетами из второй группы получим ответ "Неверно". Истратили 2 вопроса. Наконец, проверяется монета № 1 и монеты №3 и № 4. Получилось бы ещё 2 дополнительных вопроса, если бы в последнюю очередь выбрали монету №3.
Всего получилось бы в самом наихудшем сценарии 84 вопроса.