Let $p$ and $q$ be given prime numbers and $S$ be a subset of ${1,2,3,\dots ,p-2,p-1}$. Prove that the number of elements in the set $A=\{ (x_1,x_2,…,x_q ):x_i\in S,\sum_{i=1}^q x_i \equiv 0(mod\: p)\}$ is multiple of $q$.
Problem
Source: XI International Festival of Young Mathematicians Sozopol 2022, Theme for 11-12 grade
Tags: number theory
09.09.2022 18:19
Very nice. I prove this by inducting on $|S|$. Base case, $|S|=1$. If $S=\{a\}$ for some $1\le a\le p-1$, then clearly $|A|=0$ since $(a,\dots,a)$ does not satisfy the condition ($(p,q)=1$). Inductive hypothesis. Suppose the assertion is true for all $S'$ with $|S'|=n$, $n\ge 1$. Consider $S=S'\cup \{a\}$. Also, let $A'=\{(x_1,\dots,x_q):x_i\in S',\textstyle \sum_i x_i\equiv 0\pmod{q}\}$. Note that $|S|-|S'|$ is precisely the number of all $(x_1,\dots,x_q)$ with at least one $a$ such that $\textstyle\sum_i x_i \equiv 0\pmod{q}$. For any $1\le \ell \le q-1$, denote by $M_\ell$ the number of all $(x_1,\dots,x_{q-\ell})$ with $\textstyle \sum_{1\le i\le q-\ell}x_i\equiv 0\pmod{q}$. Using $\ell$ as the parameter counting the number of $i$ with $x_i=q$, we thus get \[ |S|-|S'|=\sum_{1\le \ell \le q-1}\binom{q}{\ell}M_\ell, \]where the first binomial term is for choosing $\ell$ spots (out of $q$) for $a$. As $q\mid \textstyle \binom{q}{\ell}$ for $1\le \ell\le q-1$ (we used the primality of $q$), we complete the proof since $q\mid |S'|$.
20.09.2022 02:55
Easier than it seems. Suppose there are $k$ distinct $x$-s in a tuple. If $k=1$, then $qx_1 = 0 (mod p)$ and so $p \mid x_1$, contradicting the given assumptions. For $k\geq 2$ there are $\frac{q!}{a_1!a_2!\cdots a_k!}$ tuples and this is a multiple of $q$, done.