задача дня-17

[falcao]

Не так давно встретилась задача -- скорее всего, она известная. Слишком уж естественная у неё формулировка. В таких случаях кому-то может быть известно "авторское" решение, которое мне было бы интересно узнать

Comments

[mathreader]

Не решение пока, а переформулировка. Перенумеруем замки 1..n и ключи 1..n, но соответствие, какой ключ подходит к какому замку, определяется перестановкой:

1 2 ... n

k1 ... kn

Требуется "восстановить" эту перестановку за минимальное число тестов. Каждый тест имеет два исхода: "не подходит" (0), или "подходит" (1). Каждый тест с результатом 0 исключает (n-1)! возможных перестановок, а каждый тест с результатом 1 сужает "фазовое пространство" перестановок в n раз в первый раз, в n-1 раз во второй раз и т.д.

Получается алгоритмическая задача как покрыть "пермутаэдр" всех перестановок минимальным количеством множеств вполне конкретного вида, имеющих мощность (n-1)!, так, чтобы дополнение к ним всем было одно-элементным. При этом если у нас получился тест с результатом 1, то фазовое пространство сжимается, но счетчик использованных множеств все же увеличивается на 1.

Вот картинка для n=4

[falcao]

Мысль о рассмотрении множества перестановок у меня тоже возникала, но процесс этот очень трудно контролируем. По крайней мере, я не знаю, как эту идею можно применить. Мы исключаем на одном шаге перестановки, переводящие i в j после неудачной пробы, но множества этого типа друг с другом как-то сложно пересекаются. И общая картина при этом не ясна.