Задача 10. Конверты с открытками

Хватит 39 операций

Занумеруем конверты от $1$ до $40$ и спросим про пары $(1; 2)$, $(1; 3)$, …, $(1; 40)$ — это $39$ операций.

Если все ответы «да», в конверте $1$ есть открытка: иначе ответы «да» означали бы, что открытки во всех $39$ остальных конвертах, а $39$ — нечётное число.

Если хотя бы один ответ «нет», конверт $1$ пуст. Тогда для каждой пары $(1; j)$ с ответом «да» открытка лежит в конверте $j$. Такая пара есть: открыток не меньше двух (их чётное число, и они есть), и каждая лежит в одном из конвертов $2, \ldots, 40$.

Меньше нельзя: ведущий всегда отвечает «да»

Пусть ведущий на любой вопрос отвечает «да» — это честно, например, если открытки во всех $40$ конвертах (их чётное число). Предположим, что после не более чем $38$ вопросов мы называем конверт $v$.

Конверт $v$ участвовал не более чем в $38$ вопросах, а других конвертов $39$ — значит, есть конверт $u$, про пару $(v; u)$ с которым мы не спрашивали. Положим открытки во все конверты, кроме $v$ и $u$: их $38$, чётное число. В каждой заданной паре есть конверт, отличный от $v$ и $u$ (единственная пара из них двоих не задавалась), поэтому все ответы «да» верны. Но конверт $v$ пуст — мы ошиблись.

Ответ

$39$ операций хватает, а меньшего числа может не хватить. Ответ: $39$. В общем виде для $n$ конвертов ($n$ чётно) ответ $n - 1$: названный конверт обязан побывать в паре с каждым из остальных.