Трамвайный билет имеет номер,состоящий из шести цифр(лидирующие нули пишутся).Диа. Счастливые билеты

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

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

Итак всего, рассмотрим какой-нибудь счастливый билет 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+30 25+3969+4761+5329+5625)=2*27626=55252.

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

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

Городская легенда о счастливом билете возникла, вероятно, вместе с этим документом. Покупая билет на проезд в любом виде транспорта, человек пытается угадать, принесет ли он ему счастье. Совсем не редкость, когда получивший такую частицу бумаги, стоит и подсчитывает числа, стараясь узнать повезло или нет. Билеты, названные «счастливыми» люди способны хранить годами носить как талисманы.

Поверье о «счастливом» билете основано на нумерологических упражнениях с идентификационным номером билета. Главное требование - получение талона на проезд в обычном порядке. Специальный поиск нужных цифр не считается по-настоящему удачным. Номер должен быть шестизначным. Хотя, существуют способы, расчета «счастливых» билетов, которые можно употреблять и на документах с нечетным количеством цифр.

Известны множество способов определения таких талонов. Один из них - «ленинградский». Согласно этой концепции, сумма четных чисел номера билета должна быть равна сумме нечетных. Самый популярный - «московский». Для определения «счастливого» билета этим способом, следует сложить между собой первые три числа, а затем вторую тройку. Суммы должны совпасть.

Жители Новосибирска поступают похожим способом, чтобы определить «удачный» талон. Правда, есть особенность - они складывают каждую тройку чисел до получения однозначного. С каждой стороны должно получиться одно и то же число, тогда билет «счастливый».

Иногда подсчитывают сумму каждой пары чисел в номере. Если три равны - талон наверняка принесет счастье.

Симметрия в этом деле - не на последнем месте. Номер, отмеченный таким знаком скорее всего принесет обладателю удачу. Одинаковое сочетание цифр как в правой, так и в левой половине номера - верный признак благосклонности фортуны. Существует способ «отзеркаливания». Когда первые три цифры, словно отражаясь в зеркале, повторяют вторую тройку - билет считается «счастливым».

Людям свойственно считать некоторые числа особенным, приносящими удачу только им. Талонами, волшебным образом влияющими на судьбу считаются те, сумма числ в номерах которых соответствует счастливому числу данной личности. Сложив между собой все цифры до получения однозначного числа, можно это узнать.

Любителям тренировать мозг, стоит выполнить различные упражнения с цифрами номера талона. Их можно перемножить, затем из полученного производного вычесть число их суммы. Если в результате получится ноль - это верный признак того, что судьба благоволит обладателю.

Когда не возникает сомнений в том, что билет приносит удачу, следует позаботиться о том, чтобы он всегда был рядом с человеком, как талисман. Только так он будет приносить счастье тому, кто его приобрел.

Сколько существует способов заплатить 50 центов? Мы считаем, что платить можно пенни 1 , никелями 5 , даймами 10 , четвертаками 25 и полудолларами 50 . Дьёрдь Пойа популяризовал эту задачу, продемонстрировав поучительный способ её решения с помощью производящих функций.

Запишем бесконечную сумму, представляющую все возможные способы размена. Начать проще всего со случая, когда имеется меньше разновидностей монет, поэтому положим для начала, что у нас нет никаких монет, кроме пенни. Сумму всех способов заплатить некоторое количество пенни (и только пенни) можно записать в виде

поскольку каждый вариант выплаты включает некоторое количество никелей, выбираемых из первого множителя, и некоторое количество пенни, выбираемых из P . (Заметьте, что N не равняется сумме 1 + 1 + 5 + (1 + 5 ) 2 + (1 + 5 ) 3 + ..., поскольку эта сумма включает многие виды выплат более чем по одному разу. Например, член (1 + 5 ) 2 = 1 1 + 1 5 + 5 1 + 5 5 трактует 1 5 и 5 1 , как если бы они были различными, но мы хотим перечислить все множества монет по одному разу безотносительно к их порядку.)

