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

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

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

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

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

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

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

Теперь очень хочется сказать, что ответом является сумма красивых номеров . Но посчитаны также числа, которые удовлетворяют более чем одному условию, а такие числа не являются красивыми. На самом деле мы посчитали два раза числа, которые удовлетворяют двум условиям, и три раза числа, удовлетворяющие трем условиям! Это нужно вычесть.
Сколько чисел удовлетворяют одновременно условиям а) и в)? Это числа, которые кратны и . Первые встречается в циклах из пяти чисел, а вторые — в циклах из девяти чисел, циклы совпадают через число шагов, равное наименьшему общему кратному и , т.е. (можно прямо сказать, что если число кратно и , то оно кратно , однако мы используем циклы, поэтому о них и говорим). Первое подходящее число , а затем мы находим циклов. Тогда всего числа одновременно удовлетворяют условиям а) и в).

Что касается чисел, которые удовлетворяют условиям а) и б), сначала находим первое такое число. не подходит, поэтому мы добавляем по , чтобы найти нужное число: не подходит, тоже, и не , а вот подходит. И от делящиеся на числа находятся в циклах по пять чисел, а дающие остаток при делении на — в циклах по семь чисел. Тогда два условия повторяются в циклах по чисел, которых после 00030 всего Поэтому чисел, которые удовлетворяют условиям а) и б), всего .

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

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

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

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

штук.

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