Профессор Тарантога в статье о сепульках дал $n$ определений сепуления. Аспиранты профессора постепенно доказали, что все эти определения эквивалентны. Каждый из аспирантов защитил диссертацию на тему: «Сепуление в смысле $i$-го определения является сепулением в смысле $j$-го определения». Какое максимальное количество аспирантов могло быть у Тарантоги, если диссертации защищались последовательно и основной результат очередной диссертации не следовал из ранее защищённых?
Обозначим определения, данные Тарантогой, через $S_i$ ($i=1$, $\ldots$, $n$). Будем утверждение «сепуление в смысле $S_i$ является сепулением в смысле $S_j$» обозначать так: $S_i\to S_j$. (Можно представлять себе $S_i$ как «множество всех сепулений по $i$-му определению», тогда $S_i\to S_j$ будет означать, что $S_i$ содержится в $S_j$.) Ясно, что результат $S_i\to S_j$ будет следовать из ранее защищённых, только если уже защищена цепочка диссертаций, ведущая из $S_i$ в $S_j$ (см. рисунок).
Назовём парой две диссертации $S_i\to S_j$ и $S_j\to S_i$. Покажем, что защищённые пары не могут образовывать цикла. Действительно, если имеется цикл $S_i\leftrightarrows S_j\leftrightarrows\ldots\leftrightarrows S_k\leftrightarrows S_i$, то последняя по времени защищённая диссертация этого цикла следует из остальных.
Докажем теперь по индукции, что всего могло быть защищено не более $n-1$ пар. Для $n=2$ всё очевидно. Предположим, что было защищено $n$ пар. Пусть какое-либо $S_i$ входит не более чем в одну защищённую пару. Тогда в оставшихся $n-1$ парах участвуют $n-1$ определений, чего не может быть по предположению индукции. Значит, любое $S_i$ входит по крайней мере в две пары. Но тогда можно построить цепочку $S_i\leftrightarrows S_j\leftrightarrows\ldots\leftrightarrows S_k\leftrightarrows S_i$, которая замкнётся не позднее $n$-го шага. Противоречие (тем самым доказано, что защищённые пары не могут образовывать цикла).
Заметим теперь, что всего имеется $\dfrac{n(n-1)}2$ различных пар. Но, по доказанному, только в $n-1$ парах могут быть защищены обе диссертации. Значит, в каждой из оставшихся $\dfrac{n(n-1)}2-(n-1)$ пар может быть защищена только одна диссертация. Таким образом, у профессора Тарантоги было не более
$$2(n-1)+\left[\dfrac{n(n-1)}2-(n-1)\right]=\dfrac{n(n+1)}2-1$$
аспирантов.
Покажем теперь, как можно защитить такую уйму диссертаций. Сначала $n-1$ аспирантов защищают диссертации $S_1\to S_n$; $S_2\to S_n$; $\ldots$; $S_{n-1}\to S_n$. Затем $n-2$ аспирантов защищают диссертации $S_1\to S_{n-1}$; $S_2\to S_{n-1}$; $\ldots$; $S_{n-2}\to S_{n-1}$; $\ldots$; и т. д.
Наконец ещё один аспирант защищает диссертацию $S_1\to S_2$.
Последние $n-1$ аспирантов последовательно защищают диссертации $S_n\to S_{n-1}$; $S_{n-1}\to S_{n-2}\ldots S_2\to S_1$. Итак, всего защищено $\dfrac{n(n-1)}2+n-1=\dfrac{n(n+1)}2-1$ диссертаций.
Легко проверить, что ни одна диссертация не следует из ранее защищённых. Вместе с тем доказана эквивалентность всех определений, так как защищены диссертации $S_1\to S_n$; $S_n\to S_{n-1}$; $\ldots$; $S_2\to S_1$.