Аналогично, если допустить ещё и даймы, то получим бесконечную сумму

Наша задача состоит в том, чтобы найти, сколько слагаемых в C сто́ят ровно 50 центов.

Задача решается с помощью простого трюка. Заменим 1 на z , 5 на z 5 , 10 на z 10 , 25 на z 25 и 50 на z 50 . Каждое слагаемое тогда заменится на z n , где n — стоимость исходного слагаемого в пенни. Например, слагаемое 50 10 5 5 1 превратится в z 50+10+5+5+1 = z 71 . Каждый из четырёх возможных способов заплатить 13 центов, а именно, 10 1 3 , 5 1 8 , 5 2 1 3 и 1 13 , сведётся к z 13 ; следовательно, коэффициентом при z 13 после z -подстановки будет 4.

Пусть P n , N n , D n , Q n и C n обозначают число способов заплатить сумму в n центов, если можно использовать монеты не старше, соответственно, 1, 5, 10, 25 и 50 центов. Наш анализ показал, что эти числа суть коэффициенты при z n в соответствующих степенных рядах

P =	1 + z + z 2 + z 3 + z 4 + ... ,
N =	(1 + z 5 + z 10 + z 15 + z 20 + ...)P ,
D =	(1 + z 10 + z 20 + z 30 + z 40 + ...)N ,
Q =	(1 + z 25 + z 50 + z 75 + z 100 + ...)D ,
C =	(1 + z 50 + z 100 + z 150 + z 200 + ...)Q .

Очевидно, что P n = 1 для всех n ≥0 . По кратком размышлении легко доказать, что N n = [n /5] + 1: для того чтобы составить сумму в n центов из пенни и никелей, мы должны взять 0, или 1, или..., или [n /5] никелей, после чего останется лишь единственный способ выбрать требуемое число пенни. Итак, значения P n и N n легко вычисляются, однако с D n , Q n и C n дело обстоит гораздо сложнее.

Один из подходов к исследованию этих формул основан на замечании, что 1 + z m + z 2m + ... есть просто 1/(1 – z m ). Следовательно, мы можем записать

Теперь, приравнивая коэффициенты при z n в этих уравнениях, получим рекуррентные соотношения, из которых желаемые коэффициенты легко вычисляются:

Например, коэффициент при z n в D = (1 – z 25)Q равен Q n – Q n –25 ; поэтому должно быть Q n – Q n –25 = D n , как и записано выше.

Можно было бы раскрыть эти соотношения и выразить Q n , например, в виде Q n = D n + D n –25 + D n –50 + D n –75 + ..., где сумма обрывается, когда индексы становятся отрицательными. Однако, исходная, неитеративная форма удобна тем, что каждый коэффициент вычисляется с помощью всего одного сложения, как в треугольнике Паскаля.

Используем эти соотношения, чтобы найти C 50 . Во-первых, C 50 = C 0 + Q 50 , так что нам нужно знать Q 50 . Далее, Q 50 = Q 25 + D 50 и Q 25 = Q 0 + D 25 ; поэтому нас также интересуют D 50 и D 25 . Эти значения D n в свою очередь, зависят от D 40 , D 30 , D 20 , D 15 , D 10 и D 5 и от N 50 , N 45 , ..., N 5 . Таким образом, чтобы определить все нужные коэффициенты, достаточно выполнить простые вычисления:

n	0	5	10	15	20	25	30	35	40	45	50
P n	1	1	1	1	1	1	1	1	1	1	1
N n	1	2	3	4	5	6	7	8	9	10	11
D n	1	2	4	6	9	12	16		25		36
Q n	1					13					49
C n	1										50

В самом низу таблицы находится ответ C 50: имеется ровно 50 способов дать 50 центов «на чай».

А что можно сказать о замкнутой форме для C n ? Перемножение всех уравнений даёт нам компактное выражение для производящей функции

