Городская олимпиада по математике среди физ-мат школ г. Алматы

Пусть задано множество $\{1, 2,\ldots,n\}$. Из этого множества выбрали $2n - 1$ (не обязательно попарно различных) двухэлементных подмножеств. Докажите, что всегда можно удалить $(n-1)$ из этих подмножеств так, что объединение оставшихся подмножеств будет содержать не более $\frac{2n}{3}+1$ различных элементов.

Комментарий/решение

Постройм граф где элементы 1,2,3,...,n это соответствено n вершины, где ребра это подмножества. Тогда задача сводиться к тому что мы должны удалить n-1 ребер так чтобы оставшиеся ребра покрывали не более $\frac{2n}{3}+1$ вершин. Пусть после j удалений осталось n-j вершин и $e_{j}$ ребер. Пусть $l_{j}$=(2n-1)-$e_{j}$- число потерянных ребер.

Докажем что $l_{j}$$\le$3j при всех j$\le$t.

Тогда минимальная степень d вершины которую мы удалим не больше чем общего среднего:

$d\le \frac{2e_j}{n-j}$

$l_{j+1}=l_j+d$

Разберем два случая:

Случай 1: $l_j$$\ge$ 2j

$e_j\le 2n-1-2j=2(n-j)-1$

$d\le \frac{2e_j}{n-j}<4$

$l_{j+1}=l_j+d\le 3(j+1)$

Случай 2: $l_j$$\le$ 2j-1

$l_{j+1}\le l_j+\frac{2(2n-1-l_j)}{n-j}$

$1-\frac{2}{n-j}>0$

$l_{j+1}\le (2j-1)+\frac{2(2n-2j)}{n-j}=2j+3\le 3(j+1)$

Тогда:

$3t=3\lceil n/3\rceil-3\le (n+2)-3=n-1$

$(2n-1)-(n-1)=n$

$n-t=n-\lceil n/3\rceil+1\le \frac{2n}{3}+1$

$\blacksquare$