Дана таблица n×n, столбцы которой пронумерованы числами от 1 до n. В клетки таблицы расставляются числа 1, ..., n  так, что в каждой строке и в каждом столбце все числа различны. Назовём клетку хорошей, если число в ней больше номера столбца, в котором она находится. При каких n существует расстановка, в которой во всех строках одинаковое количество хороших клеток?

   Решение

На окружности расположена тысяча непересекающихся дуг, и на каждой из них написаны два натуральных числа. Сумма чисел каждой дуги делится на произведение чисел дуги, следующей за ней по часовой стрелке. Каково наибольшее возможное значение наибольшего из написанных чисел?

   Решение

На столе стоят 2004 коробочки, в каждой из которых лежит по одному шарику. Известно, что некоторые из шариков – белые, и их количество четно. Разрешается указать на любые две коробочки и спросить, есть ли в них хотя бы один белый шарик. За какое наименьшее количество вопросов можно гарантированно определить какую-нибудь коробочку, в которой лежит белый шарик?

   Решение

Темы:    [ Теория алгоритмов (прочее) ] [ Оценка + пример ]

Сложность: 4+ Классы: 10,11

Прислать комментарий

Условие

На столе стоят 2004 коробочки, в каждой из которых лежит по одному шарику. Известно, что некоторые из шариков – белые, и их количество четно. Разрешается указать на любые две коробочки и спросить, есть ли в них хотя бы один белый шарик. За какое наименьшее количество вопросов можно гарантированно определить какую-нибудь коробочку, в которой лежит белый шарик?

Решение

Занумеруем коробочки (и соответственно шарики в них) числами от 1 до 2004 и будем вопрос обозначать парой номеров коробочек. Будем называть небелые шарики черными.

Покажем, что за 2003 вопроса можно найти белый шарик.
Зададим вопросы (1,2) , (1,3) , (1,2004) . Если все ответы положительны, то первый шарик белый (иначе есть еще хотя бы один черный шарик, и первый вместе с ним составит черную пару). Если же хотя бы один ответ отрицателен, то первый шарик черный; тогда белыми являются ровно те шарики, про которые (в паре с черным первым) ответ был положительным, и в этом случае мы найдем даже все белые.

Пусть существует алгоритм, позволяющий гарантированно найти белый шарик за меньшее число вопросов. Будем отвечать на все вопросы положительно. Тогда максимум после 2002 вопросов игрок сможет указать на какую-то (для определенности, первую) коробочку и заявить, что в ней шарик белый. При этом какого-то из вопросов вида (1,n) (скажем, вопроса (1,2) ) задано не будет, ибо таких вопросов всего 2003. Положим теперь в 1-ю и 2-ю коробочку черные шарики, а во все остальные– белые. Тогда все наши ответы будут верны, а указанный игроком шарик окажется черным. Противоречие.

Ответ

За 2003 вопроса.

Источники и прецеденты использования