Человек имеет 10 друзей и в течение нескольких дней приглашает некоторых из них в гости так, что компания ни разу не повторяется (в какой-то из дней он может не приглашать никого). Сколько дней он может так делать?

   Решение

Темы:    [ Последовательности (прочее) ] [ Простые числа и их свойства ] [ Произведения и факториалы ] [ Примеры и контрпримеры. Конструкции ] [ Индукция (прочее) ]

Сложность: 4 Классы: 10,11

Прислать комментарий

Условие

Все натуральные числа выписали в ряд в некотором порядке (каждое число по одному разу). Обязательно ли найдутся несколько (больше одного) чисел, выписанных подряд (начиная с какого-то места), сумма которых будет простым числом?

Решение

  Покажем как записать натуральные числа в бесконечную последовательность, где таких "простых сумм" нет.
  Возьмём  a₁ = 1,  a₂ = 3.  Пусть конечная последовательность a₁, a₂, ..., a_n  (n > 1)  без "простых сумм" уже построена, и m – наименьшее натуральное число, которое не является ее членом. Положим  S = a₁ + a₂ + ... + a_n + m,  a_n+1 = S!,  a_n+2 = m.  Полученная последовательность a₁, ..., a_n+2 также не содержит "простых сумм". Действительно, любая сумма, содержащая слагаемое a_n+1, равна  S! + k,  где  1 < k ≤ S,  и не является простым числом, поскольку делится на k.
  Продолжая такое построение по индукции, мы получим бесконечную последовательность. Из построения очевидно, что каждое натуральное число попадает в эту последовательность ровно один раз.

Замечания

8 баллов

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