которая является рациональной функцией от z , знаменатель которой имеет степень 91. Таким образом, мы можем разложить знаменатель на 91 множитель и выразить C n в «замкнутом виде», состоящем из 91 слагаемого. Но такое ужасное выражение не лезет ни в какие ворота. Нельзя ли в этом частном случае найти что-либо лучшее, а не применять общий метод?

А вот и первый проблеск надежды: если в C (z ) заменить 1/(1 – z ) на (1 + z + z 2 + z 3 + z 4)/(1 – z 5):

= (1 + z + z 2 + z 3 + z 4)Č (z 5), Č (z ) =

то степень знаменателя «сжатой» функции Č (z ) уже только 19, так что эта функция гораздо лучше исходной. Новое выражение для C (z ) показывает, в частности, что C 5n = C 5n +1 = C 5n +2 = C 5n +3 = C 5n +4 ; и действительно, это соотношение легко объяснить: чаевые в 53 цента можно дать ровно столькими же способами, как и чаевые в 50 центов, поскольку количество пенни по модулю 5 заранее известно.

Однако даже для Č (z ) не существует простого выражения, основанного на корнях знаменателя. Вероятно, простейший способ вычисления коэффициентов Č (z ) получится, если заметить, что каждый сомножитель в знаменателе является делителем 1 – z 10 . Следовательно, мы можем записать

Вот, для полноты картины, развернутое выражение для A (z ):

(1 + z + ... + z 9) 2 (1 + z 2 + ... + z 8)(1 + z 5) =
= 1 + 2z + 4z 2 + 6z 3 + 9z 4 + 13z 5 + 18z 6 + 24z 7 +
+ 31z 8 + 39z 9 + 45z 10 + 52z 11 +57z 12 + 63z 13 + 67z 14 + 69z 15 +
+ 69z 16 + 67z 17 + 63z 18 + 57z 19 + 52z 20 + 45z 21 + 39z 22 + 31z 23 +
+ 24z 24 + 18z 25 + 13z 26 + 9z 27 + 6z 28 + 4z 29 + 2z 30 + z 31 .

И, в завершение, воспользовавшись тем, что

получаем следующее выражение для коэффициентов Č n при степенях z n в разложении функции Č (z ), в котором n = 10q + r и 0≤r <1 0:

Č 10q +r =	∑	A j	(	k + 4 k	)	=
	j , k 10k +j =n

= A r

(

q + 4 q

)

+ A r +10

(

q + 3 q

)

+ A r +20

(

q + 2 q

)

+ A r +30

(

q + 1 q

)

.

Здесь фактически содержится 10 различных случаев, по одному на каждое значение r ; но это всё же неплохая замкнутая формула в сравнении с альтернативами, включающими степени комплексных чисел.

Используя это выражение, можем узнать, например, значение C 50q = Č 10q . Здесь r =0 , и мы имеем

для суммы в 1 доллар получается

(

6 4

)

+ 45

(

5 4

)

+ 52

(

4 4

)

= 292 способа;

а для миллиона долларов это число составит

(

2000004 4

)

+ 45

(

2000003 4

)

+ 52

(

2000002 4

)

+ 2

(

2000001 4

)

=

= 66666793333412666685000001.

Счастливый билет... Тех, кто помнит советский общественный транспорт с проездными билетами, компостерами - это словосочетание заставит ностальгически улыбнуться. А вот юному поколению, возможно, потребуется объяснение.

Счастливый билет... Тех, кто помнит советский общественный транспорт с проездными билетами, компостерами - это словосочетание заставит ностальгически улыбнуться.

А вот юному поколению, возможно, потребуется объяснение.

Что такое счастливый билет?

Cчастливым билетом считается тот, в котором сумма первых трех цифр совпадает с суммой трех последних, например: 142511=(1+4+2)+(5+ 1+1)=7-7.

Попрактикуйтесь в арифметике - ведь такой билет приносит счастье! Получив его, следует загадать желание, а сам билет - сохранить.

