Maths Olympiad Prep

Library / /90 of 97

Algebra Difficulty 8.7 Shortlist Find the answer

For a rational point (x,y), if xy is an integer that divided by 2 but not 3, color (x,y) red, if xy is an integer that divided by 3 but not 2, color (x,y) blue. Determine whether there is a line segment in the plane such that it contains exactly 2017 blue points and 58 red points.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Consider the line y=ax+b y = ax + b where b=2 b = 2 and a=p1p2pm a = p_1 p_2 \cdots p_m for primes p1,p2,,pm p_1, p_2, \ldots, p_m that will be chosen appropriately. We need to ensure that for a rational point (x,y) (x, y) , xy=zZ xy = z \in \mathbb{Z} such that 1+az 1 + az is a perfect square.

We construct the primes p1,p2,,pm p_1, p_2, \ldots, p_m such that pi>20172017 p_i > 2017^{2017} and for all 1jm1 1 \le j \le m-1 ,
3kj,1kmpk2(modpj). 3 \prod_{k \ne j, 1 \le k \le m} p_k \equiv 2 \pmod{p_j}.
This can be achieved by ensuring pm23kj,1km1pk(modpj) p_m \equiv \frac{2}{3 \prod_{k \ne j, 1 \le k \le m-1} p_k} \pmod{p_j} , which is guaranteed by the Chinese Remainder Theorem and Dirichlet's theorem.

We claim that this construction works. Suppose 1+azx2(moda) 1 + az \equiv x^2 \pmod{a} . Then for some x1,x2,,xm{1,1} x_1, x_2, \ldots, x_m \in \{-1, 1\} , xxj(modpj) x \equiv x_j \pmod{p_j} .

Let vj v_j be the unique integer such that vj0(modpi) v_j \equiv 0 \pmod{p_i} for all ij i \ne j and vj2(modpj) v_j \equiv 2 \pmod{p_j} with 1vjP 1 \le v_j \le P . This implies that the set of x x such that x21(moda) x^2 \equiv 1 \pmod{a} in Za \mathbb{Z}_a is of the form 1+j=1mejvj -1 + \sum_{j=1}^m e_j v_j where ej{0,1} e_j \in \{0, 1\} . Notice vj=3apj v_j = \frac{3a}{p_j} for 1jm1 1 \le j \le m-1 . For size reasons, 2<v1++vm1=3aj=1m11pj<a 2 < v_1 + \cdots + v_{m-1} = 3a \sum_{j=1}^{m-1} \frac{1}{p_j} < a . Therefore, 2<v1++vm<2a 2 < v_1 + \cdots + v_m < 2a . Since v1++vm2(modpj) v_1 + \cdots + v_m \equiv 2 \pmod{p_j} for all 1jm 1 \le j \le m , it follows that v1++vm=a+2 v_1 + \cdots + v_m = a + 2 .

Step 1: Construct an interval with 2017+58=2075 2017 + 58 = 2075 blue points and 0 red points. Observe that the set j=1m1ejvj3ej(mod6) \sum_{j=1}^{m-1} e_j v_j \equiv 3 \sum e_j \pmod{6} . Therefore, if x=1+j=1m1ejvj x = -1 + \sum_{j=1}^{m-1} e_j v_j , 3x21 3 \mid x^2 - 1 (so 3x21a 3 \mid \frac{x^2 - 1}{a} ) and the parity of x21a \frac{x^2 - 1}{a} is also the same as the parity of x21 x^2 - 1 , which is the parity of ej \sum e_j .

Therefore, all z z such that 1+az=(j=1m1ejvj1)2 1 + az = (\sum_{j=1}^{m-1} e_j v_j - 1)^2 for some e1++em1 e_1 + \cdots + e_{m-1} odd corresponds to a blue point because 3z 3 \mid z and 2z 2 \nmid z and a4x2+x=z \frac{a}{4} x^2 + x = z has a solution with xQ x \in \mathbb{Q} . Hence, when 0<z<(j=1m1vj1)2 0 < z < (\sum_{j=1}^{m-1} v_j - 1)^2 , there is an interval of 2m2>2075 2^{m-2} > 2075 blue points.

Step 2: Use discrete continuity.

Suppose we sort all z1<z2<<z6×2m z_1 < z_2 < \cdots < z_{6 \times 2^m} such that 1+azi=bi2 1 + az_i = b_i^2 is a perfect square for all i i . Then notice bi+2m=bi+a b_{i + 2^m} = b_i + a because there are 2m 2^m solutions to x21(moda) x^2 \equiv 1 \pmod{a} in Za \mathbb{Z}_a .

Consider zj+t2m z_{j + t2^m} for 0t5,1j2m 0 \le t \le 5, 1 \le j \le 2^m . We can see zj+t2m=bj+t2m21a=(bj+ta)21a z_{j + t2^m} = \frac{b_{j + t2^m}^2 - 1}{a} = \frac{(b_j + ta)^2 - 1}{a} .

We know a a is either 1 1 or 1 -1 mod 6. For any value of bj b_j , we can set t{0,,5} t \in \{0, \cdots, 5\} such that 3bj+ta 3 \mid b_j + ta and 2bj+ta 2 \nmid b_j + ta , which forces (bj+ta)21a=zj \frac{(b_j + ta)^2 - 1}{a} = z_j to be divisible by 2 but not 3, which is red. Therefore, the number of red points among z1<<z6×2m z_1 < \cdots < z_{6 \times 2^m} is at least 2m 2^m , while the number of blue points is at most 5×2m 5 \times 2^m .

Let cj c_j be the number of blue points among zj,,zj+2074 z_j, \cdots, z_{j + 2074} . Observe cj+1cj1 |c_{j+1} - c_j| \le 1 and ct=2075 c_t = 2075 for some t t . Therefore, by discrete continuity, there exists cj=2017 c_j = 2017 , finishing the problem.

The answer is: Yes.\boxed{\text{Yes}}.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.