2019-05-26
В ящиках лежат камни. За один ход выбирается число $k$, затем камни в ящиках делятся на группы по $k$ штук и остаток менее, чем из $k$ штук. Оставляют по одному камню из каждой группы и весь остаток. Можно ли за 5 ходов добиться, чтобы в ящиках осталось ровно по одному камню, если в каждом из них а) не более 460 камней; б) не более 461 камня?
Решение:
Заметим, что если выбрано число $k$, то после хода в ящике, в котором было $m$ камней, будет $q+r$ камней, где $q$ и $r$ - частное и остаток от деления $m$ на $k$ соответственно.
Ясно, что достаточно рассмотреть ситуацию, когда в первом ящике лежит 1 камень, во втором - 2 камня и т. д. вплоть до $n$-го ящика, в котором лежит $n$ камней (где $n = 460$ в пункте «а» и $n = 461$ в пункте «б»).
1. Пусть в ящиках лежат $1, 2, \cdots, n$ камней, где $n$ - некоторое натуральное число. Пусть выбрано число $k$ и сделан ход. Пусть $f(n, k)$ - максимальное число камней в ящике (после хода). Тогда для любого числа камней $1 \leq j \leq f(n, k)$ найдется ящик, в котором лежит $j$ камней. Иначе говоря, числа камней в ящиках снова будут образовывать начальный отрезок натурального ряда. Докажем это обратной индукцией по $j$. Пусть найдется ящик с $j$ камнями. Тогда найдется такое число $m (1 \leq m \leq n)$, что $j=q+r$, где $q$ и $r$ - частное и остаток от деления $m$ на $k$. Если $r \neq 0$, то в ящике, в котором был $m-1$ камень, станет $j-1$ камень. Если $r=0$, то нужно рассмотреть ящик, в котором было $m-k$ камней. Утверждение доказано.
2. Пусть частное от деления $n+1$ на $k$ равно $q$. Рассмотрим ящик, в котором лежит $(q-1)k+(k-1)$ камней. В нем останется $q+k-2$ камня. Нетрудно видеть, что это будет самый большой ящик (впрочем, если $n+2$ делится на $k$, то будет еще ровно один ящик с таким же числом камней). Итак,
$f(n, k) = q + k - 2 = \left [ \frac{n + 1}{k} \right ] + k - 2$. (1)
3. Оптимальное значение $k$ (при котором $f(n, k)$ достигает минимума) равно $[\sqrt{n+1}]+1$.
Доказательство. Имеем
$f(n, k)= \left [ \frac{n+a}{k} + k \right ] - 2$.
Функция $\frac{n+1}{x}$ убывает на интервале $(0; \sqrt{n+1})$ и возрастает на интервале $(\sqrt{n+1}; n]$. Так как $[x]$ - неубывающая функция, $f(n, k)$ достигает минимума либо при $k = [\sqrt{n+1}]$, либо при $k = [\sqrt{n+1}] + 1$.
Осталось доказать, что всегда
$f(n, [ \sqrt{n+1}]+1) \leq f(n, [\sqrt{n+1}])$.
Пусть $[\sqrt{n+1}] = s$. Тогда
$s^2 \leq n+1 < (s+1)^2$. (2)
В силу (1) достаточно доказать, что
$\left [ \frac{n+1}{s+1} \right ] < \left [ \frac{n+1}{s} \right ]$.
Из (1) следует, что
$\left [ \frac{n+1}{s+1} \right ] \leq s$, а $ \left [ \frac{n+1}{s} \right ] \geq s$.
Значит, достаточно доказать, что обе части не могут равняться $s$. Но
$\left [ \frac{n+1}{s} \right ] = s \Rightarrow \frac{n+1}{s} < s+1 \Rightarrow \frac{n+1}{s+1} < s \Rightarrow \left [ \frac{n+1}{s+1} \right ] < s$.
Утверждение доказано.
4. Пусть
$g(n)=f(n, [\sqrt{n+1}]+1)$.
Тогда, начиная с ящиков с $1, 2, \cdots, n$ камнями, мы при оптимальном выборе $k$ (за один ход) получим ящики с $1, 2, \cdots, g(n)$ камнями. Осталось убедиться прямым вычислением, что $g(g(g(g(g(460)))))=1$, а $g(g(g(g(g(461)))))=2$.
Последовательность ходов для $n = 460$ приведена в таблице:
Изложим рассуждение при $n=461$ более подробно: из доказанного следует, что если в ящиках содержатся все наборы камней от 1 до 461, то после первого хода останутся, по крайней мере, все наборы от 1 до $g(461)=f(461, 22)=41$; после второго - все наборы от 1 до $g(41)=11$; затем - от 1 до 5; от 1 до 3; и, наконец, от 1 до 2. Итак, при $n=461$ не всегда можно оставить 1 камень во всех ящиках.
Ответ: а) Можно; б) нет, не всегда.