Олимпиадная задача: максимальное число сторон пересечения n кругов — теория множеств, комбинаторика

   Занумеруем круги числами от 1 доn. Нумерация сторон Ф представляет собой круговую расстановку этих чисел (с повторениями), удовлетворяющую след. условиям:       а) два одинаковых числа не стоят рядом;       б) нет фрагментов вида ...a...b...a...b... .    Действительно, рассмотрим две дугиAB, ограничивающие пересечение круговaиb. Если взять две точкиA₁иA₂на одной из них (принадлежащей границе кругаa) и две точкиB₁иB₂– на другой, то хордыA₁A₂иB₁B₂, очевидно, не пересекаются.    Индукцией поnдокажем, что длинаlтакой расстановки не превосходит  2n– 2.    База (n= 2)  очевидна.    Шаг индукции. Если все числа встречаются не более одного раза, то все в порядке:  n≤ 2n– 2.    Пусть одно из чисел (a) встретилось  k> 1  раз. Разорвем расстановку в этих местах и из каждой части составим свою расстановку, "склеив" концы. Все они удовлетворяют указанным условиям, значит, длина  l_i i-й расстановки не больше  2n_i– 2.  Кроме того, в этих расстановках нет общих чисел, отличных отa. Поэтому, сложив, получим  l≤ 2(n+k– 1) – 2k= 2n– 2.    Расстановки длины  2n– 2  существуют, например,  1, 2, ...,n–1,n,n–1, ..., 2  или  1,n, 2,n, ...,n–1,n. Нетрудно построить примеры фигур Ф, соответствующих этим расстановкам.

2n – 2 стороны.