2014-06-08
Пусть M – подмножество множества всех пар натуральных чисел $i < k$, не превосходящих заданного натурального числа $n \geq 2$. При этом, если пара $i < k$ принадлежит множеству M, то никакая пара $k < m$ ему не принадлежит. Какое наибольшее число пар может быть в множестве М?
Решение:
Обозначим через А и В множества всех меньших и соответственно больших чисел, из которых состоят пары множества М. Тогда по условию задачи ни один элемент из В не содержится в множестве А, а значит, $A \bigcap B = \varnothing$. Пусть количества элементов множеств А и В равны а и b соответственно. Тогда $a + b \leq n$, и в любой паре из М меньший элемент может принимать не более чем а значений, а больший – не более чем b значений. Поэтому число элементов в М не превосходит числа
$ab \leq a(n-a) \leq ((a+n-a)/2)^{2} = n^{2}/4$.
Так как $ab \in Z$, то $ab \leq [n^{2}/4]$. Если число я четное, то наибольшее количество элементов в множестве М достигается в случае
$M = \{ (j;l) | j \leq n/2; l >n/2 \}$
(тогда М состоит из $n^{2}/4$ элементов). Если же число я нечетное, то достаточно взять
$M = \{ (j;l) | j < n/2; l >n/2 \}$
(тогда М состоит из
$\frac{n-1}{2} \cdot \frac{n+1}{2} = \frac{n^{2}}{4} - \frac{1}{4} = \left [ \frac{n^{2}}{4} \right ]$
элементов). Таким образом, и в случае четного, и в случае нечетного $n$ наибольшее возможное количество элементов в множестве М равно $[n^{2}/4]$.