Three persons $A,B,C$, are playing the following game: A $k$-element subset of the set $\{1, . . . , 1986\}$ is randomly chosen, with an equal probability of each choice, where $k$ is a fixed positive integer less than or equal to $1986$. The winner is $A,B$ or $C$, respectively, if the sum of the chosen numbers leaves a remainder of $0, 1$, or $2$ when divided by $3$. For what values of $k$ is this game a fair one? (A game is fair if the three outcomes are equally probable.)
Problem
Source:
Tags: probability, combinatorics, game, game strategy, counting, IMO Shortlist
02.09.2010 13:05
Consider the generating function $G(x) = \prod_{i=1}^{1986}(1+x^iy)$. The exponent of x in each term of the expanded generating function gives the sum of the elements of the subset, and the exponent of the y gives the number of elements. Thus, we need to find the number of terms in each of the sums $ \sum_{i\equiv 0 (mod 3)}x^iy^k$ and $ \sum_{i\equiv 2 (mod 3)}x^iy^k$. For the first sum, using a roots of unity filter, we want the coefficient of $y^k$ in $\frac{\prod_{i=1}^{1986}((1+w^iy) + \prod_{i=1}^{1986}(1+w^2iy) + \prod_{i=1}^{1986}(1+w^3iy))}{3}$ $=\frac{2((1+y)(1+wy)(1+w^2y))^{662} + (1+y)^{1986}}{3}$ $=\frac{2(1+y^3)^{662} + (1+y)^{1986}}{3}$ Where $w$ is a primitive cubic root of unity.So the coefficient of $y^k$ is $ \begin{cases}\frac{\binom{1986}{k}}{3}\text{ if }3\nmid k\\ \frac{\binom{1986}{k}+2\binom{662}{k/3}}{3}\text{ if }3|k\end{cases} $ The second sum is the same as $ \sum_{i\equiv 0 (mod 3)}x^{i+1}y^k$ So using the roots of unity filter again on $xG(x)$ we want to find the coefficient of $y^k$ in $\frac{w\prod_{i=1}^{1986}((1+w^iy) + w^2\prod_{i=1}^{1986}(1+w^2iy) + w^3\prod_{i=1}^{1986}(1+w^3iy))}{3}$ $=\frac{(w+w^2)((1+y)(1+wy)(1+w^2y))^{662} + (1+y)^{1986}}{3}$ $=\frac{(w+w^2)(1+y^3)^{662} + (1+y)^{1986}}{3}$ $=\frac{(1+y)^{1986} - (1+y^3)^{662}}{3}$ So the coefficient of $y^k$ is $ \begin{cases}\frac{\binom{1986}{k}}{3}\text{ if }3\nmid k\\ \frac{\binom{1986}{k}-\binom{662}{k/3}}{3}\text{ if }3|k\end{cases} $ Clearly, the two are equal iff $3\nmid k$. In this case since the total number of subsets is $\binom{1986}{k}$, the number with sum congruent to 1 modulo 3 is also $\frac{\binom{1986}{k}}{3}$ and thus remainders 0,1,2 have equal chances iff $3\nmid k$.
02.09.2010 20:13
A variant on this problem actually appeared as problem $6$ in the 1995 IMO. Here's a solution based in part on the combinatorial solution to that problem: Given a subset $S$ and an integer $j$ in $\{1, \dots, 662\}$, we call $S$ consistent for $j$ if $\{3j-2, 3j-1, 3j\}$ are either all in $S$, or all not in $S$. Now consider the following operation on a set $S$: If $S$ is consistent for every $j$, do nothing. Otherwise, find the smallest $j$ for which $S$ is not consistent, and "rotate" $S$ within the group of $3$ by replacing $3j-2$ by $3j-1$, replacing $3j-1$ by $3j$, and replacing $3j$ by $3j-2$. Example: If $S=\{1,2,3,7,9\}$, then $j=3$ and we replace $S$ by $\{1,2,3,8,7\}$. Applying it again would replace $S$ by $\{1,2,3,9,8\}$, and applying it again would return you to $\{1,2,3,7,9\}$. On the other hand, the operation would do nothing to $\{1,2,3,7,8,9\}$. This operation splits the $k$ element subsets into groups of size $3$, along with possibly some fixed points. Within each group of size $3$, the sets correspond to $3$ different winners, so the game is fair. However, all the fixed points are winners for $A$ (since $3$ always divides $(3j-2)+(3j-1)+3j$). So the game's fair iff there are no fixed points. But fixed points occur exactly when $3$ divides $k$.
28.04.2021 16:35
I learned this trick today so I will post my solution.
02.01.2025 12:50
same as @above, so storage