что-то заглохло всё)
пока самая дельная мысль высказана в одном из сообщений Майтона

Соколинский Борис,

приближение неплохое)

VladimirKr,

да, всё верно.

при такой вероятности, 32 исхода можно разделить на 16 пар, в каждой паре два "поразрядно противоположных" исхода, тогда будет одна пара с вероятностью 1/5, 5 пар с вероятностью каждой 2/25, и 10 пар по 1/25, что легко разбивается на 5 равных кучек.

Майтон правильно заметил вот что:


это элементарно доказывается: если P = m/n, где m > 1 и НОД(n, m) = 1, то у всех (кроме одного) исходов вероятностного пространства k испытаний будет вероятность вида m * (натуральное_число) / n^k, такая же вероятность будет у 4 из 5 кучек, а это нельзя сократить до 1/5

попробую чуть подробнее.

напомню, что рассматриваем m/n, такое что m и n взаимно просты, и m > n-m (то есть берем большую из вероятностей орла и решки), откуда m > 1, так как случай р=1/2 очевидно не подходит.

согласен.
причем есть только один исход (n-m)^k/n^k, остальные будут содержать m в числителе.

согласен.

однако все суммы числителей, кроме одной (той самой, в которую попадет (n-m)^k) будут делиться на m, так как все слагаемые этих четырёх сумм делятся на m.

но тогда каждая из этих четырёх сумм не может быть пятой частью от n^k, так как n^k не делится на m (m и n - взаимно простые), значит не делится на сумму.

если требуется минимальный k для равновероятного выбора одного числа из N, то задача весьма сложная и многоплановая...

по правде сказать, я не до конца уверен в минимуме для N=5.

сам по себе подход, когда берем

для многих чисел дает не минимум. Например для 6 это не прокатит: для 6 можно сделать за 5 вызовов рандомайзера, а при такой вероятности за 5 не получится, P ⁵ > 1/6

в общем, здесь всё просто и понятно только для степени двойки )