Имеется черный ящик, в котором внутри реализована некоторая фиксированная перестановка из N элементов. У ящика можно попросить сгенерировать случайную строку из N бит, с независимыми равновероятными 0 и 1 в каждой позиции, произвести над ней эту свою перестановку, и показать исходную строку и результат.
Сколько в среднем запросов нужно сделать, чтобы однозначно определить, какая внутри ящика перестановка?
Например, при N=2, c вероятностью 50% случайная строка нам ничего не скажет (если она оказалась 00 или 11, то она такая и останется), а с вероятностью 50% мы узнаем, какая из двух возможных перестановок была реализована. Итого, ожидаемое количество проб S = 0.5*(1+S) + 0.5*1, т. е. S = 2. Для N=3 уже нужна бумажка. А дальше я и не знаю.
This entry was originally posted at https://spamsink.dreamwidth.org/1239092.html. Please comment there using OpenID.