Блог им. unC0RrСчастливые билетики

Про счастливые билеты написано довольно много: оценка количества таких билетов, общая формула для n-значных билетов в m-ичной системе счисления, московская и ленинградская системы определения «счастливости», график распределения счастливых билетов. Как стартовую точку по этой теме, рекомендую статью на Википедии.

Тем не менее, счастливые билеты хранят в себе некоторые пока неисследованные тайны, о которых я расскажу.

Речь пойдёт о распределении счастливых билетов. Количество шестизначных счастливых билетов равняется 55252, следовательно, вероятность получить такой билет равняется 0,055252. Но какова вероятность получить счастливый билет в случае, когда вы едете не один, и покупаете сразу несколько билетов? Теория вероятностей не помогает ответить на этот вопрос, поскольку речь идёт о нескольких билетах подряд, а не о случайной выборке билетов.

Для исследования вопроса воспользуемся программой на языке Haskell, которая рассчитает интересующие нас данные методом перебора, и рассмотрим случаи московской и ленинградской систем на шестизначных билетиках.

Определим множество всех билетов:
> bilets = [0..999999]

и функции определения счастливости по московской и ленинградской системе:
> -- сумма цифр на чётных позициях равна сумме цифр на нечётных
> isLuckyL a = 
>     ((a `mod` 10) + ((a `div` 100) `mod` 10) + ((a `div` 10000) `mod` 10)) 
>     == (((a `div` 10) `mod` 10) + ((a `div` 1000) `mod` 10) + ((a `div` 100000) `mod` 10)) 

> -- сумма первых трёх цифр равна сумме последних трёх
> isLuckyM a = 
>     ((a `mod` 10) + ((a `div` 10) `mod` 10) + ((a `div` 100) `mod` 10)) 
>     == (((a `div` 1000) `mod` 10) + ((a `div` 10000) `mod` 10) + ((a `div` 100000) `mod` 10))

Нам нужно определить для каждой последовательности из нескольких билетов подряд, есть ли в ней хотя бы один счастливый. Для этого определим список distances, который будет хранить в себе расстояние от билетика до следующего счастливого.
> distances = map distance tickets
>    where
>    distance ticket = if isLuckyL ticket then 0 else 1 + distance (ticket + 1)

Теперь легко узнать, сколько существует групп из n последовательных билетов, среди которых есть хотя бы один счастливый, применив фильтрацию по расстоянию.
> counts a = show a ++ ": " ++ show (length $ filter (a > ) distances)

Выведем количество таких последовательностей для всех последовательностей длиной от 1 до 1000.
> main = putStrLn $ unlines $ map counts [1..1000]

Применяя в функции distances isLuckyL или isLuckyM, получим данные для ленинградской или московской систем соответственно.

Теперь самое интересное — анализ данных. Построим график зависимости количества счастливых последовательностей билетиков от их длин:



Из графика видно, что ленинградская система на некотором промежутке длин даёт большую вероятность получить счастливый билетик, чем московская. По данным программы, при длинах от 1 до 10 вероятности в обеих системах равны, а при больших длинах ленинградская система выгоднее московской. Так, при 11 билетиках подряд шанс получить счастливый билет по московской системе 506269 из миллиона, по ленинградской — 552511 из миллиона, то есть на 4,6% выше.

Из полученных данных следует, что при езде вдесятером у вас есть неплохие шансы на счастливый билет (49,7%), если конечно, он достанется именно вам. Также, при езде большими группами выгоднее придерживаться ленинградской системы.

P.S. Текст заметки является программой на Literate Haskell.
  • +4
  • unC0Rr
  • 19 декабря 2009, 20:59

Комментарии (19)

  • avatar
  • SPU
  • 19 декабря 2009, 22:03
  • #
  • 0
Сравнение систем разных городов забавно, но вот это:
«Теория вероятностей не помогает ответить на этот вопрос, поскольку речь идёт о нескольких билетах подряд, а не о случайной выборке билетов»
просто «ацкий отжиг».
Какая разница, один билетик или несколько подряд? Меняются всего лишь условия задачи, а теория вероятностей ни куда не девается. Такие задачи как раз на практике по теорверу дают.
Дело в том, что распределение билетиков разное. Как теория вероятностей поможет тебе ответить какой-нибудь формулой на вопрос, каковая вероятность выпадения хотя бы одного счастливого билета при покупке 12 билетов за один раз? Тут на ум ничего кроме прямого подсчёта не приходит.
Про условную вероятность и зависимые события слышали?
Ко всему прочему распределение счастливых билетов вовсе не линейно, поэтому реальная вероятность очень сильно зависит от серии билетов. И считать некую усредненную вероятность вообще бессмысленно.
Конечно, слышал. Вот только они тут совсем не в кассу. Я считаю вероятность того, что попадётся хотя бы один счастливый билет при поездке в автобусе, при условии что номера билетов распределены равномерно, и заранее неизвестно, какой рулончик у кондуктора в руках. Разве эти условия не правомерны?
Говоря про распределение номеров я имел в виду распределение между рулончиками (т.е. что рулонов с номерами, начинающимися на 100, столько же, сколько на 345, и т.п.)
Рулонов да, а вот счастливых билетов в них — нет. Пусть один рулон содержит все билеты с одинаковыми первыми цифрами (для московской системы). Сколько будет счастливых билетов в рулоне 100***? Их по пальцам можно сосчитать, а именно 3 штуки на 1000 билетов. А сколько будет счастливых билетов в рулоне 123***?