Есть поверье, что билет лучше сразу съесть, как, например, счастливый пятилепестковый цветочек сирени. Но, учитывая, что в среднем каждый 18 билет - счастливый, мы все же лучше обратимся к нумерологии.

Получив счастливый билет, вы можете рассчитать его нумерологический код и загадать желание в соответствии с его значением. Таким образом вы усиливаете действие цифровых вибраций. Код билета представляет собой сумму всех цифр его номера, доведенных до простого числа. Например: 142511=1+4+2+5+1+1=14=1+4=5.

Загадываем желание на счастливый билет

Каково значение основных чисел и что лучше загадывать на каждое из них?

Счастливый билет: сумма равна 1

Единица - сильное, активное число, покровительствующее рискованным начинаниям, радикальным решениям, поворотам судьбы. Хотите резко изменить ситуацию- переехать, сменить работу, встретить любимого, разбогатеть - загадывайте желание.

Единица так же благоприятна для того, чтобы загадать успех в частном бизнесе: даже если вы считаете себя недостаточно предприимчивым, забудьте об этом - счастливый билет поможет в реализации самого фантастического проекта.

Счастливый билет: сумма равна 2

Число, связанное с взаимодействием и коммуникациями, признанием и популярностью, поэтому загадывайте воплощение каких-то карьерных или творческих амбиций.

Если в семье или отношениях случился разлад то на это число хорошо загадывать примирение и озвучивать мечты о взаимопонимании и мире в семье.

Счастливый билет: сумма равна 3

Тройка отвечает за общение - производственное, дружеское, родственное, романтическое. Тому, кто нуждается во взаимопонимании с каким-то конкретным человеком - будь то любимый или босс, - счастливый билет с таким кодом поможет завоевать расположение и симпатию.

Если вы испытываете проблемы в общении, то стеснительность, закомплексованность должны отступить перед вашим желанием.

Счастливый билет: сумма равна 4

Число, связанное с управлением и подчинением, с воздействием, которые вы оказываете на других людей.

Если вы не очень строгий родитель, четверка поможет вам оказать нужное влияние на ребенка-подростка, если вы начальник - заставит подчиненных ревностно исполнять ваши распоряжения; если вы влюблены - поможет настоять на своем. Но постарайтесь не переборщить с желанием - вы же не хотите, чтобы вас воспринимали как тирана и деспота?

Счастливый билет: сумма равна 5

Число эмоций и чувств, романтики и приключений. Забудьте о проблемах на работе.

Самое время окунуться в океан любви и загадать, чтобы на ваши чувства ответили взаимностью и не тянули с предложением руки и сердца. Даже в привычное течение семейной жизни этот счастливый билет может внести ощущение новизны и искушения.

Счастливый билет: сумма равна 6

Число, связанное с самореализацией. Вы уверены, что выбрали именно ту профессию, которая больше всего соответствует вашим способностям и характеру? Не загадать ли вам перемены в жизни, которые помогут раскрыть вашу личность?

Не стесняйтесь мечтать, только пусть ваши мечты выглядят как стратегия, а не как абстрактная живопись: сформулируйте свое желание как можно яснее - это число любит порядок и четкость.

Счастливый билет: сумма равна 7

Семерка - проводник в таинственные, мистические, трансцендентные миры. Не стоит загадывать что-то бытовое или материальное - это магическое число поможет вам в духовных поисках, раскроет перед вами удивительные тайны, позволит проникнуть в тонкие сферы.

Можно попросить счастливый билет раскрыть ваши эзотерические способности или получить знак свыше, увидеть своего ангела-хранителя или заглянуть в будущее. Но готовы ли вы к исполнению такого желания, может, выбрать что-то попроще?

Счастливый билет: сумма равна 8

Самое время загадать что-то конкретное, весомое, зримое, восьмерка- число богатства и процветания. Если вы недовольны своим материальным положением, загадывайте нежданное богатство, денежное поступление, повышение зарплаты или наследство.

