С 2011 года проводится Рождественская лотерея, в которой разыгрываются призы между сто тысячью билетов с номерами от
до
(числа всегда написаны с использованием пяти цифр). Несмотря на то, что все билеты имеют одинаковые шансы выиграть, часто говорят о красивых номерах и номерах довольно некрасивых. Поскольку оценка красоты является эстетической, является ли число красивым или нет зависит от вкусов каждого.
В нашем случае лотерейный номер будет считаться красивым, если его номер отвечает одному и только одному из следующих трех условий:
а) делится на
,
б) дает в остатке
при делении на
,
в) сумма его цифр делится на
.
Задача состоит в том, чтобы определить, сколько номеров билетов, участвующих в Рождественской лотерее (помните, их номера от
до
) красивые согласно определению, приведенному выше.
Последовательные вычисления
Так как не совсем легко сразу посчитать, сколько чисел удовлетворяют одному условию, но не удовлетворяют двум другим, первый шаг заключается в нахождении, сколько чисел удовлетворяет каждому из условий.
У нас 100000 чисел, и одно число из каждых пяти подряд идущих кратно 5. Таким образом, условию а) удовлетворяют
чисел. Первое из них
, а последнее
.
Что касается условия в), вспомним, что сумма цифр делится на девять тогда и только тогда, когда число делится на
. Это встречается у одного из девяти подряд идущих чисел, но число
не целое, потому нужно быть немного осторожнее. Первое число, для которого выполняется условие —
, а дальше условие выполняются для каждого девятого из девяти чисел. То есть у нас есть в общей сложности
![Rendered by QuickLaTeX.com \[1 + (99999 / 9) = 1 +11111 = 11112\]](http://hijos.ru/wp-content/ql-cache/quicklatex.com-aa9855e2ea0db4316cc3c6e3077fd60f_l3.png)
чисел, удовлетворяющих условию в). Первое из них
и последнее
.
Для условия б) поступаем таким же образом: от первого числа, для которого выполняется это условие, отсчитываем по семь чисел, чтобы понять, сколько их у нас есть в общей сложности. Первый требуемое число
, и у нас остается еще
чисел, которым соответствуют
циклов по семь чисел. Дробь показывает, что новый цикл не завершен, поэтому в общей сложности насчитывается
чисел, которые удовлетворяют условию б).
Теперь очень хочется сказать, что ответом является сумма
красивых номеров
. Но посчитаны также числа, которые удовлетворяют более чем одному условию, а такие числа не являются красивыми. На самом деле мы посчитали два раза числа, которые удовлетворяют двум условиям, и три раза числа, удовлетворяющие трем условиям! Это нужно вычесть.
Сколько чисел удовлетворяют одновременно условиям а) и в)? Это числа, которые кратны
и
. Первые встречается в циклах из пяти чисел, а вторые — в циклах из девяти чисел, циклы совпадают через число шагов, равное наименьшему общему кратному
и
, т.е.
(можно прямо сказать, что если число кратно
и
, то оно кратно
, однако мы используем циклы, поэтому о них и говорим). Первое подходящее число
, а затем мы находим
циклов. Тогда всего
числа одновременно удовлетворяют условиям а) и в).
Что касается чисел, которые удовлетворяют условиям а) и б), сначала находим первое такое число.
не подходит, поэтому мы добавляем по
, чтобы найти нужное число:
не подходит,
тоже, и не
, а вот
подходит. И от
делящиеся на
числа находятся в циклах по пять чисел, а дающие остаток
при делении на
— в циклах по семь чисел. Тогда два условия повторяются в циклах по
чисел, которых после 00030 всего
Поэтому чисел, которые удовлетворяют условиям а) и б), всего
.
Чтобы увидеть, как много чисел удовлетворяют условиям б) и в), действуем аналогично. Первое подходящее число
, и условия выполнятся через каждые
числа (
является наименьшим общим кратным
и
). Поэтому находим
, таким образом,
лотерейных билетов, номера которых удовлетворяют условиям б) и в).Таким образом, чтобы удалить некрасивые номера, удовлетворяющие двум условиям, нужно вычесть из предыдущего результата
![Rendered by QuickLaTeX.com \[2\cdot (2223 +2857 +1588) = 13336.\]](http://hijos.ru/wp-content/ql-cache/quicklatex.com-559d3d1d3fea90d0a4fccdf796fd6b37_l3.png)
Теперь все суммируем
Но будьте осторожны! Если мы это сделаем, мы шесть раз вычтем количество чисел, которые удовлетворяют всем трем условиям, а нужно это число вычесть три раза. Чтобы это исправить, мы снова добавим его три раза.Таким образом, нужно посчитать, сколько чисел удовлетворяют трем условиям. Мы искали среди чисел, кратных
и
, то есть кратных
, первое, дающее остаток
при делении на
. Это не
, подходит
. И теперь, так как наименьшее общее кратное
и
составляет
, это длина циклов, которые появляются для чисел, удовлетворяющих трем условиям. После того мы пройдем
таких циклов, и поэтому есть
чисел, удовлетворяющих всем трем условиям.
Cложив все это вместе, получим, что по определению, данному в условии задачи, красивых лотерейных билетов
штук.
То есть их почти треть от общего числа билетов.Техника, которую мы использовали для расчета, известна как формула включения — исключения. И, хотя мы не использовали ее непосредственно, для работы с различными числами, удовлетворяющими условиям делимости, теорема, которую называют китайской теоремой об остатках.
Оставьте свой отзыв