| Задача о лотерейном билете. ID:46745 |
Пт, 25 апреля 2003 00:00 [#] [») |
|
|
Есть несколько (реально - 37) пронумерованных стеклянных ящичков, куда участники лотереи кидают билеты. Розыгрыш проходит следующим образом: сначала случайным образом (на рулетке) определяется счастливый бокс (ящичек), затем случайным образом из всех билетов этого бокса выбирается один.
Задача. Пусть у нас на руках N билетов. У нас есть возможность последними бросить билеты в боксы, причем количество уже брошенных билетов в каждом боксе можно определить (ящички - стеклянные). Каким образом нужно распределить билеты чтобы был максимальный шанс выиграть в лотерее?
Пример. Пусть будет только два бокса. У нас на руках 4 билета, в боксах находятся 24 "чужих" билета.
Тогда, если билеты распределены равномерно (12+12) то самое выгодное бросить в каждый ящичек по 2 своих билета.
Если в первом боксе 10, во втором 14, то нужно бросить 3 и 1 билет соответственно для масимального шанса.
И если, наконец, во втором боксе в два раза больше билетов чем в первом (8+16) то все 4 билета выгоднее бросить в первый бокс.
А как решать эту задачу в общем случае? А если боксов 37, и есть возможность примерно определить распределение билетов (в процентах, например) и у нас на руках не 4, а сотня билетов?
Надеюсь, что задачка понравится.
Скайтс.
|
|
|
| Re: Задача о лотерейном билете. ID:46747 ответ на 46745 |
Пт, 25 апреля 2003 00:00 («] [#] [») |
|
|
Привет, Скаитс!
Задачка, действительно, занимательная 
Предлагаю на общий суд свой вариант решения:
Основная идея: каждый билет должен максимально повышать наше МО.
Пусть Бокс1 содержит N1 билетов, Бокс2 содержит N2 билетов, ...Бокс37 содержит N37 билетов.
N - всего билетов в боксе,
OurN - кол-во наших билетов в боксе
Опуская очередной билет в некий бокс, мы получаем :
OurN/N - МО нашего выигрыша , если выпадет это бокс (до опускания билета)
(OurN+1)/(N+1) - МО нашего выигрыша , если выпадет это бокс (после опускания билета)
Приращение МО: (OurN+1)/(N+1) - OurN/N
Сокращая дробь, получаем f(n) = (N - OurN) / (N*N + N)
Ответ: Для того, чтобы принять решение куда опускать очередной билет, необходимо рассчитать
(N - OurN) / (N*N + N) для каждого бокса и опустить туда, где f(n) -максимально.
|
|
|
| Re: Задача о лотерейном билете. ID:46756 ответ на 46745 |
Пн, 28 апреля 2003 00:00 («] [#] [») |
|
| Лох Чилийский |
|
Форумы Покер.ру
|
|
Вспомнился весьма поучительный случай. На рулетке остаются в принципе незаполненными 5
номеров. Подходит сурьезный дядя и за минуту до спина, раз и ставит все свои билеты (около 15-
ти) в один из пустых номеров. И отходит.
Так вот что главное - угадал  ))
А Вы говорите, математика.
P.S. Сам не видел, но человеку рассказавшему верю безоговорочно. Он заставил по билету в
четыре оставшихся номера, и по уму раскидал остатки. И что главное - не угадал ))
|
|
|
| Re: Задача о лотерейном билете. ID:46759 ответ на 46747 |
Вт, 29 апреля 2003 00:00 («] [#] [») |
|
|
Jack Daw, здравствуйте.
Для справедливости этого решения нужно доказать, что сумма нескольких последовательных максимальных
приращений МО всегда больше или равна сумме такого же числа другой последовательности приращений.
М.б.существует вариант, при котором сначала прирост МО небольшой, но последующие докладывания билетов
дают бОльший эффект.
Это основная проблема методов оптимизации - глобальный максимум может занимать очень малую площадь (к
тому же может быть окружен локальными максимумами) и не всегда двигаясь вверх (пусть даже максимально
быстро) можно его найти.
Миша.
P.S. Прошу прошения за неправильно приведенный (и удаленный) контрпример, а также за исправления поста.
|
|
|
| Re: Задача о лотерейном билете. ID:46760 ответ на 46745 |
Вт, 29 апреля 2003 00:00 («] [#] [») |
|
|
Скаитс, привет.
Сразу скажу, что задачу я не решал по причине неприязни к дискретным методам оптимизации (начиная с
симплекс-метода и дальше).
Это типичная задача нелинейного математического программирования :
ЦФ=1/N*СУММ_i=1..N(MTi/(MTi+ATi)), для ЦФ ищется максимум,
Система ограничений : СУММ_i=1..N(MTi)=ALL_MT,
где : N - число ящиков,
MTi - количество “наших” билетов в i-том ящике,
ATi - количество чужих билетов в i-том ящике,
ALL_MT - общее число “наших” билетов.
Возможно, ЦФ имеет некую особенность, позволяющую найти точное решение, не используя общие методы. Если
это так - скажи, плз, я “помучаюсь”. Если таковой нет, я - пас.
Удачи.
Миша.
|
|
|
| Re: Задача о лотерейном билете. ID:46761 ответ на 46760 |
Вт, 29 апреля 2003 00:00 («] [#] [») |
|
|
Привет, Михаил!
Решение этой задачки привел в первом посте Jack Daw. Очень простое и эффектное решение.
Если не нравится эта задача, то есть еще несколько казиношно-лотерейных задачек (возникших
на основе реальных лотерей), которые я, с удовольствием, представлю публике.
По поводу практической ценности этих задачек. Не знаю как в столице (Москве), но в нашем
городе, вероятность попасть в розыгрыш и выиграть лотерею достаточно велика. А многие
лотереи предполагают принятие решений играющими, и шанс получить приз сильно зависит от
правильности принятия таких решений.
Удачи,
Скайтс.
|
|
|
| Re: Задача о лотерейном билете. ID:46762 ответ на 46761 |
Вт, 29 апреля 2003 00:00 («] [#] [») |
|
|
Привет. Я видел, но пока это решение без доказательства. Ты уверен, что оно точное ?
Миша.
P.S. Не задача не нравится, а упомянутые методы.
|
|
|
| Re: Задача о лотерейном билете. ID:46763 ответ на 46762 |
Вт, 29 апреля 2003 00:00 («] [#] [») |
|
|
Не уверен.
Если мы раньше (на угад) покидали билетов и у нас стоит задача куда кинуть последний билет, то
данный метод (то что предложил Jack Daw ) дает правильный ответ.
Возможно, здесь для доказательства алгоритма в общем случае нужно использовать метод
математической индукции?
Доказательства у меня пока нет. Есть маленький макрос на Экселе, который для указанных
условий (кол-ва боксов и кол-во чужих билетов в каждом боксе) раскидывает билетики по
вышеизложенному алгоритму.
|
|
|
| Re: Задача о лотерейном билете. ID:46765 ответ на 46763 |
Ср, 30 апреля 2003 00:00 («] [#] [») |
|
|
Скаитс, привет.
Извини, что не сумею сейчас подробно ответить - исчезаю на несколько дней. Тут дело не в индукции. Если
целевая функция (в нашем случае это МО) имеет ОДИН максимум, то этот алгоритм применим. Представь себе
перевернутую рюмку без ножки. Как ни двигайся по одной координате, потом по другой, лишь бы вверх - придешь
к вершине. Этот случай похоже как раз такой. Можно, например, сначала раскидать все билетики равномерно, а
затем по одному перекладывать, пока достигается рост МО. Результат будет тот же. И возьми более сложную
ЦФ - в виде горной гряды, здесь такие алгоритмы могут завести тебя на маленькую вершинку, а самый максимум
ты не найдешь. К счастью, они не будут придумывать такие безумные правила, чтобы ЦФ приобрела подобный
вид -)).
Удачи.
Миша.
|
|
|
| Почти доказательство :-) ID:46768 ответ на 46763 |
Пт, 2 мая 2003 00:00 («] [#] |
|
|
Всем привет.
Да, Миша, ты оказался совершенно прав, указывая на пробелы в предлагаемом мной
методе. "На любой сложный вопрос есть простой неправильный ответ"
Тем не менее, попробую обосновать свою точку зрения. Я также не пылаю большой любовью
симплекс-методу (что обусловлено, скорее, стилем преподавания в вузе, чем, собственно,
дисциплиной), поэтому предложенное доказательство построено на логических рассуждениях и
стандартных методах матанализа.
Докажем (Утверждение 1), что для любого конкрентого бокса приращение МО при опускании
ТЕКУЩЕГО билета больше, чем приращение МО при опускании в него СЛЕДУЮЩЕГО билета.
Иными словами, что:
(OurN+1)/(N+1) - OurN/N > (OurN+2)/(N+2) - (OurN+1)/(N+1), где OurN и N - натуральные числа,
причем N >= OurN.
(OurN+1)/(N+1) - OurN/N - (OurN+2)/(N+2) + (OurN+1)/(N+1) > 0
Опуская промежуточные преобразования, получаем:
(OurN*N + 2*N - 2*OurN) / N*(N+1)*(N+2) > 0
Очевидно, что числитель и знаменатель всегда больше 0. (т.к. N >= OurN), следовательно, и сама
дробь тоже всегда больше 0 при натуральных OurN и N.
Утверждение 1 доказано.
Теперь докажем (Утверждение 2), что, следуя предложенному в моем предыдущем посте
алгоритму, мы найдем OurN маскимально возможных приращений, из всех, которые только могут
возникнуть на любом из боксов при опускании неограниченого количества билетов в течениие
неограниченого времени.
Доказательство от противного. Согласно алгоритму ("рассчитать (N - OurN) / (N*N + N) для
каждого бокса и опустить туда, где f(n) -максимально."), мы находим для шага i максимальное
возможное приращение МО на данный момент времени.
Предположим, что на некоем шаге 'x' на каком-то из боксов 'b1' существует некое приращение МО
(delta MO(x,b1)), которое больше, чем мы нашли на на шаге 'i' на боксе 'b2' (delta MO(i,b2)). Тогда:
delta MO(x,b1) > delta MO(i,b2)
Так как, согласно нашему алгоритму, delta MO(i,b2) максимально на шаге i, то delta MO(i,b2) >=
delta MO(i,b1).
Следовательно,
delta MO(x,b1) > delta MO(i,b1), причем, x>i.
Это противоречит Утверждению 1, следовательно, сделанное нами предположение неверно.
Не существует в дальнейшем такого приращения МО, которое больше, чем найденное в данный
момент.
Вышеизложенное справедливо для всех i на диапазоне 1...OurN.
Утверждение 2 доказано.
Пусть есть оптимальное решение Sопт.
Его можно представить в виде суммы прирашений МО, полученных при последовательном
опускании билетов в ящики:
Sопт = delta MO(1,b1) + delta MO(2,b2) + ...+ delta MO(OurN,bOurN)
Расставим слагаемые по убыванию и сравним эту сумму с суммой прирашений, полученых следуя
нашему алгоритму, где delta MOmax(i) - прирашение МО, максимальное на i шаге:
Sалг = delta MOmax(1) + delta MOmax(2) + ...+ delta MOmax(OurN).
Количество слагаемых одинаковое (OurN), причем (из Утверждения 2) каждое i-е слагаемое из
Sалг больше или равно i-му слагаемому из Sопт, следовательно Sалг >= Sопт. По условию Sопт
есть оптимальное решение.
Следовательно Sалг =Sопт, что и требовалось доказать.
Best regards.
|
|
|
