ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 107998
Темы:    [ Деление с остатком ]
[ Индукция (прочее) ]
[ Монотонность и ограниченность ]
Сложность: 5-
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

В ящиках лежат камни. За один ход выбирается число k, затем камни в ящиках делятся на группы по k штук и остаток менее, чем из k штук. Оставляют по одному камню из каждой группы и весь остаток. Можно ли за пять ходов добиться, чтобы в ящиках осталось ровно по одному камню, если в каждом из них
  а) не более 460 камней;
  б) не более 461 камня?

Решение

  Заметим, что если выбрано число k, то после хода в ящике, в котором было m камней, будет  q + r  камней, где q и r – частное и остаток от деления m на k соответственно.
  Ясно, что достаточно рассмотреть ситуацию, когда в первом ящике лежит 1 камень, во втором – 2 камня и т. д. вплоть до n-го ящика, в котором лежит n камней (где  n = 460 или 461).

  1) Пусть в ящиках лежат 1, 2, ..., n камней. Пусть выбрано число k и сделан ход а  f(n, k)  – максимальное число камней в ящике (после хода). Тогда для любого числа камней j,  1 ≤ j ≤ f(n, k)  найдётся ящик, в котором лежит j камней. Иначе говоря, числа камней в ящиках снова будут образовывать начальный отрезок натурального ряда.
  Докажем это обратной индукцией по j. Пусть найдётся ящик с j камнями. Тогда найдётся такое число  m  (1 ≤ m ≤ n),  что  j = q + r,   где q и r – частное и остаток от деления m на k. Если  r ≠ 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 = [n+1/k] + k – 2.

  Обозначим  m = s = [m].

  3) Оптимальное значение k (при котором  f(n, k)  достигает минимума) равно  s + 1.
  Доказательство.  f(n, k) = [n+1/k + k] – 2.  Функция  n+1/x + x  убывает на интервале    (0, m)  и возрастает на интервале   (m, n].  Так как [x] – неубывающая функция,  f(n, k)  достигает минимума либо при  k = s,  либо при  k = s + 1.
  Осталось доказать, что  f(n, s + 1) < f (n, s), то есть что  [n+1/s+1] < [n+1/s].
  Из неравенства  s² ≤ n + 1 < (s + 1)²  следует, что  [n+1/s+1] ≤ s,  а [n+1/s] ≥ s.  Значит, достаточно доказать, что обе части не могут равняться s. Но
[n+1/s] = s  ⇒  n+1/s < s + 1  ⇒   n+1/s+1 < s  ⇒  [n+1/s+1] < s.

  4) Пусть  g(n) = f(n, s + 1).  Тогда, начиная с ящиков с 1, 2, ..., n камнями, мы при оптимальном выборе k (за один ход) получим ящики с 1, 2, ..., g(n) камнями.

  Осталось убедиться прямым вычислением, что  g(g(g(g(g(460))))) = 1,  а g(g(g(g(g(461))))) = 2.
  Последовательность ходов для  n = 460  приведена в таблице:


  Если же в ящиках содержатся все наборы камней от 1 до 461, то после первого хода останутся, по крайней мере, все наборы от 1 до
g(461) = f(461, 22) = 41;  после второго – все наборы от 1 до g(41) = 11; затем – от 1 до 5; от 1 до 3; и, наконец, от 1 до 2. Итак, при  n = 461  не всегда можно оставить по одному камню во всех ящиках.

Замечания

1. Вместо того чтобы доказывать неравенство  f(n, s + 1) ≤ f(n, s),  можно было бы просто перебрать различные варианты.

2. Задача возникла у программистов. Обрабатывался текст, содержащий более одного пробела между некоторыми словами. Нужно было так обработать текст, чтобы оставить между словами ровно один пробел. При этом применялась следующая операция: выбиралось число k и при последовательном просмотре текста каждая группа из k пробелов подряд заменялась на один пробел.

Источники и прецеденты использования

олимпиада
Название Московская математическая олимпиада
год
Номер 56
Год 1993
вариант
Класс 11
задача
Номер 4

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .