LiveStreet

Про счастливые билеты написано довольно много: оценка количества таких билетов, общая формула для 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.