Загадайте подарок, о котором больше всего мечтаете , или какую-то крупную покупку, можно озвучить желание открыть свое дело, в общем, для этого числового кода нужны земные и вещественные желания.

Счастливый билет: сумма равна 9

Пора извлечь из архива памяти якобы неразрешимые проблемы и с новыми силами попытаться их преодолеть. Девятка поможет распутать даже самые запутанные узлы личных отношений, решить самые сложные производственные или научные задачи.

В случае, если в номере есть нули или повторы, сила его основного числа ослабляется. А вот счастливый билет, в котором все цифры разные, усиливает притяжение удачи.

Не забывайте оплачивать проезд и чаще получайте счастливые билеты!

Как стать счастливым? Неоднократно, устами умнейших своих представителей, человечество пыталось дать ответ на этот вопрос.

Один из ответов (не ручаемся за то, что его автор относится к указанной группе) гласит: для счастья нужно совсем немного: всего-то - купить у кондуктора трамвайный билетик со счастливым номером. Далее нужно произвести определённые действия. Какие именно - я, признаться, уже плохо помню. Вроде, речь шла даже о том, что билетик нужно съесть.

Мы ни в коем случае не предлагаем запихивать в рот, а уж, тем более, пропускать через желудочно-кишечный тракт не очень чистую бумагу, покрытую типографской краской и предупреждаем, что подобные действия могут негативно отразиться на вашем здоровье. И вообще, на вопрос, поставленный в начале статьи, у нас ответа нет.

Интересовать нас будет ответ на другой вопрос, гораздо менее глобальный. Детально сформулируем его в виде следующей задачи.

Каждый трамвайный билет имеет номер, состоящий из шести произвольных цифр от 0 до 9. Номер считается "счастливым", если сумма его первых трёх цифр совпадает с суммой трёх последних. Например, счастливым является номер "123420". Сколько всего существует счастливых номеров?

В дальнейшем билет со счастливым номером тоже будем называть счастливым. Задачу будем решать различными способами. Программы будут весьма простыми, поэтому данную статью можно смело рекомендовать новичкам в программировании на C99 (именно этот язык будет использоваться в статье). Правда, "математическая" часть статьи может показаться сложной тем, кто с комбинаторикой пока на "Вы".

Метод перебора

Первый способ, который мы будем использовать - "лобовой". Разумеется, речь идёт о методе перебора. "Лобовые" способы обычно имеют ряд преимуществ перед более изощрёнными. Они, как правило, более просты с точки зрения разработки и реализации. Как следствие, на их создание тратится меньшее время. Наконец, в их реализации сложнее допустить ошибку.

Так что, если никаких особых требований к решению задачи не предъявляется (например, связанных с объёмом памяти, быстродействием, количеством операций), то "лобовой" метод вполне сгодится. Но, конечно же, программа, построенная даже на таком методе, должна, как минимум, запускаться на компьютере (неожиданно, не правда ли?) и, кроме этого, выполняться приемлемое время.

Современные (и даже не очень) компьютеры выполняют перебор миллиона чисел (а именно столько существует номеров билетов) за доли секунды, поэтому проблем с временем выполнения явно не возникнет.

Идея метода перебора заключается в следующем. Будет создана переменная для хранения текущего числа обнаруженных счастливых номеров. Для перебора всех возможных номеров будем использовать два цикла: внешний и внутренний. Счётчик каждого из них будет пробегать значения от 0 до 999. Таким образом, можно считать, что счётчик внешнего цикла содержит первую "тройку" цифр номера, а счётчик внутреннего - вторую (или наоборот).

На каждой итерации внутреннего цикла будут сравниваться суммы цифр значений счётчиков циклов; в случае их равенства значение счётчика счастливых номеров будет увеличиваться на единицу. По окончании итераций значение счётчика счастливых номеров будет выведено на печать.

