Число решений

[Sonic86]

Ну да, кажись, идея нормальная: доказать, что k=1.
Если А - не конечное множество и не имеет вид $N\B$, где В - конечное, то есть бесконечно много элементов, как принадлежащих, так и не принадлежащих А. Тогда это верно при $n > N$ при любом N.
Рассматриваем уравнение $x_1+...+x_k=ka$. Рассматриваем всевозможные перестановки компонент решения - множество решений разбивается на классы, которые не изменяются при всех перестановках. Если $r_1, ..., r_k$ - количества одинаковых $x_j, 1 \leq x_j \leq k$, то мощность класса будет равна $\frac{k!}{r_1! ... r_k!}$, причем $r_1 + ... + r_k = k$. Если $a \in A$, то уравнение $x_1+...+x_k=ka$ имеет решение (a,a,...,a) - оно не меняется при перестановках, значит его класс имеет мощность 1. Если же $a \not \in A$, то уравнение $x_1+...+x_k=ka$ не будет иметь решения (a,a,...,a). Обозначим число остальных решений уравнения для $a \in A$ буквой $S_1$, а для $a \not \in A$ - буквой $S_2$. Так как число решений - одно и то же, то $m=1+S_1 = S_2$. Рассмотрим все остальные решения. Для них $r_j < k$, значит сумма произведений мощностей остальных классов (как для $S_1$, так и для $S_2$) на количества этих классов будет делится на $d_k = НОД(\frac{k!}{r_1! ... r_k!})$, где $0 \leq r_j < k, r_1+...+r_k = k$. Но $d_k >1$, значит из $m=1+S_1 = S_2, d_k | S_i$ получаем противоречие: $d_k |1$.
Докажем, что $d_k >1$ напрямую.
Пусть $k=p_1^{\alpha_1}...p_t^{\alpha_t}>1$, рассмотрим простое $p:p|k$ и найдем $ord_p(d_k) = ord_p(k!)- \sum\limits_{j=1}^k ord_p(r_j!)$. Пусть $ord_p(k)= s$, тогда $ord_p(r_j) \leq s$, тогда
$k=b_sp^s+b_{s-1}p^{s-1}+...+b_1p+b_0$
$r_j=a_{j,s}p^s+a_{j,s-1}p^{s-1}+...+a_{j,1}p+a_{j,0}$
Тогда $\sum\limits_{j=1}^k (a_{j,s}p^s+a_{j,s-1}p^{s-1}+...+a_{j,1}p+a_{j,0}) = b_sp^s+b_{s-1}p^{s-1}+...+b_1p+b_0$
С помощью формулы для $ord_p(A!)$ получаем, что
$ord_p(k!) = \frac{k - 1}{p-1}$
$\sum\limits_{j=1}^k ord_p(r_j!) = \frac{1}{p-1}\sum\limits_{j=1}^k (a_{j,s}(p^s-1)+...+a_{j,1}(p-1)) =$
$= \sum\limits_{j=1}^k ord_p(r_j!) = \frac{1}{p-1} \sum\limits_{j=1}^k \( (a_{j,s}p^s+...+a_{j,0} - (a_{j,s}+...+a_{j,0})) \) =$
$= \sum\limits_{j=1}^k ord_p(r_j!) = \frac{k - R}{p-1}$.
Таким образом, $ord_p(d_k) = ord_p(k!)- \sum\limits_{j=1}^k ord_p(r_j!) \Leftrightarrow \frac{k-1}{p-1} = \frac{k-R}{p-1}$
$\Leftrightarrow R=1$. Это означает, что какое-то $r_j$ - степень р, а остальные равны нулю, значит $r_j = k$, что уже исключено.