IMO 1986 SL 10

Origin: HUN

Problem

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.)

Solution

The set X = {1, . . . , 1986} splits into triads T1, . . . , T662, where Tj = {3j −2, 3j −1, 3j}. Let F be the family of all k-element subsets P such that |P \capTj| = 1 or 2 for some index j. If j0 is the smallest such j0, we define P ′ to be the k-element set obtained from P by replacing the elements of P \capTj0 by the ones following cyclically inside Tj0. Let s(P) denote the remainder modulo 3 of the sum of elements of P. Then s(P), s(P ′), s(P ′′) are distinct, and P ′′′ = P. Thus the operator ′ gives us a bijective correspondence between the sets X \inF with s(P) = 0, those with s(P) = 1, and those with s(P) = 2. If 3 ∤k is not divisible by 3, then each k-element subset of X belongs to F, and the game is fair. If 3 | k, then k-element subsets not belonging to F are those that are unions of several triads. Since every such subset has the sum of elements divisible by 3, it follows that player A has the advantage.