Для подсчёта упомянутых сумм цифр нам нужно научиться извлекать из любого числа от 0 до 999 цифры, которые используются для его записи. Договоримся считать, что количество цифр всегда равно трём, даже если число двухзначное или однозначное (в этом случае "недостающие" цифры будем считать нулями).

Эти цифры получить несложно. Первую цифру можно получить, если произвести целочисленное деление числа на 100. Вторую - если целую часть частного от деления числа на 10 снова разделить на 10 и взять остаток. Наконец, третью - если разделить число на 10 и взять остаток.

Ниже приведён код программы, решающей нашу задачу методом перебора.

#include int main() { int s = 0; //счётчик количества счастливых номеров for (int i = 0; i <= 999; i++) for (int j = 0; j <= 999; j++) if (i / 100 + i / 10 % 10 + i % 10 == j / 100 + j / 10 % 10 + j % 10) s++; printf("Количество счастливых номеров равно %d", s); return 0; }

Выполнение программы приводит к следующему выводу на консоль:

Количество счастливых номеров равно 55252

Задача методом перебора решена.

Альтернативный способ

Напишем теперь более эффективную программу. Разницы в быстродействии мы, скорее всего не увидим, но зато, надеюсь, получим моральное удовлетворение от проделанной работы. Действовать будем следующим образом.

Сумма трёх цифр может принимать значения от 0 до 27. Создадим массив c , состоящий из 28 элементов, и поместим в каждый из них значение, равное количеству чисел, принадлежащих диапазону от 0 до 999, сумма цифр каждого из которых равна индексу элемента. Сделать это несложно: сначала заполняем элементы нулями, а потом перебираем все числа из этого диапазона, для каждого числа подсчитываем сумму его цифр и увеличиваем на единицу значение элемента массива, индекс которого совпадает с вычисленной суммой.

Очевидно, что если записать подряд два любых числа из диапазона от 0 до 999 (дополнив необходимым количеством нулей слева однозначные и двухзначные числа), сумма цифр каждого из которых равна n , то мы получим номер счастливого билета с суммой цифр 2n. Таким образом, количество счастливых номеров, сумма цифр которых равна 2n , будет совпадать с количеством различных пар чисел из указанного диапазона, сумма цифр каждого из которых равна n .

Поскольку каждый элемент пары может быть любым числом из диапазона от 0 до 999, сумма цифр которого равна n , то количество всех таких пар, очевидно, равно квадрату количества всех таких чисел, т. е. квадрату значения элемента массива c с индексом, равным n . Это означает, что число счастливых номеров можно получить, если просуммировать квадраты значений всех элементов массива c .

Вот код программы, работающей по описанному выше алгоритму:

#include int main() { int c; for (int i = 0; i < 28; i++) c[i] = 0; for (int i = 0; i < 10; i++) for (int j = 0; j < 10; j++) for (int k = 0; k < 10; k++) c++; int s = 0; //счётчик количества счастливых номеров for (int i = 0; i < 28; i++) s += c[i] * c[i]; printf("Количество счастливых номеров равно %d", s); return 0; }

Заметим, что мы не стали, на этот раз, перебирать в цикле числа от 0 до 999, а вместо этого построили три вложенных друг в друга цикла, в каждом из которых перебираются цифры от 0 до 9.

Выполнение данной программы приводит к точному такому же выводу на консоль, что и выполнение предыдущей.

Математический подход

Очень часто после того, как некоторая комбинаторная задача решена программным способом, возникает желание попробовать получить чисто математическое решение, для построения которого требуются лист бумаги, ручка и, в крайнем случае, калькулятор, умеющий выполнять 4 арифметических действия. Мне удалось решить задачу о счастливых номерах без использования компьютера, но решение получилось несколько громоздким. Не исключено, что кто-то из читателей сможет предложить более элегантное решение.

Будем для вычисления количества счастливых номеров S использовать выведенную в предыдущем разделе формулу

S = ∑ k = 0 27 c k 2 ,

