Смоделируйте использование игральной кости с семью гранями, если в вашем распоряжении имеется только кость с пятью гранями

Как вы можете получить случайное число в диапазоне от 1 до 7, используя игральную кость с пятью гранями?

Иначе говоря, в вашем распоряжении устройство, которое генерирует случайное целое число от 1 до 5. Но вам необходимо воспользоваться им для генерирования случайных чисел в диапазоне от 1 до 7. Представьте, что семь человек с лотерейными билетами под номерами от 1 до 7 страстно ждут розыгрыш. Как вы используете кость с пятью сторонами, чтобы выбрать победителя, заведомо зная, что проигравшие будут недовольны и что вам, возможно, придется в суде доказывать, что процедура определения победителя была совершенно случайной.

Есть несколько простых идей, но, увы, они могут показаться несправедливыми. Одна из них — бросить кость дважды и сложить выпавшие числа. Это даст результат в диапазоне от 2 до 10. Кажется, все справедливо? Нет. Любой знает, что не все суммы двух бросков в равной степени вероятны. Сумма в середине распределения (7) более вероятна. То же самое верно и в отношении кости с пятью сторонами.

Другая идея — бросить кость дважды и умножить полученные значения или каким–то другим способом получить на их основе большее число. Затем разделить его на 7 и взять только остаток. Остаток будет в диапазоне от 0 до 6. 0 нам не нужен, и поэтому будем считать его за 7. Такой вариант обеспечит нам получение «случайного» числа в диапазоне от 1 до 7.

Я поставил слово «случайный» в кавычки, потому что математик Джон фон Нейман писал, что любой, кто рассматривает арифметические методы получения случайных чисел, попадает, конечно, в «страну греха». Хотя такой подход для некоторых целей может быть вполне приемлем, результат на самом деле не является в полной мере случайным, и поэтому в Google или Amazon такой ответ высоко не ценится. А вот в Интернете числа должны быть действительно случайными, так как в противном случае хакеры воспользовались бы этим преимуществом. В казино, например.

Для получения действительно случайного исхода пусть каждый из семи игроков бросает кость с пятью сторонами один раз. Игрок, показавший более крупное число, выигрывает. Если высшее значение показали несколько игроков, они бросают кость снова (столько раз, сколько необходимо). Единственный минус в таком подходе — возможно, придется много раз подбрасывать кость. Даже если равенства (ничьих) не будет, потребуется семь бросков.

Есть более совершенный ответ. Подумайте более внимательно о цифрах. Числа с 1 по 7 можно представить в виде трех битов, то есть бинарных чисел от 001 до 111. Можете ли вы сгенерировать три случайных бита, используя кость с пятью сторонами?

Разумеется, каждый бросок даст вам одну цифру трехбитного числа. Если выпадет 2 или 4, назовите результат ноликом, если 1 или 3 — единица, если 5 — бросайте снова. Продолжайте бросать столько, сколько необходимо, если выпадет пятерка.

Повторение этой процедуры три раза генерирует число в диапазоне от 000 до 111. Переведите снова в десятичное исчисление, и тогда человек, у которого выпало большее число, выигрывает (например, 101 означает, что выиграл лотерейный билет № 5). Если выпал 000, проведите броски снова.

Это потребует всего три броска кости, если не будет повторений. В среднем при таком подходе требуется чуть больше четырех бросков.

Разбор головоломки по книге «Действительно ли Вы достаточно умны, чтобы работать в Google?»