Falcão (falcao) wrote,
Falcão
falcao

  • Mood:
  • Music:

счастливые билеты

Этот пост написан по просьбе crazy_flyer. Речь пойдёт о хорошо известной задаче: как подсчитать число счастливых билетов? Причём сделать это нужно по возможности не очень длинно, избегая слишком сложных вычислений. Тот способ, который я предлагаю, приводится под "катом".

Я не ставлю своей целью написать текст как можно короче. Наоборот: я исхожу из того, что лучше произнести какие-то дополнительные слова, лишь бы в итоге было понятно не только то, какой в задаче ответ, но и то, откуда он взялся. Тексты такого рода рекомендуется читать в "пошаговом" режиме, то есть просто улавливать и усваивать то, что написано. При этом желательно свой собственный "творческий" аппарат на время чтения отключить.

Итак всего, рассмотрим какой-нибудь счастливый билет abcdef. По определению, сумма первых трёх цифр равна сумме трёх последних, то есть a+b+c=d+e+f. Обозначим эту сумму через k и будем называть для краткости рангом счастливого билета. Например, 191731 -- это счастливый билет ранга 11.

Ясно, что ранг счастливого билета может принимать значения от 0 до 27 включительно. Поэтому общее число S счастливых билетов, которое мы хотим найти, будет представлять собой сумму S(0)+S(1)+S(2)+...+S(27), где через S(k) мы обозначили число счастливых билетов ранга k.

Таким образом, задача будет решена, если мы найдём 28 слагаемых нашей суммы. Это довольно много. Но заметим, что нам достаточно найти лишь половину этих значений, потому что остальные будут повторяться. А именно: если взять какой-то счастливый билет ранга k и заменить в нём каждую цифру на дополнительную до 9, то получится счастливый билет ранга 27-k. Например, билет 191731 ранга 11 превратится в билет 808268 ранга 16.

Отсюда следует, что S(k)=S(27-k), то есть набор слагаемых нашей суммы одинаково читается слева направо и справа налево. В середине будут стоять равные друг другу слагаемые S(13) и S(14). Поэтому мы приходим к такой формуле:

S = 2*(S(0)+S(1)+S(2)+...+S(13)),

то есть найти нужно всего 14 чисел. Это пока что всё равно много, но далее окажется, что способ нахождения первых 10 слагаемых очень простой, и все они находятся однотипно. А последние 4 мы найдём, зная предыдущие, применяя некоторую поправку.

Итак, пусть k есть ранг билета; как найти число S(k)? Выбирая один из таких билетов, мы сначала выбираем тройку цифр с суммой k. Сколькими способами это можно сделать? Пока мы этого не знаем, поэтому обозначим это число через T(k). Например, T(0)=1 -- для единственной тройки 000 с суммой 0, а T(1)=3 -- здесь имеются в точности три тройки: 001, 010, 100 с суммой 1.

Утверждается, что S(k)=T(k)*T(k)=T(k)^2. В самом деле, выписывая номер счастливого билета ранга k, мы можем сделать это в два этапа: выписать сначала первую тройку, а потом вторую. При поэтапном выборе число способов перемножается, что и приводит к выписанному выше равенству.

Итак, мы приходим к формуле

S = 2*(T(0)^2+T(1)^1+T(2)^2+...+T(13)^2),

то есть ответом в задаче будет удвоенная сумма квадратов 14 чисел, которые мы сейчас найдём.

Итак, что такое T(k)? Это число решений уравнения a+b+c=k в целых неотрицательных числах, но ещё с дополнительным ограничением, что a,b,c -- это цифры, то есть никакая из них не может превышать 9. Забудем сначала про имеющееся ограничение и подсчитаем просто число решений этого уравнения. Дело в том, что при k=0,1,...,9 у нас автоматически будет выполнено наше ограничение, и в итоге мы найдём 10 из 14 интересующих нас чисел.

Итак, сколько же решений имеет уравнение a+b+c=k? Прежде всего, введём для этого количества обозначение U(k). Понятно, что третья переменная c может принимать значения от 0 до k. Зафиксируем одно из таких значений; тогда a+b=k-c. Сколько решений имеет такое уравнение, уже от двух переменных?

