Question

На доске выписаны числа 1, 2, 3, ....., 99, 100. Том хочет стереть некоторые из этих чисел так, чтобы произведения оставшихся не делилось на 18. Какое наименьшее количество чисел ему придётся стереть?

Answer 1

18=2*3*3
99/3=33 числа делится на 3
100/2=50 делится на 2
33-1=32 числа (отнимаем 1 отменьшего потому что в разложении 2 тройки)

Answer 2

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

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

Разложим число 18 на простые множители: 18 = 2 * 3 * 3.

Мы знаем, что если произведение делится на 18, то оно должно содержать все простые множители числа 18. Следовательно, среди чисел от 1 до 100 должны быть присутствовать числа, которые являются кратными 2, 3 и 3.

Выясним количество чисел, которые делятся на 2: 2, 4, 6, ..., 98, 100. Всего таких чисел будет 50.

Количество чисел, которые делятся на 3: 3, 6, 9, ..., 99. Последовательность чисел делится на 3 равномерно, поскольку имеется 33 числа, делящихся на 3.

Количество чисел, которые делятся на 3 еще раз: 3, 6, 9, ..., 99 (скоректированная последовательность). Поскольку мы уже учли числа, кратные 2 и 3, мы должны удалить все числа, кратные 9, чтобы избежать повторения. Всего есть 11 чисел, кратных 9.

Теперь найдем общее количество чисел, которые должны быть стерты: 50 + 33 + 11 = 94.

То есть, Тому придется стереть 94 числа, чтобы произведение оставшихся чисел не делилось на 18.