Олимпиадная задача по теории чисел для 8–11 классов от Доценко В. В.

Решение 1:   Индукция. База  (n = 1)  очевидна.

  Шаг индукции. Перевернём карточки, на которых написано число n, и на обороте каждой напишем единицу. Из оставшихся карточек возьмём любые n. Согласно задаче 160673 из них можно выделить группу карточек, сумма чисел на которых кратна 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!. С оставшимися карточками процесс можно повторить.

Ответ задачи отсутствует