Выбрано 2 задачи 
Убрать все задачи
Команда из n школьников участвует в игре: на каждого из них надевают шапку одного из k заранее известных цветов, а затем по свистку все школьники одновременно выбирают себе по одному шарфу. Команда получает столько очков, у скольких её участников цвет шапки совпал с цветом шарфа (шарфов и шапок любого цвета имеется достаточное количество; во время игры каждый участник не видит своей шапки, зато видит шапки всех остальных, но не имеет права выдавать до свистка никакую информацию). Какое наибольшее число очков команда, заранее наметив план действий каждого её члена, может гарантированно получить:
а) при n = k = 2;
б) при произвольных фиксированных n и k?
В ящиках лежат камни. За один ход выбирается число k, затем камни в ящиках делятся на группы по k штук и остаток менее, чем из k штук. Оставляют по одному камню из каждой группы и весь остаток. Можно ли за пять ходов добиться, чтобы в ящиках осталось ровно по одному камню, если в каждом из них
а) не более 460 камней;
б) не более 461 камня?
|
|
 |
Условие
В ящиках лежат камни. За один ход выбирается число 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 пробелов подряд заменялась на один пробел.
