Счастливобилетчикам — по носу математикой
Искать счастье бесполезно, главное — где оно найдет тебя. Некоторые, в том числе и я, заимел привычку проверять маршрутные проездные билеты на предмет этого «счастья» — билет можно назвать «счастливым», если сумма его первых трех цифр равняется сумме трех остальных. Забавное такое, знаете ли, занятие.
Но иногда бывает так, что счастливые билеты попадаются очень часто, а иногда — их не бывает и несколько месяцев. Это если ездить один раз в день по какому-нибудь маршруту.
И тут приходит замечательный вопрос: «сколько всего существует счастливых билетов?», а еще лучше, когда приходит математика с ее не менее красивым вопросом: «какова вероятность покупки счастливого билета?»
Для человека, который постиг азы программирования, не составит большого труда написать программу для подсчета этого самого количества счастливых билетов — обычным методом перебора. Что сделал и я, получив результат — 55 251 билет, который говорит, что примерно каждый восемнадцатый билет будет счастливым.
Но теперь представьте себе образ кондуктора — человека-сумка-через шею, с несколькими килограммами мелочи и катушкой билетов, которые он выдает последовательно за определенную плату. И что будет, если вы станете счастливым обладателем билета с номером «010100»? Правильно, счастливобилетчиков на этом маршруте не будет, пока кондуктор не покончит с этой катушкой.
Теперь попробуем ответить на этот вопрос математически.
Максимально возможно счастливый билет «999999» имеет сумму триад равную 27 = 9+9+9 = 9+9+9. Билетов с суммой счастливых цифр равной 1 будет 9, это билеты:
Билетов с суммой счастливых цифр равной 3 будет 36. Можете посчитать сами — любым методом. Составим таблицу для каждой такой комбинации:
Получается, что максимальное количество счастливых билетов будет в группах, сумма триад которых равняется 13 или 14.
В таких катушках каждый девятый билет будет счастливым, пока сумма двух цифр одной триады не превзойдет значения 13…14. Следовательно, можно логически предположить, что каждый 18 билет в такой группе будет счастливым. А ввиду такого «классического» распределения, то и во всей группе билетов от 000001 до 999999.
Осталось вспомнить один из методов теории вероятностей, и посчитать:
Получая результат с хорошей точностью, с отклонением ≈ 3%.
А еще, счастливые билеты нужно съедать, чтобы ощутить этот прилив вселенского счастья.
Из номеров 000 001 . 999 999 нужно найти все счастливые билеты (как сделать с помощью разбивания на масив char ) [закрыт]
Вопросы с просьбами помочь с отладкой («почему этот код не работает?») должны включать желаемое поведение, конкретную проблему или ошибку и минимальный код для её воспроизведения прямо в вопросе. Вопросы без явного описания проблемы бесполезны для остальных посетителей. См. Как создать минимальный, самодостаточный и воспроизводимый пример.
Закрыт 7 лет назад .
Можно меньше итераций делать.
Сумм мало: от 1 до 18. Достаточно пробежать от 1 до 999 и сохранять очередное число в массив, в зависимости от суммы его цифр. Каждой сумме соответствует массив тех чисел, из которых она получается.
Напр. для суммы 1 это будет массив из 1, 10 и 100.
Далее остаётся составить все возможные пары из каждого массива:
Так не будет «холостых» вариантов в циклах. У меня получился 55251 счастливый билет. 999+55251=56250 итераций вместо 999999. А вероятность получить счастливый билет, выходит, чуть больше 1/20.
Задача о счастливых билетах
Задача о счастливых билетах — условное название комбинаторной задачи подсчета количества последовательностей цифр длины 6, начиная с 000000 и до 999999, у которых сумма первых трех цифр равна сумме трех последних. Система счисления при этом предполагается десятичной, то есть цифры берутся от 0 до 9. Название задачи происходит от используемого в некоторых течениях городской культуры в СССР и России термина «счастливый билет» в отношении билетов общественного транспорта с суммой первых трех цифр равной сумме трех последних цифр или аналогичными свойствами. Задача может быть решена перебором, существуют и явные формулы ее решения. Возможное обобщение задачи — решать ее при четном числе цифр 2n и в m-ичной системе счисления (m, n — натуральные числа), то есть вычислять количество последовательностей цифр длины 2n, у которых сумма первых n цифр равняется сумме n последних цифр, а сами цифры берутся от 0 до m. Разбиралась в нескольких публикациях в журнале «Квант» в 1970-х и 1980-х годах, согласно С. К. Ландо предлагалась А. А. Кирилловым на своем семинаре в МГУ в 1970-е годы.
Содержание
Явные формулы решения [ править ]
Методом производящих функций в книге С. К. Ландо «Производящие функции» выводится следующая формула для числа 6-значных счастливых билетов в десятичной системе счисления.
Этот результат можно привести к явным формулам, использующим интеграл от тригонометрических функций, приписываемых в книге С. Ландо математику В. Дринфельду, который получил их будучи десятиклассником. В публикациях журнала «Квант» говорится, что формулы в виде интегралов прислали в журнал читатели.
Решение методом включения-исключения [ править ]
Таким образом, по принципу включения-исключения число 6-значных 10-ичных счастливых билетов равно
Ее также можно вывести с помощью производящих функций.
Рекуррентное соотношение [ править ]
Отсюда получается рекуррентное соотношение, с помощью которого можно последовательно вычислять числа N n ( k ) <\displaystyle N_
С помощью данного рекуррентного соотношения можно дать элементарное (не использующее теорию функций комплексного переменного) доказательство формулы для числа счастливых билетов в виде интеграла.
Сколько счастливых билетов в 999999
Счастье за деньги не купишь, гласит народная мудрость. Зато можно, хоть и случайно, купить счастливый билетик. Мы воспринимаем это событие как удачу, потому что оцениваем его вероятность как низкую. Но так ли уж редко это происходит на самом деле?
Эта статья была опубликована в журнале OYLA №9(37). Оформить подписку на печатную и онлайн-версию можно здесь.
Сперва проясним, что такое счастливый билет. Любой билет, в кино или на поезд, имеет уникальный номер. Как правило, его присваивают последовательно начиная с 0 и до некоторого значения. Делается это для удобства учёта. Мы будем рассматривать билеты, у которых номер состоит из 6 цифр: от 000000 до 999999. Определений счастливого билета несколько, но мы остановимся на наиболее популярном: билет называется счастливым, если сумма первых трёх цифр его номера равна сумме последних трёх цифр. Прежде чем начать охоту за билетами, давайте ответим на частые вопросы, с ними связанные. В этом нам поможет математика.
Переведём этот вопрос на формальный язык математики: существует ли такой счастливый билет ABCDEF, что ABCDEF + 1 тоже будет счастливым? Иначе говоря, для этих чисел должно выполняться равенство:
A + B + C = D + E + F
A + B + C = D + E + F + 1
Если первое из шестизначных чисел оканчивается не на 9 (F9), то при прибавлении единицы сумма последних трёх цифр изменится, а первых трёх нет, значит, билет перестанет быть счастливым. Если же на конце было 9 (F = 9), то сумма последних трёх цифр уменьшится (если на конце более трёх девяток, то уменьшится и сумма первых трёх, но не настолько). Итак, счастливые билеты подряд не идут. Но, с другой стороны, подряд они могут идти через девятку: например, 100001 и 100010. Более того, иногда цепочка «через девять» бывает весьма длинной: 900009, 900018, 900027, …, 900090. Это если нам повезло с началом. А если начало — 998999? Тогда ближайший счастливый билет будет аж через тысячу! Действительно, дальше все билеты будут начинаться с 999, так что на конце для счастья тоже надо иметь 999…
Для начала попробуем приблизительно оценить их количество. Несложная оценка снизу: нам подходят все билеты вида АВСАВС. Сколько таких билетов? А столько же, сколько всего комбинаций первых трёх цифр — 1000. Так что счастливых билетов точно не меньше 1000. Неплохо, но мы не учли кучу вариантов, когда цифры разные — например, те же 900018. Можно попытаться учесть перестановки цифр АВС, то есть билеты вида АВСВСА, АВСАСВ и т. д. Но, увы, просто умножить на 6 (количество возможных перестановок цифр А, В и С) не получится: если среди них есть совпадающие цифры, то мы имеем уже не 6 вариантов, а 3 или 1.
Впрочем, эту идею можно реализовать по-другому. Рассмотрим все комбинации следующего вида: на первых трёх местах стоят цифры А, В и С, на вторых трёх — те же цифры, но в произвольном порядке. Сколько же таких вариантов набежит? На первом месте может стоять любая из 10 цифр, то есть пока 10 вариантов. Для любой первой цифры есть 9 вариантов второй, значит, их уже 90. Для каждого из этих 90 существует 8 вариантов третьей цифры — всего, стало быть, 720. И теперь нам осталось умножить 720 на количество способов переставить три фиксированные различные цифры по оставшимся трём местам. Как мы уже поняли, таких вариантов 6, значит, общее количество чисел — 4320. Однако и это оценка снизу, причём «сильно снизу»: мы всё ещё не учитываем варианты с разными цифрами.
Хорошо, попробуем теперь оценить искомую сумму сверху. Заметим, что, если каждый счастливый билет ABCDEF заменить на билет ADBECF, количество не изменится, значит, можно просто посчитать количество шестизначных чисел, у которых сумма цифр на чётных местах равна сумме на нечётных. А это очень похоже на признак делимости на 11! Напомним, если в числе разность между суммой цифр на чётных и нечётных местах делится на 11, то и число делится на 11. Значит, все наши счастливые билеты «второго типа» делятся на 11, а тогда их не больше, чем чисел, делящихся на 11, то есть 90909 (1000000 : 11). Получается, что счастливых билетов не больше 90909. Впрочем, это также очень грубая оценка, ведь вовсе не каждое число, делящееся на 11, имеет равные суммы цифр на чётных и нечётных местах — например, 000506. Так что счастливых билетов существенно меньше. Давайте же точно подсчитаем, сколько их!
Чтобы посчитать точное количество, заменим каждую из трёх последних цифр на дополняющую её до 9. D заменим на K = (9 – D), E на M = (9 – E), F на N = (9 – F). Так как исходно A + B + C = D + E + F, то теперь для числа ABCKMN:
A + B + C + K + M + N
A + B + C + 9 – D + 9 –E + 9 – F
Итак, количество счастливых билетов в точности равно количеству чисел от 000000 до 999999, сумма цифр которых равна 27. Стало немного легче, но предстоит ещё немало работы. Сперва вычислим искомое количество. Для этого нарисуем таблицу, в которой по горизонтали укажем количество используемых цифр, а по вертикали — искомую сумму. Таким образом мы последовательно ответим на все вопросы вида «Сколько существует способов представить число k в виде суммы n цифр». Делать это мы будем рекурсивно, то есть выражать большие значения через меньшие. Поехали!
Очевидно, что в первом столбце у нас будет по одному способу получить числа от 0 до 9 (с помощью одной цифры), а всё, что больше 9, — 0 способов.
Далее, если перейти ко второму столбцу и взять, допустим, число на пересечении второго столбца и шестой строки (k = 5), сколько существует способов представить 5 в виде суммы двух цифр? Логика тут простая. В качестве второй цифры мы можем выбрать любой из вариантов от 0 до 5. Если выбираем 0, то сумма всех цифр, кроме второй, должна быть равна 5 (да-да, понятно, что в данном случае «всех, кроме второй» — это только первая цифра, но давайте сразу составим алгоритм в общем виде). Если выбираем в качестве второй цифры 1, то сумма оставшихся должна быть равна 4 и т. д. Но ведь тогда мы просто должны сложить способы из предыдущего столбца — для всех чисел от 0 до 5! И получить 6 вариантов.
Ещё пример: допустим, я хочу заполнить во втором столбце поле для k = 11. Несложно увидеть, что тогда вторая цифра 0 или 1 не даёт ни одного варианта, так как первая не может быть больше 9. Иначе говоря, мы обращаемся к пустым ячейкам первого столбца, которые соответствуют k = 10 и k = 11. Впрочем, можно считать, что там не пустота, а нули — это не важно. Так или иначе, мы должны сложить все варианты из предыдущего столбца, от k = 2 до k = 11. Это даёт 8. Таким же образом заполняем второй столбец. Последнее число мы впишем при k = 18, так как максимальная сумма двух цифр равна 18.
Переходим к третьему столбцу. Давайте ещё раз посмотрим на примере, как он заполняется. Допустим, k = 15. Тогда, поскольку последняя цифра может быть от 0 до 9, сумма первых двух должна быть равна 6, 7, 8, 9, …, 15. А для всех этих чисел мы уже знаем количество способов представить их в виде суммы двух цифр. Берём эти значения из таблички (это числа 7, 8, 9, 10, 9, 8, 7, 6, 5 и 4), складываем их и получаем результат: 73 способа представить 15 в виде суммы трёх цифр.
Действуя аналогично, продолжаем заполнять табличку. Занятие это весьма муторное, но конечное. Особенно если написать программу. Но можно сделать всё и руками — главное, нигде не обсчитаться. И если довести таблицу до шестого столбца, число, соответствующее k = 27, и будет искомым ответом. Если вы не ошибётесь, то получите ровно 55 252.
Альтернативный подход
Прежде чем делать выводы, попробуем подсчитать количество счастливых билетов другим способом. Например, так: ограничимся в предыдущем решении первыми тремя столбцами. В третьем мы получили количество способов представить число k в виде суммы трёх цифр — мы сделали это для любого k от 0 до 27. Теперь забудем наши соображения о девятках (про замену цифр на дополняющие до 9) и рассмотрим произвольный счастливый билет ABCDEF. Пусть A + B + C = k. Сколько есть способов подобрать такие А, В и С? Это мы знаем из таблички — допустим, D3(k).
А сколько способов подобрать вторые три цифры? Да столько же, ведь речь всё о тех же вариантах представить число k как сумму трёх слагаемых! Стало быть, так как нас устраивают любые комбинации, общее количество способов подобрать счастливый билетик, у которого сумма первых трёх цифр равна k, будет (D3k2). Следовательно, всё, что осталось сделать, — это взять числа из третьего столбца (1, 3, 6, 10, …, 1), каждое из них возвести в квадрат и полученные квадраты сложить. Если всё это проделать, получится то же число 55 252.
Да, есть и более короткая комбинаторная формула, но вывести её гораздо сложнее. Не будем приводить полное рассуждение — лишь обозначим идею и выпишем окончательную формулу. Идея в следующем: вернёмся к тому, что нам надо посчитать количество способов представить 27 как сумму 6 цифр. Сделаем это так: возьмём 27 яблок и поставим среди них 5 перегородок. Тогда количество яблок до первой перегородки будет первым слагаемым суммы, от первой перегородки до второй — вторым слагаемым и т. д. Обратите внимание, что перегородки могут стоять подряд, и в этом случае слагаемое окажется равным нулю. Значит, задача сводится к подсчёту количества способов расставить перегородки. Но заметим, что всего у нас получилось 32 объекта (27 яблок и 5 перегородок) и мы должны выбрать местоположение для 5 перегородок (на остальные места встанут яблоки). Сколько же существует способов выбрать 5 мест из 32? C32, если вы знакомы с комбинаторикой (впрочем, если не знакомы — столько же).
Проблема в том, что это ещё не ответ. Мы посчитали количество способов представить 27 в виде суммы 6 слагаемых, но пока не учли, что ни одно слагаемое не должно быть больше 9. Если же учесть это, итоговая формула будет такой:
Это число посчитать гораздо проще, и мы тоже получим 55 252 — можете убедиться сами.
Итак, что же мы получили? Мы вычислили, что примерно 5,5% билетов являются счастливыми, — иначе говоря, в среднем каждый восемнадцатый. Не так уж и редко, оказывается!
А вот оправдается ли статистика на практике, проверяйте сами. И помните, что если съесть такой билетик раньше времени, то кроме отравления можно заработать ещё и немаленький штраф от контролёра, что мало соответствует представлениям большинства о счастье. Зато счастье от решения непростой задачи у нас никто не отнимет. До новых счастливых встреч!