Задача 109194

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

Сложность: 5- Классы: 8,9,10

Условие

Автор: Шаповалов А.В.

У ведущего есть колода из 52 карт. Зрители хотят узнать, в каком порядке лежат карты (при этом не уточняя   сверху вниз или снизу вверх). Разрешается задавать ведущему вопросы вида "Сколько карт лежит между такой-то и такой-то картами?". Один из зрителей подсмотрел, в каком порядке лежат карты. Какое наименьшее число вопросов он должен задать, чтобы остальные зрители по ответам на эти вопросы могли узнать порядок карт в колоде?

Решение

  Алгоритм. Покажем, как установить порядок карт за 34 вопроса. Разобьём все карты колоды (занумерованные снизу вверх), кроме 19-й, на тройки:

  В каждой тройке двумя вопросами определим расстояния между крайними, а также между нижней и средней картами. После этого ясно, что
  1) 1-я и 52-я карты – крайние в колоде. В силу условия можно считать, что 1-я карта – нижняя, а 52-я – верхняя. При этом 18-я карта также окажется на своем месте.
  2) Каждая следующая тройка "плотно" вставляется в предыдущую. Априори это можно сделать двумя способами. Средняя карта тройки примыкает (во всех тройках, кроме первой) к соответствующей крайней (эти две карты назовем толстым концом).
  3) Между концами 17-й тройки остается еще два места. Эта тройка вставлена во все предыдущие, поэтому эти места "заняты" 18-й и 19-й картами. То есть 18-я карта находится внутри 17-й тройки и, тем более, внутри всех предыдущих троек.
  Поскольку ниже 18-й карты всего 17 мест, то они заняты тонкими концами всех троек. Таким образом, расположение карт восстанавливается однозначно – так, как указано в таблице.
  Оценка. Разобьём изначально все карты на 52 группы по одной карте. При вопросе про две карты из разных групп объединяем эти группы. Тем самым, каждый вопрос уменьшает число групп максимум на одну. Если задано не более 33 вопросов, то останется не менее 19 групп. Среди них групп из трёх (и более) карт – не больше 17. Значит, либо найдётся группа из двух карт, либо две группы по одной карте. В обоих случаях можно эту пару карт поменять местами, не трогая остальных: при этом все ответы не изменятся. Тем самым, порядок не восстанавливается однозначно.

Ответ

34 вопроса.

Замечания

1. 9 баллов.

2. Задача также опубликована в Задачнике "Кванта" ("Квант", 2007, №1, М2033).

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

олимпиада
Название	Турнир городов
Турнир
Номер	28
Дата	2006/2007
вариант
Вариант	осенний тур, основной вариант, 8-9 класс
задача
Номер	7