Задача 60433

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

Сложность: 3 Классы: 8,9,10 Название задачи: Двоечники.

Условие

В классе имеется a₁ учеников, получивших в течение года хотя бы одну двойку, a₂ учеников, получивших не менее двух двоек, ..., a_k учеников, получивших не менее k двоек. Сколько всего двоек в этом классе? (Предполагается, что ни у кого нет более k двоек.)

Решение 1

Количество учеников, получивших ровно одну двойку, равно  a₁ – a₂,  ровно две двойки –  a₂ – a₃,  и т. д. Поэтому общее количество двоек равно
(a₁ – a₂) + 2(a₂ – a₃) + 3(a₃ – a₄ ) + ... + (k – 1)(a_k–1 – a_k) + ka_k = a₁ + (2a₂ – a₂) + (3a₃ – 2a₃) + (ka_k – (k–1)a_k) = a₁ + a₂ + ... + a_k.

Решение 2

Занумеруем двойки каждого ученика в порядке их получения. Тогда a₁ – количество первых двоек, a₂ – количество вторых двоек, и т. д. Значит, количество всех двоек равно  a₁ + a₂ + ... + a_k.

  Замечание. Искушённый читатель сразу заметит здесь переход от диаграммы Юнга к симметричной.

Ответ

a₁ + a₂ + ... + a_k.

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

книга
Автор	Алфутова Н.Б., Устинов А.В.
Год издания	2002
Название	Алгебра и теория чисел
Издательство	МЦНМО
Издание	1
глава
Номер	2
Название	Комбинаторика
Тема	Комбинаторика
параграф
Номер	4
Название	Формула включений и исключений
Тема	Формула включения-исключения
задача
Номер	02.099