Задача 67587
|
|
 |
Условие
В ряд слева направо стоят коробки с номерами 1, 2, 3, … В них по очереди кладут числа 1, 2, …, 2025. В каждой коробке каждые два числа должны быть взаимно просты. Очередное число кладётся в самую левую из разрешённых коробок. Все числа разложили.а) Сколько чисел попало во вторую коробку?
б) Сколько чисел попало в третью коробку?
Решение
В первую коробку, очевидно, попадёт единица и все простые числа, меньшие 2025, а составные числа туда попасть не могут.Во вторую коробку не может попасть число, делящееся на два различных простых, так как квадрат меньшего из этих простых попал бы сюда раньше. Поэтому в эту коробку попадут в точности квадраты простых чисел, не превышающие $2025=45^2$. Это числа $2^2$, $3^2$, $5^2$, …, $43^2$. Их 14.
В третью коробку попадут следующие попарные произведения последовательных простых чисел: $2\cdot3$, $5\cdot7$, $11\cdot13$, $17\cdot19$, $23\cdot29$, $31\cdot37$, $41\cdot43$. Докажем это. Число 6 туда попадает, пусть там уже лежат числа $p_1p_2$, $p_3p_4$, …, $p_{2k-1}p_{2k}$, и следующим туда попадает число $A$.
В разложении $A$ участвуют простые числа, не меньшие $p_{2k+1}$. Число $p_{2k+1}^2$ попадёт во вторую коробку, так что $A$ равно либо $p_{2k+1}^3$, либо $p_{2k+1}p_{2k+2}$. Заметим, что для простых чисел, меньших 50, $p_{2k+1}^3>p_{2k+1}p_{2k+2}$. Действительно, это неравенство равносильно неравенству $p_{2k+1}^2>p_{2k+2}$, но $5^2>7$, а $7^2$ уже больше даже $47$. Поэтому $A=p_{2k+1}p_{2k+2}$.