где c k - количество чисел от 0 до 999, сумма цифр которых равна k .

Пусть A k - множество всех упорядоченных троек однозначных чисел, сумма которых равна k . Заметим, что заменив в каждом элементе этого множества каждое число разностью числа 9 и данного числа, мы перейдём от множества A k к множеству A 27-k . Таким образом, между множествами A k и A 27-k может быть установлено взаимно однозначное соответствие, откуда следует, что c k = c 27-k . С учётом этого равенства формулу для вычисления S можно переписать в виде:

S = 2 ∑ k = 0 13 c k 2 .

Зададимся целью выразить c k через k .

Пусть t i - количество чисел от 0 до 99, сумма цифр которых равна i , где i принимает значения от 0 до 18. Несложно заметить, что t i = i + 1, если i ≤ 9, причём t i = t 18-i (последнее равенство устанавливается точно таким же способом, как и равенство c k = c 27-k ), откуда следует, что t i = 19 - i , если i ≥ 10. Таким образом, числа t i в порядке возрастания индексов имеют следующие значения:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 9, 8, 7, 6, 5, 4, 5, 4, 3, 2, 1.

Рассмотрим упорядоченную тройку однозначных чисел, сумма которых равна k . Пусть сумма второго и третьего чисел равна i . Зададимся вопросом: какие значения может принимать параметр i при фиксированном k ? Минимальное значение, которое может принять i (обозначим его i min ), очевидно, равно разности k и максимально возможного значения первого числа, равного min(k , 9), т. е.

I m i n = k - min k , 9 = max k - 9 , 0 .

Максимальное значение, которое может принять i (обозначим его i max ), очевидно, равно разности k и минимально возможного значения первого числа, равного max(k - 18, 0), т. е.

I m a x = k - max k - 18 , 0 = min k , 18 .

Итак, мы выяснили, что для фиксированного k параметр i может принимать любые значения из диапазона от max(k - 9, 0) до min(k , 18). Но, поскольку каждому значению i соответствует t i упорядоченных пар однозначных чисел, сумма которых равна i , то для получения количества всех упорядоченных троек однозначных чисел, сумма которых равна k (т. е. для получения c k ), нужно просуммировать все числа t i , индексы которых попадают в указанный диапазон. Таким образом,

C k = ∑ i = max k - 9 , 0 min k , 18 t i .

C k = ∑ i = k - 9 k t i .

Итак, мы выразили c k через t i . Но значения t i нам уже известны, поэтому мы можем теперь заняться теперь выражением с k через k . Для k от 0 до 9 имеем:

C k = ∑ i = 0 k t i = ∑ i = 0 k i + 1 = ∑ i = 1 k + 1 i = k + 1 k + 2 2 = k 2 + 3 k + 2 2 .

Здесь мы использовали хорошо известную формулу суммы первых k натуральных чисел:

∑ i = 1 k i = k k + 1 2 .

Теперь выразим с k через k для k от 10 до 13:

C k = ∑ i = k - 9 k t i = ∑ i = k - 9 9 t i + ∑ i = 10 k t i = ∑ i = k - 9 9 i + 1 + ∑ i = 10 k 19 - i .

Для вычисления последних двух сумм применим следующую формулу суммы n членов арифметической прогрессии a 1 , a 2 , …, a n :

∑ k = 1 n a k = a 1 + a n 2 · n .

∑ i = k - 9 9 i + 1 = k - 8 + 10 2 · 19 - k = k + 2 19 - k 2 = - k 2 + 17 k + 38 2 ,
∑ i = 10 k 19 - i = 9 + 19 - k 2 · k - 9 = 28 - k k - 9 2 = - k 2 + 37 k - 252 2 .

Окончательно получаем:

C k = - k 2 + 17 k + 38 2 + - k 2 + 37 k - 252 2 = - 2 k 2 + 54 k - 214 2 = - k 2 + 27 k - 107 .

