Девятый бит: Блог кафедры АСОИУ ОмГТУ

Семь галстуков и один кубик

У Петра Петровича было шесть галстуков, и когда ему нужно было выбрать какой-нибудь из них, то он бросал кубик и надевал галстук, номер которого выпал на кубике. Таким образом, у всех галстуков были равные шансы быть выбранными.

Но вот, на день рождения, друзья подарили Петру Петровичу еще один, седьмой, галстук. Как теперь, пользуясь только кубиком, Петр Петрович может выбрать один из семи галстуков, чтобы у всех галстуков шансы быть выбранными оставались равными?

Задачку придумал Дмитрий Ланин.

  • Бросить два раза. Первый бросок определяет, четные или нечетные галстуки выбираются (если число на кубике нечетное, то выбор ведется среди 1, 3, 5, 7 галстука, если четное, то среди 2, 4, 6). Дальше оставшиеся галстуки нумеруются по новой (например, в первом случае 7-й галстук будет 4-м), и кубик бросается вновь, чтобы определить галстук, который одеваем.

    Вероятность того, что при первом броске число будет четным или нечетным, равна 0,5. Вероятность же выпадения конкретного номера галстука при втором броске равна 1/6 (да, иногда придется бросать дважды). Т. е. шанс выбора конкретного галстука равен 1/12 :-) .

  • 2 Глеб Еремеев: // Первый бросок определяет, четные или нечетные галстуки выбираются (если число на кубике нечетное, то выбор ведется среди 1, 3, 5, 7 галстука, если четное, то среди 2, 4, 6) //
    Получается несимметричная ситуация: в половине случаев разбираем 4 галстука, а в другой половине — только 3. Шансы галстуков не будут равны.

  • «Получается несимметричная ситуация: в половине случаев разбираем 4 галстука, а в другой половине – только 3. Шансы галстуков не будут равны.»

    Будут, поскольку шанс выпадения каждого из галстуков равен 1/6 и в первом, и во втором случае. Правда, в некоторых случаях может выпасть число, не соответствующее ни одному из галстуков. В этом случае нужно будет бросить заново

    Однако ШАНС ВЫБОРА каждого из галстуков равен :).

  • Нужно три броска. Первый бросок определит первые 4 кандидата-галстука. Второй оставит из них 2. Третий определит финалиста :)

    Сразу видно не играли вы в D&D. А вообще открою тайну: существуют восьмигранные «кубики».

  • VoViaN, а как одним броском отсечь 3 из 7 (или выбрать 4 из 7)? Ведь число сочетаний из 7 по 3 (и по 4) равно 35 — не кратно 6.

    Глеб, твоё решение верное, требует 2 броска + с вероятностью 5/12 ещё 2 броска и т.д. Моё первое решение было похожим, только дерево пооптимальнее: на каждом броске выбираем одну из трёх ветвей, итого за два броска 9 листьев, из которых 7 нужных и 2 неудачных (требуется переброс обоих кубиков). Таким образом вероятность переброса 2/9, что почти в 2 раза меньше 5/12.

    Самое красивое решение предложил В.Н. Задорожный. Во-первых, за 2 броска с вероятностью переброса всего 1/36. Во-вторых, выбор галстука не требует мат. вычислений (т.е. выпавшие числа не требуется ни складывать, ни умножать и прочее). Попробуете догадаться?

  • упс. решил, что галстуков стало 8. Сейчас подумаю…

  • дурацкая капча!

    Галстуки группируются по 3. 7-й галстук поочередно добавляется в одну из групп. Требуется 2 или 3 броска для определения галстука в зависимости от того выбрали при первом броске группу из 3 галстуков или из 4-х.

    Вот только надо прикинуть будет ли такой способ равновероятным…

  • может быть 1м броском определяем один из 6 галстуков, 2м броском определяем седьмой (например приняв его за 6 на кубике). А если выпал дубль за два броска (6 и 6), то перебрасываем. Итого у каждого галстука вероятность выпадения 5/36, а переброса 1/36.
    Васин Антон (аспирант).

  • Да, Антон, это верное решение, и такая же схема (по сути) была у В.Н. Задорожного и у Дмитрия Ланина (автора задачи).

You must be logged in to post a comment.