Математика, которая мне нравится

Последовательные вычисления

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

У нас 100000 чисел, и одно число из каждых пяти подряд идущих кратно 5. Таким образом, условию а) удовлетворяют

чисел. Первое из них

, а последнее

.

Что касается условия в), вспомним, что сумма цифр делится на девять тогда и только тогда, когда число делится на

. Это встречается у одного из девяти подряд идущих чисел, но число

не целое, потому нужно быть немного осторожнее. Первое число, для которого выполняется условие —

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

чисел, удовлетворяющих условию в). Первое из них

и последнее

.

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

, и у нас остается еще

чисел, которым соответствуют

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

чисел, которые удовлетворяют условию б).

Теперь очень хочется сказать, что ответом является сумма

красивых номеров

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

и

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

и

, т.е.

(можно прямо сказать, что если число кратно

и

, то оно кратно

, однако мы используем циклы, поэтому о них и говорим). Первое подходящее число

, а затем мы находим

циклов. Тогда всего

числа одновременно удовлетворяют условиям а) и в).

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

не подходит, поэтому мы добавляем по

, чтобы найти нужное число:

не подходит,

тоже, и не

, а вот

подходит. И от

делящиеся на

числа находятся в циклах по пять чисел, а дающие остаток

при делении на

— в циклах по семь чисел. Тогда два условия повторяются в циклах по

чисел, которых после 00030 всего

Поэтому чисел, которые удовлетворяют условиям а) и б), всего

.

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

, и условия выполнятся через каждые

числа (

является наименьшим общим кратным

и

). Поэтому находим

, таким образом,

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

.

Теперь все суммируем

Но будьте осторожны! Если мы это сделаем, мы шесть раз вычтем количество чисел, которые удовлетворяют всем трем условиям, а нужно это число вычесть три раза. Чтобы это исправить, мы снова добавим его три раза.Таким образом, нужно посчитать, сколько чисел удовлетворяют трем условиям. Мы искали среди чисел, кратных

и

, то есть кратных

, первое, дающее остаток

при делении на

. Это не

, подходит

. И теперь, так как наименьшее общее кратное

и

составляет

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

таких циклов, и поэтому есть

чисел, удовлетворяющих всем трем условиям.

Cложив все это вместе, получим, что по определению, данному в условии задачи, красивых лотерейных билетов

штук.

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