Итак, нам удалось выразить с k через k для любых k от 0 до 13. Подставим теперь эти найденные выражения в формулу для вычисления количества счастливых номеров:

S = 2 ∑ k = 0 13 c k 2 = 2 ∑ k = 0 9 c k 2 + ∑ k = 10 13 c k 2 = 2 ∑ k = 0 9 k 2 + 3 k + 2 2 2 + ∑ k = 10 13 - k 2 + 27 k - 107 2 =
= 1 2 ∑ k = 0 9 k 2 + 3 k + 2 2 + 2 ∑ k = 10 13 - k 2 + 27 k - 107 2 .

Найдём каждую из двух последних сумм (обозначим их, в порядке следования, S 1 и S 2), по-отдельности.

Для нахождения S 1 раскроем скобки, стоящие под знаком суммы, разобьём сумму на несколько сумм и вычислим каждую из них. Нам потребуются формула суммы первых n натуральных чисел, приведённая нами ранее, а также следующие общеизвестные формулы квадратов, кубов и четвёртых степеней первых n натуральных чисел:

∑ k = 1 n k 2 = n n + 1 2 n + 1 6 ,
∑ k = 1 n k 3 = n n + 1 2 2 ,
∑ k = 1 n k 4 = n n + 1 2 n + 1 3 n 2 + 3 n - 1 30 .

S 1 = ∑ k = 0 9 k 2 + 3 k + 2 2 = ∑ k = 0 9 k 4 + 9 k 2 + 4 + 6 k 3 + 12 k + 4 k 2 =
= ∑ k = 0 9 k 4 + 6 k 3 + 13 k 2 + 12 k + 4 = ∑ k = 0 9 k 4 + 6 ∑ k = 0 9 k 3 + 13 ∑ k = 0 9 k 2 + 12 ∑ k = 0 9 k + ∑ k = 0 9 4 = ∑ k = 1 9 k 4 +
+ 6 ∑ k = 1 9 k 3 + 13 ∑ k = 1 9 k 2 + 12 ∑ k = 1 9 k + 40 = 9 · 10 · 19 · 269 30 + 6 · 9 · 10 2 2 + 13 · 9 · 10 · 19 6 +
+ 12 · 9 · 10 2 + 40 = 15333 + 12150 + 3705 + 540 + 40 = 31768 .

Для нахождения второй суммы просто вычислим слагаемые и сложим их. Я не вижу особого смысла прибегать, как в предыдущем случае, к использованию нескольких формул, поскольку слагаемых всего 4. Итак, находим S 2:

S 2 = ∑ k = 10 13 - k 2 + 27 k - 107 2 = - 100 + 270 - 107 2 + - 121 + 297 - 107 2 +
+ - 144 + 324 - 107 2 + - 169 + 351 - 107 2 = 63 2 + 69 2 + 73 2 + 75 2 = 3969 + 4761 +
+ 5329 + 5625 = 19684 .

Остаётся вычислить S:

S = 1 2 S 1 + 2 S 2 = 31768 2 + 2 · 19684 = 15884 + 39368 = 55252 .

Задача решена.

Заключение

Несложно подсчитать вероятность покупки у кондуктора билета со счастливым номером: она равна 0,055252, т. е. немного превышает 5,5%. Вероятность невысока, но если вы часто ездите на трамвае, то, скорее всего, счастливый билет вам когда-нибудь достанется. Давайте, подсчитаем, например, вероятность того, что билет со счастливым номером будет куплен вами хотя бы один раз в течение невисокосного года, если каждый день в течение этого года вы совершаете ровно одну поездку на трамвае:

1 - 1 - 0 , 055252 365 = 0 , 9999999990 …

Девять девяток после запятой. Событие почти достоверное! Впрочем, если вы готовы довольствоваться двумя девятками, то вполне сгодится и квартал (91 день). 91 поездка на трамвае в Санкт-Петербурге на момент написания этой статьи обойдётся в 2730 рублей. Не очень высокая плата за счастье, не правда ли?