Условие, что конкретные номера рулона в руках кондуктора нам не известны весьма правомерны, только тогда стоит говорить о верхней и нижней оценке, а не об абстрактном среднем. Среднее хорошо писать для конкретных серий, что, кстати, довольно разумно, т.к. обычно в одном виде транспорта у всех кондукторов на руках примерно одинаковые серии билетов, а это уже дает некоторые знания «охотнику за билетами».
И всё же. Я захожу вдесятером в автобус, и хочу знать какой шанс у меня на счастливый билет. Всё. Остальные оценки — это уже вероятности при каком-то дополнительном условии (например, при условии, что первые цифры 1, 0 и 0), о чём речь не идёт.
В теории все прекрасно, а на практике толку от этих знаний ноль, т.к. реальная вероятность от «нифига» до «дофига» в зависимости от серии. Останется только бегать по автобусам в надежде на то, что среди близких серий есть более выгодная, либо ждать какое-то время, пока не распродадут «плохие» серии.
Задача то получилась из серии «какова вероятность, что в соседней канаве окажется крокодил, если вы мгновенно оказались в неизвестной точке неизвестной планеты в неизвестное время», только с более благоприятными условиями.

И таки вернемся к началу. При чем же тут теория вероятности? Как не трудно догадаться изначально у нас была одна дискретная случайная величина с равномерным распределением, помухлевав над ней мы получили другую дискретную величину абсолютно того же рода с тем же распределением, но другой вероятностью. И куда же тут исчезла теория? Что изменилось от того, что новая величина зависит от старой через функцию, записанную в виде программки?
Точно так же можно утверждать, что «реальная» вероятность от 0 до 1 в зависимости от счастливости билета.

Про величины, вообще ничего не понял. Что за изначальная величина?
Изначальная — это вероятность вытащить счастливый билет с одной попытки. Вторая величина — это ровно то же самое, определяется тем же номером билета (первого в цепочке), только рассматриваемое пространство будет другим, но абсолютно того же размера (миллион счастливых или не счастливых цепочек).

Геометрически счастливые билеты для московской системы — это просто точки с целочисленными координатами, лежащими в сечении куба [0,9]x[0,9]x[0,9] (младшие разряды) плоскостью x+y+z=C (старшие разряды), где C=[0,1,2,...,27], а цепочки билетов представляются как отрезки внутри куба, которые последовательно заполняют его по принципу штабелей.
Всё это верно, но не вижу, какая же мысль должна дойти до меня. Что с того, что пространство другое? На что должна меня навести геометрическая интерпретация?
На то, что эта фраза «Теория вероятностей не помогает ответить на этот вопрос, поскольку речь идёт о нескольких билетах подряд, а не о случайной выборке билетов.» бредова, с чего я и начинал.
Все, что делалось в программке и вокруг этих билетов и есть теория вероятностей. Аналогия: берем палку, говорим, что она никак не поможет разбить яйцо и тут же ей это яйцо разбиваем.
Имелось в виду, что теория вероятностей в данном случае не может предоставить иной механизм для вычисления вероятности, нежели прямой подсчёт. Говорить при этом о каком либо применении теории вероятностей не приходится, разве что определение вероятности используется.
Для студентов все эти «я имел в виду не то, что имел в виду» обычно плохо заканчиваются на экзаменах ;)
К чему эта демагогия. Я не отказываюсь от своих слов, не меняю их смысл, лишь уточняю, что я имел в виду под словами «теория не помогает».
В чем график делался?
В OpenOffice.org Calc
Я хотел предположить, что тоже на Literate Haskell. А вообще хотелось бы побольше узнать про этот Literate Haskell, на русском языке про него почти ничего нет.
Literate Haskell это тот же самый Haskell, только (в таком стиле, bird-style) строки кода выделены значком >
По этим значкам компилятор отделяет программу от текста и компилирует обычным образом.
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.