Оптимальная стратегия подбора

·

Есть 4 кредитки и 6 пин–кодов. На каждой кредитке по три попытки, на третьей неправильной она блокируется. Какая самая оптимальная стратегия подбора?

GD Star Rating
loading...
Tagged with → •  

    7 Responses to Оптимальная стратегия подбора

    1. Moun:
      16/06/2010 в 02:49

      Вот мой пример развития событий:

      У нас есть 6 бумажек с пин–кодами. Вытягиваем на удачу 2 из них. Затем события развиваются по одному из 4х вариантов.

      1) Пробуем первый пин на всех 4х кредитках — не подошёл никуда. Пробуем второй пин — не подошёл никуда.
      Вероятность такого события — 1/15
      У нас есть 4 пин–кода и 4 кредитки, каждый пин подходит только к какой–то из них четырёх, но при ошибочной пробе кредитка залочится.
      Наудачу выбираем каждой кредитке пин и вот какие вероятности получаем:
      Угадано ровно 4 пина — 1/24
      Угадано ровно 3 пина — 0/24
      Угадано ровно 2 пина — 6/24
      Угадан ровно 1 пин — 8/24
      Угадано ровно 0 пинов — 9/24
      _
      Учитывая вероятность этого события:
      Угадано ровно 4 пина — 0.28 %
      Угадано ровно 3 пина — 0.00 %
      Угадано ровно 2 пина — 1.66 %
      Угадан ровно 1 пин — 2.22 %
      Угадано ровно 0 пинов — 2.50 %

      2) Пробуем первый пин на всех 4х кредитках — не подошёл никуда. Пробуем второй пин — подошёл к последней кредитке #4 (в худшем случае).
      Вероятность такого события — 4/15 (2/6*4/5)
      У нас есть 4 пин–кода и 3 кредитки, каждый пин подходит только к какой–то из них 3, кроме одного, не подходящего ни к одной. При каждой неправильной пробе кредитка лочится.
      Наудачу выбираем каждой кредитке из 3х один пин из 4 и вот какие вероятности получаем:
      Угадано ровно 3 пина — 1/24
      Угадано ровно 2 пина — 3/24
      Угадан ровно 1 пин — 9/24
      Угадано ровно 0 пинов — 11/24
      _
      Учитывая вероятность этого события и уже отгаданный пин:
      Угадано ровно 4 пина — 1.11 %
      Угадано ровно 3 пина — 3.33 %
      Угадано ровно 2 пина — 10.00 %
      Угадан ровно 1 пин — 12.22 %
      Угадано ровно 0 пинов — 0 %

      3) Пробуем первый пин на всех 4х кредитках — подошёл к последней кредитке #4 (в худшем случае). Пробуем второй пин — не подошёл никуда.
      Вероятность такого события — 4/15 (2/6*4/5)
      У нас есть 4 пин–кода и 3 кредитки, каждый пин подходит только к какой–то из них 3, кроме одного, не подходящего ни к одной. При каждой неправильной пробе кредитка лочится. Случай аналогичен случаю 2)

      4) Пробуем первый пин на всех 4х кредитках — подошёл к последней кредитке #4 (в худшем случае). Пробуем второй пин — подошёл к последней кредитке #3 (в худшем случае).
      У нас есть 4 пин–кода и 2 кредитки, 2 пина из 4х подходят только к каким–то 2м кредиткам соответственно. При каждой неправильной пробе кредитка лочится.
      Угадано ровно 2 пина — 1/12
      Угадан ровно 1 пин — 4/12
      Угадано ровно 0 пинов — 7/12
      _
      Учитывая вероятность этого события и уже отгаданный пин:
      Угадано ровно 4 пина — 3.33 %
      Угадано ровно 3 пина — 13.33 %
      Угадано ровно 2 пина — 23.33 %
      Угадан ровно 1 пин — 0 %
      Угадано ровно 0 пинов — 0 %
      _
      –––––––––––––––––––––––––––––––––––––––– –––––––––––––––––––––––––––––––––––––
      _
      Суммируя вероятности, получаем:
      Угадано ровно 4 пина — 5.83 %
      Угадано ровно 3 пина — 20.00 %
      Угадано ровно 2 пина — 45.00 %
      Угадан ровно 1 пин — 26.66 %
      Угадано ровно 0 пинов — 2.50 %
      \суммарно ~100%, слава блять богу

      Ну и что мы получаем при такой стратегии
      Есть доступ до всех кредиток — 5.83%
      Есть доступ хотя бы до 3х кредиток — 25.83%
      Есть доступ хотя бы до 2х кредиток — 70.83%
      Есть доступ хотя бы до 1ой кредитки — 97.83%
      Все кредитки проёбаны — 2.50%

      Ответить
    2. Dr4:
      16/06/2010 в 19:24

      что такое «самая оптимальная стратегия»?
      я вроде бы умею гарантированно открывать хотя бы 1 — такое решение было бы оптимальным?
      или обязательно считать, с какой вероятностью будет 2, 3, 4?

      Ответить
    3. Moun:
      16/06/2010 в 19:51

      оптимальная стратегия — это «я хочу получить как можно больше работающих карточек, что мне делать»

      Ответить
    4. Dr4:
      16/06/2010 в 19:56

      ок, имеем две стратегии: A(p4, p3, p2, p1, p0) и B(q4, q3, q2, q1, q0), в скобках — вероятность получить ровно столько карточек такой стратегией
      как их сравнить?

      Ответить
    5. AkMoon:
      16/06/2010 в 23:06

      если деньги на кредитках не имеют значения или равны то: р4*4+р3*3+р2*2+р1 сравнить с q4*4+q3*3+q2*2+q1*1

      Ответить
    6. Dr4:
      16/06/2010 в 23:29

      да, это логичный вариант
      но не менее логичный — минимизировать p0
      а если на одной карточке существенно больше, чем на других, то, возможно, лучше максимизировать p4
      в общем, интересно, что автор имел в виду

      Ответить
    7. Peels:
      17/06/2010 в 00:46

      Как правильно написал Dr4 понятие оптимальности относительно, но я бы делал так:
      Сортируем карточки и пины произвольно.
      Проверяем первые три пина на первой карточке. Если один из пинов подошел — убираем его из списка.
      Проверяем первые три пина на второй карточке. Если один из пинов подошел — убираем, и т.п.

      Во–первых, легко заметить что одна карточка откроется с вероятностью 100%.
      Во–вторых, все четыре карточки откроются с вероятностью
      3/6 * 3/5 * 3/4 = 22.5%
      В–третьих, по крайней мере две карточки откроются с вероятностью, большей чем
      1–1/2*1/2 = 75%

      Это уже выглядит лучше чем вариант предложенный выше.

      Ответить

    Добавить комментарий