Din nou teoria aditiva

[Filip Chindea]

Fixam intregii relativ primi \( m, n \ge 1 \) si \( s \in \mathbb{Z} \).
Sa se determine numarul de submultimi \( A \subseteq \{1, 2, ..., m + n - 1\} \) cu \( |A| = m \) si \( \sum_{x \in A} x \equiv s \pmod{n} \).

[TST IV 2008, Problema 2]

[Filip Chindea]

"Sketch" de solutie:
In continuare voi considera numai congruente \( \pmod{n} \).
Fie \( a, b \in \mathbb{N}^{\ast} \) cu \( am - bn = 1 \).
Priviti submultimile respective ca functii strict crescatoare \( f : \overline{1, m} \rightarrow \overline{1, m + n - 1} \). Fie \( A_s \) multimea acestor functii care satisfac \( \sum_{x \in \overline{1, m}} f(x) \equiv s \), \( B_s \) setul functiilor crescatoare \( f : \overline{1, m} \rightarrow \overline{1, n} \) cu \( \sum_{x \in \overline{1, m}} f(x) \equiv s - \frac{m(m-1)}{2} \), iar \( C_s \) multimea functiilor crescatoare \( f : \overline{1, m} \rightarrow \overline{1 + a, n + a} \) satisfacand aceeasi relatie.
Construiti bijectii intre oricare doua multimi din secventa urmatoare, \( \forall s \in \mathbb{Z} \):

\( A_s, B_s, C_{s + 1}, B_{s + 1} \) si \( A_{s + 1} \).

Singura parte mai "problematica" se solutioneaza astfel: pt. \( f \in C_{s + 1} \), consideram unicele \( a_x \in \overline{1, n} \), cu \( a_x \equiv f(x) \), pentru orice \( x \in \overline{1, m} \). Astfel am ales unica \( g \in B_{s + 1} \) cu proprietatea ca are loc egalitatea de multiseturi \( \mathrm{Im}(g) = \{a_x \ : \ x \in \overline{1, m}\} \).

In concluzie avem bijectie intre \( A_s, A_{s+1} \), de unde concluzia \( |A_1| = \cdots = |A_n| = \frac{1}{n} {m + n - 1 \choose m} \).