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