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

$n\ge 1$ бүтін саны мен $S=\left\{ 1,2,\ldots ,n \right\}$ жиыны берілген. $S$ жиынының бос емес ішкі $T$ жиыны үшін $f(T)$ арқылы $f\left( T \right)=\frac{1}{n+m-M}$ санын белгілейік, бұл жерде $m$ және $M$ сандары \mbox{$T$-ның} сәйкесінше ең кіші және ең үлкен элементтері. ${{A}_{1}},{{A}_{2}},\ldots ,{{A}_{k}}$ арқылы $S$ жиынының барлық бос емес ішкі жиындарын белгілейік. $f\left( {{A}_{1}} \right)+f\left( {{A}_{2}} \right)+\ldots +f({{A}_{k}}$) қосындысын табыңыз.

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

Решение: Рассмотрим кол во подмножеств, когда 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}$