Стойност на добри числа

[aifC]

Нека [tex]X[/tex] е произволно избрано подмножество на [tex]\{1, 2,...,2017\}[/tex].Ще казваме, че положителното число [tex]n[/tex] e "добро", ако и двете [tex]n[/tex], [tex]n+|X|[/tex] са елементи на [tex]X[/tex].Намерете очакваната стойност на добрите числа.

[aifC]

Предполагаме че [tex]n[/tex] e добро число по отношение на множеството [tex]X[/tex] с [tex]k[/tex] елементи, и тези елементи са произволно избрани от множеството [tex]\{1,2...,N\}[/tex].Тогава [tex]n, n+k \in X[/tex] и така можем да приложим две ограничения на стойностите на [tex]k[/tex]: [tex]k \ge 2[/tex] и [tex]k \le N - n[/tex]. Оставащите [tex]k-2[/tex] елемента от [tex]X[/tex], могат да бъдат избрани от останалите [tex]N - 2[/tex]. По този начин за всяко фиксирано [tex]n[/tex] ще имаме:

[tex]{N-2 \choose 0} + {N-2 \choose 1}+...+{N-2 \choose N-2-n}[/tex] множества, такива че [tex]n[/tex] е добро число. Обобщавайки всички възможни стойности на [tex]n[/tex]:

[tex]S = (N-2){N-2 \choose 0} + (N-3){N-2 \choose 1}+...+{N-2 \choose N-3}[/tex]
Прилагаме идентичността: [tex]{m \choose r} = {m \choose m-r}[/tex]

[tex]\implies S = (N-2){N-2 \choose N-2} + (N-3){N-2 \choose N-3}+...+{N-2 \choose 1}[/tex]

[tex]2S= (N-2)\left[{N-2 \choose 0} + {N-2 \choose 1}+...+{N-2 \choose N-2}\right] = (N-2)^{N-2}[/tex]

Следователно очакваната стойност на общия брой добри числа е:

[tex]\frac{S}{2^{N}} = \frac{(N-2)2^{N-3}}{2^{N}} = \frac{N-2}{8}[/tex].

В нашия случей [tex]N=2017[/tex], тогава: [tex]\frac{2017-2}{8} = \boxed{251,875}[/tex]