Prove that the probabilities that the sum of the elements of the chosen subset is congruent to 0,1,2 mod 3 are equal iff $k\equiv 1,2\mod 3$

Question

A subset of k elements of $\{1,2,\cdots, 2022\}$ is chosen at random. Prove that the probabilities that the sum of the elements of the chosen subset is congruent to 0,1,2 mod 3 are equal iff $k\equiv 1,2\mod 3$.

Generating functions could be useful for counting such sums. Let $\omega$ be a primitive cube root of unity. It could be useful to find a generating function that uses $\omega$ somehow and then find the coefficient of $x^k$ of this function. But I'm not sure how to find the coefficient of $x^k$. Perhaps finding this coefficient in at least 2 different ways could allow for some useful deductions about k?

Answer 1

First, the generating function approach doesn't quite work. The problem is that you don't take into account that the $k$ numbers must be distinct. Here's an alternative: partition $\{1, 2, \ldots, 2022\}$ into the $3$-sets of the form: $$\{1, 2, 3\}, \{4, 5, 6\}, \ldots, \{2020, 2021, 2022\}$$ where each of them is of the form $\{3k-2, 3k-1, 3k\}$, where $1 \leqslant k \leqslant \tfrac{2022}{3}$. For any $k$-subset that you pick, you can get other $k$-subsets by permuting the elements in each partition. For instance, the $5$-subset $\{1, 2, 3, 4, 5, 7\}$ could become $\{1, 2, 3, 5, 6, 9\}$. If your original $k$-subset only contained any of the partitions partially, then you can show that permuting that partition induces a bijection between the subsets with sums $0, 1, 2 \bmod{3}$. For instance, say you pick only $1$ in $\{1, 2, 3\}$. Replacing it with each of $1, 2, 3$ will give you all possible sums modulo $3$ equally.

If $k \equiv 1, 2 \bmod{3}$, then any $k$-subset must choose partially from some partition (every partition has size $3$, so if $k$ was a disjoint union of partitions, then $3 \mid k$), and the above argument shows that the number of subsets with sum of each residue class modulo $3$ are equal.

On the other hand, if $k \equiv 0 \bmod{3}$, the same argument gives you equal number of subsets which have sums $0, 1, 2 \bmod{3}$, with the exception that you must consider the $k$-subsets which are disjoint unions of partitions. Since each partition has sum divisible by $3$, all these $k$-subsets have sum being $0 \bmod{3}$. Thus, you get more subsets with sum $0 \bmod{3}$ than sum $1, 2 \bmod{3}$.

Answer 2

This answer is partial.

Assume that $k>0$, put $n=2022$, and $[n]=\{1,2,\dots,n\}$. Let $\mathcal P$ be the family of all $k$-element subsets of $[n]$. I assume that each of ${n\choose k}$ memebers of $\mathcal P$ have the same probability to be chosen. For each $i\in \{0,1,2\}$ put $$\mathcal P_i=\{A\in\mathcal P:\sum_{a\in A} a\equiv i\pmod 3\}.$$

Suppose that $k$ is not divisible by $3$. For each element $a\in [n]$ put $a'=a+1$, if $a<n$, and $a'=1$, otherwise. For each subset $A$ of $[n]$ put $A'=\{a':a\in A\}$. Then $\sum_{a\in A'} a\equiv k+\sum_{a\in A'} \pmod 3$. For each $i\in \{0,1,2\}$ put $\mathcal P'_i=\{A':A\in\mathcal P_i\}$. Then $\mathcal P'_i=\mathcal P_j$, where $j\equiv i+k\pmod 3$. Since $k\ne 0\pmod 3$, we see that $|\mathcal P_i|$ is the same for each $i$.

Answer 3

Partial answer: IF part

Let $\mathcal{S}_k$ be the random subset chosen and $S_k\in\{0,1,2\}$ be its sum modulo $3$. Then, $$S_k = \sum_{i\in\mathcal{S}_k}i\mod 3 =\sum_{i\in\mathcal{S}_k}(i\mod 3).$$

For $s=0,1,2$, we define $N_s= \left(\sum_{i\in\mathcal{S}_k}\mathbb{1}_{\{i=s\mod 3\}}\right)$. Therefore, we arrive at \begin{align} S_k &=(N_1+2N_2)\mod 3= (N_1-N_2)\mod 3 \\ &= (k-N_0-N_2+2N_2)\mod 3 = (k-N_0+N_2)\mod 3. \end{align} Further, $(i\mod 3)$ can take values $0, 1$, and $2$, equal probabilities since $2022$ is divisible by $3$, and every value can repeat at most $2002/3$ times. So, the distribution of $(N_s-N_t)\mod 3$ is the same for any $t,s$.

Consequently, for any $k$, we arrive at \begin{align} \mathrm{Prob}(S_k = 1) &= \mathrm{Prob}(N_1-N_2 = 1 \mod 3) = \mathrm{Prob}(N_2-N_1 = -1 \mod 3) \\ &= \mathrm{Prob}(N_1-N_2 = 2 \mod 3)=\mathrm{Prob}(S_k = 2). \end{align}

When $k=1\mod 3$, we have \begin{align} \mathrm{Prob}(S_k = 0) &= \mathrm{Prob}(N_1-N_2 = 0 \mod 3) = \mathrm{Prob}(k-N_0+N_2 = 0 \mod 3) \\ &= \mathrm{Prob}(N_2-N_0 = 1 \mod 3) = \mathrm{Prob}(N_1-N_2 = 1 \mod 3)\\ &=\mathrm{Prob}(S_k = 1). \end{align} Similarly, when $k=2\mod 3$, we can verify that $$\mathrm{Prob}(S_k = 0) =\mathrm{Prob}(S_k = 1)=\mathrm{Prob}(S_k = 2)=1/3.$$