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