Maths Olympiad Prep

Library / /23 of 53

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\}, m3m \geq 3, such that for any x,ySx, y \in S, there exists zSz \in S with x+y2z(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,s2s1,,sms1}S' = \{0, s_2 - s_1, \dots, s_m - s_1\} satisfies also the hypothesis, we may assume without loss of generality that 0S0 \in S. For any x,ySx, 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 xSx \in S, 50xS50x \in S. As 5050 and 9999 are coprime, there exists a positive integer kk such that 50k1(mod99)50^k \equiv 1 \pmod{99}. Hence,
x+y50k(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 dSd \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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.