Задачку только что придумал
Jan. 20th, 2022 01:21 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
spamsinkНадо записать, а то пойду спать и забуду.
Имеется черный ящик, в котором внутри реализована некоторая фиксированная перестановка из N элементов. У ящика можно попросить сгенерировать случайную строку из N бит, с независимыми равновероятными 0 и 1 в каждой позиции, произвести над ней эту свою перестановку, и показать исходную строку и результат.
Сколько в среднем запросов нужно сделать, чтобы однозначно определить, какая внутри ящика перестановка?
Например, при N=2, c вероятностью 50% случайная строка нам ничего не скажет (если она оказалась 00 или 11, то она такая и останется), а с вероятностью 50% мы узнаем, какая из двух возможных перестановок была реализована. Итого, ожидаемое количество проб S = 0.5*(1+S) + 0.5*1, т. е. S = 2. Для N=3 уже нужна бумажка. А дальше я и не знаю.
Имеется черный ящик, в котором внутри реализована некоторая фиксированная перестановка из N элементов. У ящика можно попросить сгенерировать случайную строку из N бит, с независимыми равновероятными 0 и 1 в каждой позиции, произвести над ней эту свою перестановку, и показать исходную строку и результат.
Сколько в среднем запросов нужно сделать, чтобы однозначно определить, какая внутри ящика перестановка?
Например, при N=2, c вероятностью 50% случайная строка нам ничего не скажет (если она оказалась 00 или 11, то она такая и останется), а с вероятностью 50% мы узнаем, какая из двух возможных перестановок была реализована. Итого, ожидаемое количество проб S = 0.5*(1+S) + 0.5*1, т. е. S = 2. Для N=3 уже нужна бумажка. А дальше я и не знаю.
no subject
Date: 2022-01-20 09:42 am (UTC)eg N=4. 0011=>1100 and 0101=>1001 provides a solution. Is it even possible to decide analytically that this combination of black box responses provides a solution without trying this combination?
no subject
Date: 2022-01-20 04:47 pm (UTC)no subject
Date: 2022-01-20 05:25 pm (UTC)I don't quite understand what "constructing all intersections of sets" means in this context, but certainly the existence of "all" makes me think that you do need to try all combinations of inputs and outputs.
no subject
Date: 2022-01-20 05:51 pm (UTC)no subject
Date: 2022-01-20 06:18 pm (UTC)eg
0011
0101
- all columns unique
But also need to check
1100
0101,
0101
0011,
...
and even longer sequences:
0011
0100
0001
etc. Don't you need to do this? Or is there a cheaper method than just enumerating?
no subject
Date: 2022-01-20 10:20 pm (UTC)I think after a few tries it would be possible to disambiguate the "input" and the "output" strings based on mutual consistency, so the number of tries could likely be the same as for the first variant, with the only difference that the figured out permutation would be either the one in the box or its inversion.
no subject
Date: 2022-01-21 07:32 am (UTC)no subject
Date: 2022-01-20 03:18 pm (UTC)О, это получается аналог судоку! Там мы тоже строим список того, какие позиции могут содержать какие числа, и вычеркиваем логические невозможности.
no subject
Date: 2022-01-20 04:42 pm (UTC)Минимумом будет честный log2(N) - перенумеруем биты по порядку и сначала подаем единицы там, где младший бит номера - единица, потом - где следующий, и т.п. А вот насколько хуже будет рандомизированный вариант, я не чувствую.
no subject
Date: 2022-01-21 04:22 am (UTC)no subject
Date: 2022-01-20 03:34 pm (UTC)что бы проверить что сеть сортировки правильная, вместо проверки всех возможных перестановок n! на входе достаточно проверить все варианты нулей и единичек 2^n - https://en.wikipedia.org/wiki/Sorting_network#Zero-one_principle
no subject
Date: 2022-01-20 04:38 pm (UTC)