|
|
 |
Условие
Имеется много карточек, на каждой из которых записано натуральное число от 1 до n. Известно, что сумма чисел на всех карточках равна n!·k, где k – целое число. Докажите, что карточки можно разложить на k групп так, чтобы в каждой группе сумма чисел, записанных на карточках, равнялась n!.
Решение 1
Индукция. База (n = 1) очевидна.
Шаг индукции. Перевернём карточки, на которых написано число n, и на обороте каждой напишем единицу. Из оставшихся карточек возьмём любые n. Согласно задаче 60673 из них можно выделить группу карточек, сумма чисел на которых кратна n. Сложим карточки этой группы в пачку и напишем на пачке эту сумму, уменьшенную в n раз. Заметим, что эта число не превосходит n – 1. Будем продолжать этот процесс, пока карточки не кончатся или не останется менее n карточек. В последнем случае сумма чисел на оставшихся карточках также кратна n и их тоже можно сложить в пачку. Сумма чисел, написанных на пачках, равна (n – 1)!·k. По предположению индукции их можно разложить на группы с суммой (n – 1)!. Теперь сумма чисел, изначально написанных на карточках каждой группы, равна n!.
Решение 2
Достаточно рассмотреть случай k ≥ 2, n ≥ 2. Поскольку (n – 2)(1 + 2 + ... + n) < 2n!, карточек с каким-то числом (пусть с m) не меньше n – 1. Отложим n – 1 из этих карточек. Из оставшихся карточек возьмём любые m. Согласно задаче 60673 из них можно выделить группу карточек с суммой, кратной m. Свяжем карточки этой группы в пачку. Сумма пачки не превосходит mn. Так будем продолжать связывать пачки, пока не останется менее m карточек. Их сумма тоже кратна m, свяжем и их в пачку.
Будем по одной складывать пачки в кучу, пока сумма чисел в куче не превысит n!. Убрав из кучи последнюю пачку, мы оставим в ней сумму, равную
n! – lm, где 0 ≤ l ≤ n – 1. Недостаток lm можно дополнить, взяв l отложенных карточек.
Итак, получена куча с суммой n!. С оставшимися карточками процесс можно повторить.
Замечания
баллы: 8-9 кл. – 9, 10-11 кл. – 8
