Maths Olympiad Prep

Library / China Girls' Mathematical Olympiad /22 of 51

China Girls' Mathematical Olympiad

Number theory Difficulty 6.0 National Olympiad Prove it China

Let SS be a subset of mm elements of {0,1,2,…,98}\{0, 1, 2, \dots, 98\}, m≥3m \geq 3, such that for any x,y∈Sx, y \in S, there exists z∈Sz \in S with x+y≡2z(mod99)x + y \equiv 2z \pmod{99}. Find all possible values of mm.

Solution

Let S={s1,s2,…,sm}S = \{s_1, s_2, \dots, s_m\}. As S′={0,s2−s1,…,sm−s1}S' = \{0, s_2 - s_1, \dots, s_m - s_1\} satisfies also the hypothesis, we may assume without loss of generality that 0∈S0 \in S. For any x,y∈Sx, y \in S, 50(x+y)≡z(mod99)∈S50(x + y) \equiv z \pmod{99} \in S. By taking y=0y = 0, we have that for any x∈Sx \in S, 50x∈S50x \in S. As 5050 and 9999 are coprime, there exists a positive integer kk such that 50k≡1(mod99)50^k \equiv 1 \pmod{99}. Hence,
x+y≡50k(x+y)(mod 99)∈S. x + y \equiv 50^k (x + y) (\text{mod } 99) \in S.
Let d=gcd⁡(99,s1,s2,…,sm)d = \gcd(99, s_1, s_2, \dots, s_m). The above argument then implies that d∈Sd \in S, therefore S={0,d,2d,… }S = \{0, d, 2d, \dots\}. For any positive factor d<99d < 99 of 9999, this SS satisfies all the requirements. Hence, all the possible values of mm are 33, 99, 1111, 3333, 9999. □\square

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.