Задачку только что придумал

[spamsink]

Надо записать, а то пойду спать и забуду.

Имеется черный ящик, в котором внутри реализована некоторая фиксированная перестановка из N элементов. У ящика можно попросить сгенерировать случайную строку из N бит, с независимыми равновероятными 0 и 1 в каждой  позиции, произвести над ней эту свою перестановку, и показать исходную строку и результат.

Comments

[relf]

По грубой прикидке около log2(N). Каждый запрос для первой позиции дает ~N/2 кандидатов для его образа, где один настоящий, а остальные случайные. Каждый случайный кандидат появляется с вероятностью ~1/2 и ожидаемо не должен появиться (хотя бы раз) в ~log2(N) раундах. Аналогично для остальных позиций. И это я еще не учёл, что выяснение настоящего образа для одной позиции исключает его из кандидатов для остальных, что ускоряет процесс.

[rengsolo]

Интуитивно я бы в формулировке задачи добавил бы "с определенной вероятностью определить перестановку". Ведь задача сведется к покрытию множества случайными подмножествами...

[relf]

Другой взгляд. Посмотрим на перестановку как двудольный граф паросочетания с N рёбрами. Изначально у нас нет никакой информации - и любое ребро из N^2 в полном двудольном графе может быть искомым. Каждой обращение к чёрному ящику удаляет каждое лишнее ребро с вероятностью ~1/2. После k обращений у нас остаётся ~(N^2-N)/2^k лишних рёбер, что опять же дает, что k = O(log2(N)) должно хватить.

[spamsink]

При самостоятельно выбираемых пробах просто ceil(log2(N)) хватает; вопрос, насколько именно ухудшается ответ в случайном случае, пардон за каламбур.

[relf]

Случайный случай как раз и дает вероятность ~1/2 удалить "левое" ребро (каждое по отдельности).

[spamsink]

Что O останется логарифмическое, более или менее понятно, а вот будет этот результат отличаться от оптимального ceil(log2(N)) на аддитивную константу, или на мультипликативную - ещё вопрос.

Что результат для тщательно сконструированных проб и для случайных может быть одинаковым - не верится совсем. Но если это действительно так, то тоже будет парадокс.

[buddha239]

Если m раз сгенерировать случайную строку из N бит, то это то же самое, что сопоставить каждой позиции число от 0 до 2^m-1. Нужно добиться, чтобы все N чисел были разными. Если 2^m "сильно меньше" N^2, то шансы на это (легко считаются и) очень малы. Если "сильно больше", то велики. Так что, действительно, получается 2log_2N.:)

[papa_lyosha]

Если обозначить F(N,k) как вероятность того, что после k вопросов (или раньше) мы будем знать перестановку, то легко получить рекуррентную формулу:
F(N,k) = sum C(N,i) F(i,k-1) F(n-i,k-1),
где суммирование ведется по i от 0 до N, а C(N,i) - биномиальные коэффициенты.
Граничные условия:
F(0,k)=1
F(1,k)=1
F(N,0)=0, при N>1
Отсюда по индукции следует, что
F(N,k) = prod (1 - i * 1/2^k), для i=0..n-1
Тогда можно получить и матожидание. Одной формулой у меня не получилось, но первые члены такие
2, 10/3, 88/21, 512/105, 5874/1085 ...

[spamsink]

Симуляцией получается, что для N=2k результат похож на 2k+1/3.

[papa_lyosha]

У меня тоже самое получается. Используя мою F для вероятности, матожидание можно найти как
M(N) = sum (1-F(N,k) ) для k=0..+inf
Тогда компьютер говорит, что
M(1024) = 20.3322776
Т.е. действительно похоже на 2*10+1/3.

[spamsink]

Для k < ceil(log2(N)) формула для f(N, k) должна давать ноль, но не даёт.