Question

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

Answer 1

Ответ:

105

Пошаговое объяснение:

Мы имеем 104 фальшивые монеты и 103 настоящие.

Разбиваем их на 103 пары, и остаётся 1 монета.

Задаём вопрос про каждую из 103 пар.

Если хоть одна пара имеет 2 фальшивых, то нам хватит 103 вопросов в самом крайнем случае.

Если в каждой паре 1 монета фальш. и 1 наст, то мы получим 103 НЕТ.

Тогда отложенная 1 монета - гарантированно фальшивая.

Проверяем отложенную и 1 монету из любой пары.

Если мы из пары взяли фальш, то получим ответ ДА.

В этом случае нам хватило 104 вопроса.

И наконец, если мы из пары взяли НАСТ. монету, то получим 104-ый ответ НЕТ.

Тогда вторая монета из пары и отложенная - две фальш, и мы получаем ДА.

В этом случае нам хватило 105 вопросов.

Если мы разобьём 207 монет на 69 троек, то получится хуже.

Потому что в каждой тройке придётся спрашивать как минимум по 2 раза, всего 69*2=138 вопросов.