Счастливобилетчикам — по носу математикой
Искать счастье бесполезно, главное — где оно найдет тебя. Некоторые, в том числе и я, заимел привычку проверять маршрутные проездные билеты на предмет этого «счастья» — билет можно назвать «счастливым», если сумма его первых трех цифр равняется сумме трех остальных. Забавное такое, знаете ли, занятие.
Но иногда бывает так, что счастливые билеты попадаются очень часто, а иногда — их не бывает и несколько месяцев. Это если ездить один раз в день по какому-нибудь маршруту.
И тут приходит замечательный вопрос: «сколько всего существует счастливых билетов?», а еще лучше, когда приходит математика с ее не менее красивым вопросом: «какова вероятность покупки счастливого билета?»
Для человека, который постиг азы программирования, не составит большого труда написать программу для подсчета этого самого количества счастливых билетов — обычным методом перебора. Что сделал и я, получив результат — 55 251 билет, который говорит, что примерно каждый восемнадцатый билет будет счастливым.
Но теперь представьте себе образ кондуктора — человека-сумка-через шею, с несколькими килограммами мелочи и катушкой билетов, которые он выдает последовательно за определенную плату. И что будет, если вы станете счастливым обладателем билета с номером «010100»? Правильно, счастливобилетчиков на этом маршруте не будет, пока кондуктор не покончит с этой катушкой.
Теперь попробуем ответить на этот вопрос математически.
Максимально возможно счастливый билет «999999» имеет сумму триад равную 27 = 9+9+9 = 9+9+9. Билетов с суммой счастливых цифр равной 1 будет 9, это билеты:
Билетов с суммой счастливых цифр равной 3 будет 36. Можете посчитать сами — любым методом. Составим таблицу для каждой такой комбинации:
Получается, что максимальное количество счастливых билетов будет в группах, сумма триад которых равняется 13 или 14.
В таких катушках каждый девятый билет будет счастливым, пока сумма двух цифр одной триады не превзойдет значения 13…14. Следовательно, можно логически предположить, что каждый 18 билет в такой группе будет счастливым. А ввиду такого «классического» распределения, то и во всей группе билетов от 000001 до 999999.
Осталось вспомнить один из методов теории вероятностей, и посчитать:
Получая результат с хорошей точностью, с отклонением ≈ 3%.
А еще, счастливые билеты нужно съедать, чтобы ощутить этот прилив вселенского счастья.
Сколько счастливых билетов в 999999
Задания Д19 C7 № 505983 
Автобусные билеты имеют номера от 000000 до 999999. Билет называется счастливым, если сумма первых трех цифр его номера равна сумме последних трех его цифр. Докажите, что:
а) число всех счастливых билетов четно;
б) сумма номеров всех счастливых билетов делится на 999.
а) Каждому счастливому билету поставим в соответствие билет, номер которого состоит из цифр, дополняющих соответствующие цифры номера исходного билета до девятки. Например, билет 239601 получит в пару билет 760398. Очевидно, парой к каждому счастливому билету является также счастливый билет. При этом никакой билет не получает в пару себя (цифра не может дополнять до девятки самое себя, поскольку 9 — нечетное число). Таким образом, мы получили разбиение всех счастливых билетов на пары.
б) Рассмотрим способ разбиения билетов на пары из пункта а). Сумма номеров билетов в каждой паре равна 999999 = 999 · 1001, значит, она делится на 999. Сложив эти попарные суммы, получим число, кратное 999.
Задача о счастливых билетах
Задача о счастливых билетах — условное название комбинаторной задачи подсчета количества последовательностей цифр длины 6, начиная с 000000 и до 999999, у которых сумма первых трех цифр равна сумме трех последних. Система счисления при этом предполагается десятичной, то есть цифры берутся от 0 до 9. Название задачи происходит от используемого в некоторых течениях городской культуры в СССР и России термина «счастливый билет» в отношении билетов общественного транспорта с суммой первых трех цифр равной сумме трех последних цифр или аналогичными свойствами. Задача может быть решена перебором, существуют и явные формулы ее решения. Возможное обобщение задачи — решать ее при четном числе цифр 2n и в m-ичной системе счисления (m, n — натуральные числа), то есть вычислять количество последовательностей цифр длины 2n, у которых сумма первых n цифр равняется сумме n последних цифр, а сами цифры берутся от 0 до m. Разбиралась в нескольких публикациях в журнале «Квант» в 1970-х и 1980-х годах, согласно С. К. Ландо предлагалась А. А. Кирилловым на своем семинаре в МГУ в 1970-е годы.
Содержание
[править] Явные формулы решения
Методом производящих функций в книге С. К. Ландо «Производящие функции» выводится следующая формула для числа 6-значных счастливых билетов в десятичной системе счисления.
Обозначим многочлен [math]A_1(s) = 1 + s + s^2 + . + s^9[/math] . Он обладает свойством, что коэффициент при [math]s^n[/math] равен числу однозначных чисел, сумма цифр которых равна [math]n[/math] . Отсюда следует, что коэффициент при [math]s^n[/math] в многочлене [math]A_3(s) = (A_1(s))^3[/math] равен числу представлений числа [math]n[/math] в виде суммы трех цифр (принимающих значения от 0 до 9). Поэтому число счастливых 6-значных билетов в десятичной системе счисления равно сумме квадратов коэффициентов многочлена [math]A_3(s)[/math] , что дает более простой по сравнению с полным перебором способ вычисления числа счастливых билетов.
Этот результат можно привести к явным формулам, использующим интеграл от тригонометрических функций, приписываемых в книге С. Ландо математику В. Дринфельду, который получил их будучи десятиклассником. В публикациях журнала «Квант» говорится, что формулы в виде интегралов прислали в журнал читатели.
Из предыдущего результата следует, что число счастливых билетов равно свободному члену (коэффициенту [math]p_0[/math] при члене [math]s_0[/math] ) многочлена Лорана [math]A_3(s)A_3\left(\frac<1>\right)[/math] . Отсюда с помощью этого многочлена Лорана и примененной к нему теоремы Коши о вычетах выводится, что число счастливых билетов равно:
[math]p_0 = \frac<1> <\pi>\int\limits_0^ <\pi>\left ( \frac<\sin 10 x ><\sin
Аналогично выводится общая формула для нахождения количества [math]2n[/math] -значных счастливых билетов в [math]m[/math] -ичной системе счисления:
Также число счастливых билетов совпадает с числом целых точек, лежащих строго внутри [math]2n[/math] -мерного куба [math][0, m+1]^<2n>[/math] на проходящей через его центр гиперплоскости, перпендикулярной главной диагонали, которое называется числом Петровского (в честь академика И. Г. Петровского).
[править] Решение методом включения-исключения
Рассмотрим конечное множество [math]B[/math] , элементы которого обладают некоторыми из свойств [math]c_1, . c_r[/math] . Обозначим [math]N(c_i)[/math] — число элементов множества [math]B[/math] , обладающих свойством [math]c_i[/math] , через [math]N(c_i,c_j)[/math] — число элементов множества [math]B[/math] , обладающих свойствами [math]c_i[/math] и [math]c_j[/math] ( [math]i \ne j[/math] ) и т. д. Пусть [math]|B|[/math] — общее число элементов множества [math]B[/math] .
При этих обозначениях число элементов множества [math]B[/math] , для которых не выполнено ни одно из свойств [math]c_i[/math] ( [math]i = 1, …, r[/math] ) равно (принцип включения-исключения):
[math]|B| — N(c_1) - … — N(c_r) + N(c_1, c_2) + … - N(c_1, c_2, c_2) - …[/math]
Число 10-ичных шестизначных счастливых билетов равно числу билетов с суммой цифр, равной 27 (это следует из того, что каждому счастливому билету с десятичной записью [math]a_1b_1c_1a_2b_2c_2[/math] можно взаимно-однозначно сопоставить билет с десятичной записью [math]a_1b_1c_1(9-a_2)(9-b_2)(9-c_2)[/math] , который имеет сумму цифр 27. Введем множество [math]B[/math] всех расстановок неотрицательных целых чисел с суммой 27 в шести позициях, а также определим 6 свойств [math]c_1, . c_6,[/math] где свойство [math]c_i[/math] обозначает, что число в [math]i[/math] -й позиции не меньше 10. Число способов расставить [math]p[/math] неотрицательных целых чисел с суммой [math]q[/math] выражается через число сочетаний и равно [math]C^
Таким образом, по принципу включения-исключения число 6-значных 10-ичных счастливых билетов равно
[math]C_<32>^5 — 6C_<22>^5+15C_<12>^5 = 55252.[/math]
Аналогично выполняется общая формула для нахождения количества [math]2n[/math] -значных счастливых билетов в [math]m[/math] -ичной системе счисления, которое равно числу билетов с суммой цифр [math]n(m–1)[/math] :
Ее также можно вывести с помощью производящих функций.
[править] Рекуррентное соотношение
Обозначим через [math]N_n(k)[/math] количество [math]n[/math] -значных [math]m[/math] -ичных чисел ( [math]n=1, 2, 3, . [/math] ), сумма цифр каждого из которых равна [math]k[/math] . В частности, [math]N_n(k) = 0[/math] при [math]k\lt0[/math] и [math]k\gt(m-1)n.[/math] Очевидно, [math]N_n(0) = 1[/math] .
Поскольку [math]n[/math] -значное число с суммой цифр [math]k[/math] получается из [math](n–1)[/math] -значного числа с суммой цифр [math]l[/math] (где [math]k–(m-1)≤l≤k[/math] ) путем добавления цифры [math]k–l[/math] , то:
Отсюда получается рекуррентное соотношение, с помощью которого можно последовательно вычислять числа [math]N_n(k)[/math] :
[math]N_n(k + 1) – N_n(k) = N_
Имеем, что число счастливых [math]2n[/math] -значных [math]m[/math] -ичных билетов [math]C_ <2n,m>= N_<2n>((m-1)n),[/math] так как оно равно числу билетов с суммой цифр [math]n(m–1).[/math]
С помощью данного рекуррентного соотношения можно дать элементарное (не использующее теорию функций комплексного переменного) доказательство формулы для числа счастливых билетов в виде интеграла.
[править] Литература
- Ландо С. К. Лекции о производящих функциях — М.: МЦНМО, 2004. ISBN 5-94057-042-9
[править] Ссылки
Персональные инструменты
Пространства имён
- Статья
- Обсуждение
Варианты
Просмотры
- Читать
- Правка
- История
Действия
Поиск
Навигация
Инструменты
- Последнее изменение этой страницы: 17:24, 6 ноября 2021.
- К этой странице обращались 18 375 раз.
Текст страницы доступен по условиям лицензии GNU Free Documentation License. Материалы могут быть скопированы при условии указания активной ссылки на источник копирования в теле статьи (на той же странице). В отдельных случаях могут действовать условия лицензии Creative Commons Attribution-ShareAlike (CC BY-SA 3.0), информацию об этом можно просмотреть на странице обсуждения или в истории правок. В частности, условия лицензии CC BY-SA 3.0 действуют в отношении статей, перенесенных из Википедии (указание на факт переноса всегда есть в истории правок статьи или на ее странице обсуждения).
В текстах упоминаются организации, признанные на территории Российской Федерации террористическими и/или в отношении которых судом принято вступившее в законную силу решение о запрете деятельности. В том числе:
Признаны террористическими организациями: «Исламское государство» (другие названия: «Исламское Государство Ирака и Сирии», «Исламское Государство Ирака и Леванта», «Исламское Государство Ирака и Шама»), «Высший военный Маджлисуль Шура Объединенных сил моджахедов Кавказа», «Конгресс народов Ичкерии и Дагестана», «База» («Аль-Каида»), «Братья-мусульмане» («Аль-Ихван аль-Муслимун»), «Движение Талибан», «Имарат Кавказ» («Кавказский Эмират»), Джебхат ан-Нусра (Фронт победы) (другие названия: «Джабха аль-Нусра ли-Ахль аш-Шам» (Фронт поддержки Великой Сирии), Всероссийское общественное движение «Народное ополчение имени К. Минина и Д. Пожарского», Международное религиозное объединение «АУМ Синрике» (AumShinrikyo, AUM, Aleph) — см. полный список.
Деятельность запрещена по решению суда: Межрегиональная общественная организация «Национал-большевистская партия», Межрегиональная общественная организация «Движение против нелегальной иммиграции», Украинская организация «Правый сектор», Украинская организация «Украинская национальная ассамблея — Украинская народная самооборона» (УНА — УНСО), Украинская организация «Украинская повстанческая армия» (УПА), Украинская организация «Тризуб им. Степана Бандеры», Украинская организация «Братство», Межрегиональное общественное объединение — организация «Народная Социальная Инициатива» (другие названия: «Народная Социалистическая Инициатива», «Национальная Социальная Инициатива», «Национальная Социалистическая Инициатива»), Межрегиональное общественное объединение «Этнополитическое объединение „Русские“», Общероссийская политическая партия «ВОЛЯ», Общественное объединение «Меджлис крымскотатарского народа», Религиозная организация «Управленческий центр Свидетелей Иеговы в России» и входящие в ее структуру местные религиозные организации, Межрегиональное общественное движение «Артподготовка» — см. полный список.