Задача 109810
|
|
 |
Условие
На столе стоят 2004 коробочки, в каждой из которых лежит по одному шарику. Известно, что некоторые из шариков– белые, и их количество четно. Разрешается указать на любые две коробочки и спросить, есть ли в них хотя бы один белый шарик. За какое наименьшее количество вопросов можно гарантированно определить какие-нибудь две коробочки, в которых лежат белые шарики?Решение
Занумеруем коробочки (и соответственно шарики в них) числами от 1 до 2004 и будем вопрос обозначать парой номеров коробочек. Будем называть небелые шарики черными.Покажем, что за 4005 вопросов можно найти два белых шарика.
Зададим вопросы (1,2), (1,3), (1,2004), (2,3), (2,4), (2,2004).
Если все ответы положительны, то первый и второй шарики белые (пусть, например, первый– черный; тогда есть еще хотя бы один черный шарик, который вместе с первым составляет черную пару).
Если же хотя бы один ответ отрицателен (скажем, на вопрос, включающий первый шарик), то первый шарик черный; тогда белыми являются ровно те шарики, про которые (в паре с черным первым) ответ был положительным, и в этом случае мы найдем даже все белые, которых хотя бы два.
Пусть существует алгоритм, позволяющий гарантированно найти два белых шарика за меньшее число вопросов. Будем отвечать на все вопросы положительно.
Тогда максимум после 4004 вопросов игрок сможет указать на какие-то (для определенности, первую и вторую) коробочки и заявить, что в них шарики белые. При этом какого-то из вопросов вида (1,n) или (2,n) (скажем, вопроса (1,k) ) задано не будет, ибо таких вопросов всего 4005. Положим теперь в 1-ю и k -ю коробочку черные шарики, а во все остальные– белые. Тогда все наши ответы будут верны, а указанный игроком первый шарик окажется черным. Противоречие.
