Решение задачи 393

Условие:

Натуральное число разрешено увеличить на любое целое число процентов от 1 до 100, если при этом получаем натуральное число. Найдите наименьшее натуральное число, которое нельзя при помощи таких операций получить из числа 1.

Решение:

Увеличим 1 на 100%, получим 2. Двойку увеличим на 50 и 100 процентов, получим 3 и 4 соответственно. Число 4 увеличим на 25, 50, 75, 100 процентов, получим 5, 6, 7, 8 соответственно. Девятку получим, увеличив 6 на 50%, десятку -- увеличив 8 на 25%. Далее увеличивая десятку на 10, 20, ..., 100 процентов, получим все числа до 20 включительно. Увеличим 20 на 5, 10, 15, 20, 25 процентов, получим 21, ..., 25. Увеличим 25 на 4, 8, ..., 100 процентов, получим все числа до 50 включительно. Увеличим 50 на 2, 4, 8, ..., 100 процентов, получим все числа до 100 включительно. Увеличим 100 на 1, 2, 3, ..., 100 процентов, получим все числа до 200 включительно. Теперь уже нельзя двигаться с шагом 1, поэтому возникает гипотеза, что нельзя получить первое простое число, большее 200. Это действительно так. Первое простое число большее 200, это 211. Покажем сначала, что все числа 201, ..., 210 можно получить 201 = 134⋅1.5 (увеличиваем 134 на 50%)
202 = 101⋅2 (увеличиваем 101 на 100%)
203 = 145⋅1.4 (увеличиваем 145 на 40%)
204 = 102⋅2 (увеличиваем 102 на 100%)
205 = 164⋅1.25 (увеличиваем 164 на 25%)
206 = 103⋅2 (увеличиваем 101 на 100%)
207 = 138⋅1.5 (увеличиваем 138 на 50%)
208 = 104⋅2 (увеличиваем 104 на 100%)
209 = 190⋅1.1 (увеличиваем 190 на 10%)
210 = 105⋅2 (увеличиваем 105 на 100%)

Теперь покажем, что 211 нельзя получить. Напомним, что все числа от 1 до 210 включительно мы получили. Пусть теперь, увеличив число n на m%, получилось 211. Тогда n⋅(1+m/100)=211, причем 106≤n≤210, 1≤m≤100. Отсюда следует, что n⋅(100+m)=211⋅100=211⋅2⋅2⋅5⋅5. Так как 211 простое, то хотя бы одно из чисел n, m+100 больше 211, противоречие.

Ответ: 211.