Привет, мои дорогие читатели! Недавно была заметка о том, как программно решить задачу с определением счастливого билета:
Давайте сегодня подумаем, а как посчитать или хотя бы оценить количество счастливых билетов при 6-значном номере? Можно ли решить такую задачу аналитически?
Давайте для интереса определим верхнюю границу количества таких билетов? Их явно меньше миллиона, верно? А может есть ещё какое-то число?
Пусть число будет считаться «красивым», если сумма первых трёх цифр даёт тот же остаток при делении на 9, что и сумма следующих трёх цифр. В десятичной системе счисления всякое число даёт тот же остаток при делении на 9, что и сумма его цифр. Это свойство даёт возможность легко найти число «красивых» билетов. Действительно, среди чисел от 1 до 999 ровно 111 дают при делении на 9 остаток 1, столько же остаток 2, и так далее.
Теперь подумаем, сколько чисел от 1 до 999 дают при делении на 9 остаток 1, сколько чисел дают остаток 2, сколько чисел дают остаток 3?...
Среди чисел от 1 до 999 ровно 111 дают при делении на 9 остаток 1, столько же остаток 2, и так далее. Сколько же существует различных «красивых» чисел с остатком 1? На первом месте может стоять 111 чисел и для каждого из них следом можно поставить любое из тех же 111 чисел. Таким образом, получаем 111·111 = 12 321 «красивых» билетов с остатком 1. Такое же число «красивых» билетов дают остатки 2, 3 и так далее. А к числам с остатком 0 или, как мы привыкли говорить, делящимся без остатка, нужно еще прибавить число 000, поэтому их будет не 111, а 112, откуда следует, что «красивых» чисел с остатком 0 будет 112·112 = 12 544. Итак, всего «красивых» чисел будет 8·12 321 + 12 544 = 111 112.
Из доказанного ранее, всякий «счастливый» билет является «красивым». Но не каждый «красивый» билет является «счастливым».
Пример: Билет с номером 100 748 является «красивым», но не будет «счастливым»:
Сумма левая = 1 + 0 + 0 = 1
Сумма правая = 7 + 4 + 8 = 19
100 mod 9 = 1 mod 9 = 1
748 mod 9 = (9⋅ 83 + 1) mod 9 = 1 = 19 mod 9.
Обозначим количество счастливых билетов через S. Тогда S < 111 112. Получена верхняя граница.
Можно дать нижнюю грубую оценку. Назовём «прекрасными» билетами такие, у которых номер состоит из двух совершенно одинаковых половинок, например 287 287. Таких билетов ровно 1000, а именно, 000 000, далее 001 001, 002 002, ... до 999 999. Потому что их столько же, сколько чисел в первой половинке (вторая половинка такая же). «Прекрасных» билетов, естественно, меньше, чем «счастливых», поэтому мы можем записать такую оценку: 1000 < S < 111 112.
Уточнение верхней границы. Москвичи считают билет «счастливым», если сумма цифр, стоящих на чётных местах, равна сумме цифр, стоящих на нечётных местах.
Признак делимости на 11: Сложим все цифры, стоящие в нечётных разрядах, потом отдельно сложим числа, стоящие в чётных разрядах. Так вот, если разность полученных сумм делится на 11, то и всё число делится на 11, и наоборот, любое число, делящееся на 11, обладает этим свойством.
Получается, что «счастливых по-московски» билетов будет не больше, чем чисел от 000 000 до 999 999, делящихся на 11. А это количество этих чисел (1000 000 ) нужно поделить на 11 и прибавить 1, чтобы учесть 000 000. Получим 90 910.
Интересный факт: Количество билетов «счастливых по-московски» равно количество обычных «счастливых» билетов. Доказательство: Расставьте первые три цифры «счастливого» билета на чётные места, последние три цифры на нечётные места, и ты получишь из «счастливого» билета билет, «счастливый по-московски». И обратно, если у билета, «счастливого по-московски», собрать все цифры, стоящие на чётных местах, в первой половине номера, а остальные — во второй, то ты получишь «счастливый» билет. Таким образом, мы установили взаимно однозначное соответствие между теми и другими билетами. А отсюда следует, что их одинаковое количество.
Уточнение даёт нам 1000 < S < 90 910.
Сделаем еще одно уточнение. Какова будет сумма цифр у номера, если в «счастливом» билете заменить три последние цифры на разности между 9 и этими цифрами?
Пример: «Счастливых» билет: 286 358
Сумма левая = 2 + 8 + 6 = 16
Сумма правая = 3 + 5 + 8 = 16
Заменяем три последние цифры:
3 на 9 - 3 = 6
5 на 9 - 5 = 4
8 на 9 - 8 = 1
Сумма цифр: 6 + 4 + 1 = 11
Сумма цифр билета будет: 16 + 11 = 27
Таким образом, счастливых билетов столько же, сколько билетов с суммой цифр 27.
Докажем, что количество счастливых билетов такое же, сколько билетов с суммой цифр 27
Билеты имеют номера от 000 000 до 999 999.
Пусть билет abcdef - счастливый (т.е. a + b + c = d + e + f).
Для него существует билет abc(9-d)(9-e)(9-f), сумма цифр которого:
a + b + c + (9 - d) + (9 - e)+ (9 - f) = (a + b + c) + 27 - ( d + e + f ) = 27.
❓ Сколько существует последовательностей из 6 неотрицательных чисел с суммой 27
Сложно сразу ответить на этот вопрос. Что если рассмотреть 6-значные счастливые билеты с сумой цифр, равно s:
Отсюда видно общая конечная формула, но непонятно как рассчитывать N(s).
В общем же случае счастливых билетов с суммой цифр, равной s в каждой «половинке», будет [N(s)]². Наименьшее возможное значение s равно 0 (для номера 000), а наибольшее — 27 (для номера 999). Просуммировав значения [N(s)]² по s от 0 до 27, мы получим число всех возможных счастливых билетов.
Вопрос: как вычислить N(s) наиболее простым способом?
Обобщим задачу и будем искать Nₖ(s) — количество k-значных билетов с суммой цифр, равной s. В истории математики известно немало задач, решить которые удалось лишь после того, как они были сформулированы в общем виде.
Для начала найдем N₁(s). Нужно определить сколько однозначных чисел имеет сумму цифр s. Для однозначного числа сумма совпадает с самим числом. . Есть одно однозначное число с суммой цифр, равной нулю, — это 0; одно однозначное число с суммой цифр, равной единице, — это 1, одно число с суммой цифр, равной двум, — 2, и т.д. Значит:
Что если мы знаем значение Nₖ₋₁(s) для всех s. Попробуем выразить через эти данные значение Nₖ(s). Другими словами, попробуем найти количество k-значных номеров с суммой цифр, равной s, предполагая, что для (k–1)-значных номеров задача уже решена.
Значение N₁(s) мы уже знаем, тогда остается найти способ перехода от k-1 к k. Тогда получится найти N₂(s), N₃(s), N₄(s) через рекуррентные соотношения.
Пусть первой цифрой k-значного номера является число d. Чтобы сумма цифр этого номера была равна s, остальные его цифры должны в сумме дать s – d. Таких (k–1)-значных номеров существует Nₖ₋₁(s – d). Цифра d может быть любым целым однозначным числом, не превосходящим k (то есть 0≤d≤9, d≤s), и каждой из этих цифр соответствует Nₖ₋₁(s – d) k-значных номеров с суммой цифр, равной s, причём все эти номера различны. Значит, всего таких номеров будет:
По этой формуле можно вычислить N₃(s), а затем просуммировать квадраты этих значение с изменением s: 0 ≤ s ≤ 27. Это можно сделать вручную или может быть с помощью Excel.
❓ upd: Я пробовал с помощью Excel, у меня не получилось, т.к. формула суммы должна как-то хитро работать со смещением. Если кто-то сможет сделать модель в Excel, то обязательно расскажите в комментариях, это интересная задача.
Если немного подумать, то можно сформировать таблицу-матрицу через Python, где первый столбец будет - сумма цифр s, а следующие столбцы - количество k-значных билетов для k = 1, k = 2, k = 3 и так далее. Сумма квадратов элементов столбцов этой матрицы даст количество счастливых билетов (двузначных, четырехзначных, шестизначных, восьмизначных и так далее).
👨🏻💻 Прикрепляю реализацию на Python
🔧Результаты запуска программы
В этой статье я доработал, уточнил и расписал подробно идею определение счастливых билетов, описанную в одном из выпусков журнала Квант.
⏳ Более простой способ - БРУТФОРС - простой перебор всех билетов
Мы уже разбирали функцию, которая может помочь при определении счастливого билета в этой статье. Используем эту функцию в брутфорсе, перебрав все билеты от 000 000 до 999 999. Получится следующее:
Метод перебора считается стрельбой из пушки по воробьям. При переборе получается решение одной конкретной задачи. Это решение не позволяет произвести обобщения и вскрыть какие-нибудь неизвестные ранее закономерности. Поэтому в математике методы перебора неинтересны. Но они полезны, когда не получается решить аналитически. Или нужно проверить решение, в котором мы не уверены.
Понравилась статья? Дайте обратную связь в комментариях. Напишите ваше мнение, идеи, мысли 😉
Если Вам нужен репетитор по физике, математике или информатике/программированию, Вы можете написать мне или в мою группу Репетитор IT mentor в VK
Библиотека с книгами для физиков, математиков и программистов
Репетитор IT mentor в VK
Репетитор IT mentor в telegram
