Олимпиада Туймаада по математике. Старшая лига. 2013 год

Карточки с номерами от 1 до $2^n$ раздают $k$ детям, $1\leq k\leq 2^n$, так чтобы каждый ребенок получил хотя бы одну карточку. Докажите, что количество способов раздать карточки делится на $2^{k-1}$, но не делится на $2^k$. ( М. Иванов )

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

Неполное решение (может вообще неправильно):

Пусть $s_i \geq 1$ количество карт у ребенка $i$. Количество способов раздать карточки должно быть равно:

$$\sum_{(s_1\ ,\ \dots \ ,\ s_k)} \dfrac{(2^n)!}{s_1!\ s_2!\ \dots \ s_k!}$$

Утверждение:

$$ v_2\left(\dfrac{(2^n)!}{s_1!\ s_2!\ \dots \ s_k!}\right) \geq k-1$$

С равенством когда все $s_i$- степени точки 2.

Доказательство:

$$ v_2\left(\dfrac{(2^n)!}{s_1!\ s_2!\ \dots \ s_k!}\right)=\sum_{1\leq j\leq n}\left(\left[\dfrac{2^n}{2^j}\right] -\sum_{1\leq i\leq k}\left[\dfrac{s_i}{2^j}\right] \right)=\sum_{1\leq j\leq n}\sum_{1\leq i\leq k}\left(\dfrac{s_i}{2^j}-\left[\dfrac{s_i}{2^j} \right] \right)$$

Достаточно доказать что:

$$\sum_{1\leq j\leq n}\left(\dfrac{s}{2^j}-\left[\dfrac{s}{2^j} \right] \right) \geq \left\{\begin{gathered} 1,~1\leq s\neq 2^x \\ 1-\dfrac{s}{2^n},~1\leq s=2^x\end{gathered}\right.$$

Пусть $t \in \mathbb{N}$ наименьшее такое что $s~\vdots ~ 2^{n-t}$:

$$\sum_{1\leq j\leq n}\left(\dfrac{s}{2^j}-\left[\dfrac{s}{2^j} \right] \right)=\sum_{n-t+1\leq j\leq n}\left(\dfrac{s}{2^j}-\left[\dfrac{s}{2^j} \right] \right)=\sum_{n-t+1\leq j\leq n}\left\{ \dfrac{s}{2^j} \right\} \geq \dfrac{c_1}{2^1}+\dots+\dfrac{c_t}{2^t}$$

для каких то натуральных $c$.

Легко убедится что $c_t=1\Leftrightarrow s=2^{n-t}$. Получаем:

$$\sum_{n-t+1\leq j\leq n}\left\{ \dfrac{s}{2^j} \right\} \geq \dfrac{1}{2^1}+\dots+\dfrac{1}{2^t}=1-\dfrac{1}{2^t}=1-\dfrac{s}{2^n}$$

Если $c_t \geq 2$ то:

$$\sum_{n-t+1\leq j\leq n}\left\{ \dfrac{s}{2^j} \right\} \geq \dfrac{1}{2^1}+\dots+\dfrac{2}{2^t}\geq 1$$

Остается доказать что количество решений $(s_1\ ,\ \dots \ ,\ s_k)$ уравнения

$$s_1+ \dots + s_k=2^n$$ где $s_i$ стерени 2 - нечетно.