Здесь ответ очевиден. Представим себе в правой части какое-то конкретное число, например, 8. Все решения уравнения a+b=8 могут быть явно выписаны: это (0,8), (1,7), (2,6), ..., (8,0). Посмотрим на первые числа в парах и увидим, что решений ровно 9, то есть на единицу больше того, что стояло в правой части уравнения. Этот принцип просто запомнить. Скажем, уравнение a+b=4 будет иметт 5 решений.

Вернёмся к уравнению a+b+c=k. Уже говорилось, что c принимает значения от 0 до k. Для удобства начнём с максимального из значений, равного k. При этом возникает уравнение a+b=0, имеющее одно решение. При c=k-1 получается a+b=1, и здесь решений уже два. Далее при c=k-1 имеем a+b=2 с тремя решениями, и так вплоть до последнего случая c=0, где приходим к уравнению a+b=k, имеющему k+1 решение. Окончательно мы получаем следующее:

число решений уравнения a+b+c=k в целых неотрицательных числах в точности равно U(k)=1+2+3+...+k+(k+1), то есть сумме первых k+1 чисел натурального ряда.

В данном случае можно воспользоваться известной формулой и "свернуть" формулу до U(k)=(k+1)*(k+2)/2, но здесь это не обязательно. Дело в том, что нам нужен список всех чисел вида T(k) при k=0,1,2,...,13. И, как говорилось выше, первые 10 чисел этого списка могут быть найдены по вышеприведённой формуле. Напомним, что при k=0,1,...,9 решениями уравнения автоматически будут тройки цифр, то есть то, что мы хотим подсчитать. А вот при k=10 и далее, уравнения будут иметь решения типа (10,0,0), которые нам не подходят.

Итак, вот список из 14 чисел вида U(k), где k=0,1,2,...,13:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105

который строится по такому принципу: начиная с 1, мы далее прибавляем последовательно 2, 3, ..., 13. Здесь первые 10 чисел выделены жирным шрифтом; их мы уже нашли верно. А для последних четырёх чисел мы сейчас сделаем поправку, удалив "лишнее".

Итак, рассмотрим число k от 10 до 13. Нас интересует число T(k), то есть число решений уравнения a+b+c=k в десятичных цифрах. Мы же нашли число решений, среди которых есть лишние. Это в точности те решения, где одна из цифр принимает значение 10 и более. Заметим, что такая цифра может быть в точности одна -- ведь в противном случае суммы всех цифр была бы как минимум 20, а у нас это не так. Сколько мы насчитали лишних решений, если значение a вышло за пределы, то есть стало равно 10+α? Подстановка в уравнение даёт α+b+c=k-10, то есть нами было учтено U(k-10) лишних решений, где a выходило за отведённые пределы. Но ровно столько же их было, когда за пределы вышло b, и столько же для c. Поэтому общее число лишних решений равно 3U(k-10), а итоговая формула для рассматриваемых значений k получается такая: T(k)=U(k)-3U(k-10) при k от 10 до 13.

Таким образом, берём 4 последних числа нашего списка: 66, 78, 91, 105 и вычитаем из них утроенные первые 4 числа списка, то есть утраиваем 1, 3, 6, 10, получая 3, 9, 18, 30 и производим вычитание, что приводит к числам 63, 69, 73, 75. Окончательно получаем список чисел T(k) при от 0 до 13:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 63, 69, 73, 75.

Каждое из этих чисел надо возвести в квадрат, потом всё сложить, а полученную сумму удвоить. Это и будет ответ. Здесь, к сожалению, приходится прибегать к подсчёту, но он не сложный. В итоге имеем:

S=2*(1+9+36+100+225+441+784+1296+2025+3025+3969+4761+5329+5625)=2*27626=55252.



Итак, общее количество счастливых билетов в точности равно 55252. Забавно, что цифры тут получились только 5 и 2. Вероятно, это связано с тем, что данную задачу можно решить или на "пятёрку", или на "двойку"! :)

Если разделить миллион (общее количество номеров билетов) на найденное количество, то получится приблизительно 18. То есть в среднем примерно каждый 18-й билет является счастливым.
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 39 comments