На доске написаны все натур числа от 1 до 2042 за 1 ход модно дописать квадрат какого-то числа на доске или НОК 2 чисел на ней. Какое наименьшее составное число нельзя записать на нее

Ответ: 2048 Пояснение - Пусть N = 2042. На доске в один ход можно дописать: - квадрат числа на доске: n^2, где 1 ≤ n ≤ N; - НОК двух чисел на доске: lcm(a, b), где 1 ≤ a, b ≤ N. - Чтобы число m было записано как НОК(a, b) с a, b ≤ N, для каждого простого p в m выполняется неравенствие v_p(m) ≤ floor(log_p N). То есть максимальная возможная степень p в НОК не превосходит floor(log_p N). - Для квадрата: m = n^2 с n ≤ N, значит v_p(m) = 2 v_p(n) ≤ 2 floor(log_p N). - Рассмотрим candidate m = 2048. Это число равно 2^11, то есть имеет единственный простной фактор 2, с экспонентой v_2(2048) = 11. - В НОК двух чисел ≤ N максимальная возможная степень двойки равна floor(log_2 2042) = 10, поэтому 2^11 не может быть получено как НОК(a, b). - Это число не является квадратом: sqrt(2048) ≈ 45.26, не целое. - Все простые множители 2048 (только 2) не превышают N, так что фактор с p > N здесь не появляется. Следовательно 2048 не может быть записано за один ход. - Проверим все composites в промежутке (N, 2N], т.е. 2043, 2044, 2045, 2046, 2047: - 2043 = 9 · 227, и lcm(9, 227) = 2043 (оба ≤ N). - 2044 = lcm(4, 511) = lcm(4, 7·73) = 2044 (или lcm(28, 73)). - 2045 = lcm(5, 409) = 2045. - 2046 = lcm(66, 31) = 2046. - 2047 = lcm(23, 89) = 2047. Все эти пары a, b ≤ 2042, значит данные числа можно дописать на доску за один ход. Таким образом, минимальное составное число, которое нельзя записать на доску за один ход, равно 2048.