Юниорская олимпиада по математике. Заключительный этап. 2019-2020 учебный год. 8 класс.

Дано целое число $n\ge 1$ и множество $S=\left\{ 1,2,\ldots ,n \right\}$. Для непустого подмножества $T$ множества $S$, определим $f\left( T \right)=\frac{1}{n+m-M},$ где $m$ и $M$ соответственно наименьший и наибольший элементы $T$. Пусть ${{A}_{1}},{{A}_{2}},\ldots ,{{A}_{k}}$ — все непустые подмножества множества $S$. Найдите сумму $f\left( {{A}_{1}} \right)+f\left( {{A}_{2}} \right)+\ldots +f\left( {{A}_{k}} \right)$.

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

Решение: Рассмотрим кол во подмножеств, когда 1 - наименьшее, n -наибольшее, то есть m-M = 1-n. Их $2^{n-2}$, так как

{2, 3, ..., n-1} каждое из этих чисел либо идет в наше множество либо не идет отсюда $2^{n-2}$. Тогда кол во чисел вида $\frac{1}{n+1-n}$ будет $2^{n-2}$. Теперь кол во чисел где m-M=2-n. Тут 2 варианта либо m=1, M=n-1, либо m=2, M=n. Тогда будет $2^{n-3} * 2$ варианта для числа $\frac{1}{n+2-n}$. Теперь для m-M=3-n. Тут 3 варианта либо m=1, M=n-2, либо m=2, M=n-1, либо m=3, M=n. Тогда будет $2^{n-4} * 3$ варианта для числа $\frac{1}{n+3-n}$. А значит вся сумма будет выглядеть так $$2^{n-2} * \frac{1}{n+1-n} + 2^{n-3} * 2 * \frac{1}{n+2-n} + 2^{n-4} * 3 * \frac{1}{n+3-n} + ... + 2^{n-(n-1)} * (n-2) * \frac{1}{n+n-2-n} + 2^{n-(n)} * (n-1) * \frac{1}{n+n-1-n} = 2^{n-2} + 2^{n-3} + ... + 2 + 1 = 2^{n-1} - 1$$ .

Теперь остались случаи когда только одно число в множестве и таких случаев ровно n, получается

$n* \frac{1}{n+m-m}=1$

Поэтому ответ $2^{n-1}$