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

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

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

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

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

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

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

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

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

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

.

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

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

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

штук.

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