Физтех 2025, отборочный этап, 11 класс, второй тур, задача 10
В некоторые из конвертов положили по одной открытке. Известно, что количество положенных открыток чётно. За одну операцию можно выбрать любые два конверта и узнать, есть ли в этих конвертах хотя бы одна открытка. За какое наименьшее количество таких операций можно гарантированно найти какой-нибудь конверт с открыткой?
Ответ
Ответ. .
Решение. Занумеруем конверты числами от до . Покажем, что за операций можно найти конверт с открыткой. Зададим вопросы про пары конвертов , , , . Если все ответы «да», то в первом конверте лежит открытка (иначе есть ещё хотя бы один пустой конверт, и один из ответов был бы «нет»). Если есть ответ «нет», то первый конверт пустой, и открытки будут лежать в тех конвертах, про которые ответили «да».
Покажем, что меньшего количества операций может не хватить. Предположим, что существует стратегия, позволяющая гарантированно найти конверт с открыткой за меньшее число операций. Будем всегда отвечать «да». Тогда максимум после операций можно будет указать на конверт с открыткой (будем считать, что это конверт ). Но тогда какого-то из вопросов вида задано не будет. Положим открытки во все конверты, кроме и . Тогда все ответы будут «да», но в конверте открытки не будет. Противоречие.