на доске написаны все натур числа от 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.