Question

На доске написаны числа от 1 до 100. какое наименьшее количество из них можно стереть так, чтобы произведение оставшихся не делилось бы на 18

Answer 1

9, 6, 3, 2, 18,36,54,72,90

Answer 2

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

Алгоритм:

1. Начнем с предположения, что на доске написаны все числа от 1 до 100. 2. Проверим, делится ли произведение всех чисел от 1 до 100 на 18. Если да, то удалим число 18, так как его удаление не повлияет на делимость произведения на 18. 3. Повторим шаг 2 для всех последующих чисел, удаляя их по очереди и проверяя делимость произведения на 18 после каждого удаления. 4. Когда произведение оставшихся чисел перестанет делиться на 18, мы найдем наименьшее количество чисел, которое можно стереть, чтобы это произошло.

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