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.
Problem
Source: 2017 China TST 5 P3
Tags: combinatorics
08.04.2017 13:06
rational point (x,y) means,x,y are both rational numbers.
09.04.2017 06:16
This should help: https://artofproblemsolving.com/community/c6h407539p2276536
09.04.2017 06:53
Nice Problem
16.03.2021 07:28
Redacted
10.04.2021 09:51
Can someone post the solution?
18.09.2021 05:16
Can someone post the solution?
04.06.2022 02:44
The answer is yes. Consider the line $y=ax+b$. Set $b=2, a=p_1p_2\cdots p_m$ for primes $p_1,\cdots,p_m$ that will be decided later. If a rational point $(x,y)$ satisfies $xy=z\in \mathbb{Z} \leftrightarrow 1+az$ perfect square. We construct $p_1,\cdots,p_m$ such that $p_i>2017^{2017}$ and for all $1\le j\le m-1,$ $$3\prod\limits_{k\ne j, 1\le k\le m} p_k \equiv 2(\bmod\; p_j)$$ To do this, we just need $p_m\equiv \frac{2}{3\prod\limits_{k\ne j, 1\le k\le m-1} p_k} (\bmod\; p_j)$, which by CRT is equivalent to mod condition mod $p_1\cdots p_{m-1}$ and exists by Dirichlet's theorem. I claim this works. Suppose $1+az\equiv x^2(\bmod\; a)$, then for some $x_1, \cdots, x_m \in \{-1,1\}$, $x\equiv x_j (\bmod\; p_j)$ Let $v_j$ be the unique integer such that $v_j\equiv 0(\bmod\; p_i)$ for all $i\ne j$ and $v_j\equiv 2(\bmod\; p_j)$ and $1\le v_j\le P$. This means the set of $x$ st $x^2\equiv 1(\bmod\; a)$ in $\mathbb{Z}_a$ is of the form $-1+\sum\limits_{j=1}^m e_jv_j$ where $e_j\in \{0,1\}$. Notice $v_j=\frac{3a}{p_j}$ for $1\le j\le m-1$. For size reasons, $2< v_1+\cdots+v_{m-1} = 3a \sum_{j=1}^{m-1} \frac{1}{p_j} < a$. Therefore, $2< v_1+\cdots+v_m < 2a$. Since $v_1+\cdots+v_m \equiv 2(\bmod\; p_j)$ for all $1\le j\le m$ it follows that $v_1+\cdots+v_m=a+2$ Step 1: construct an interval with $2017+58=2075$ blue points and 0 red points. Observe the set of $\sum\limits_{j=1}^{m-1} e_jv_j \equiv 3\sum e_j (\bmod\; 6)$. Therefore, if $x=-1+\sum\limits_{j=1}^{m-1} e_jv_j, 3\mid x^2-1$ (so $3\mid \frac{x^2-1}{a}$) and the parity of $\frac{x^2-1}{a}$ is also the same as the parity of $x^2-1$, which is the parity of $\sum e_j$ Therefore, all $z$ such that $1+az=(\sum\limits_{j=1}^{m-1} e_jv_j -1)^2$ for some $e_1+\cdots+e_{m-1}$ odd corresponds to a blue point because $3\mid z, 2\nmid z$ and $\frac a4 x^2+x=z$ has a solution with $x\in \mathbb{Q}$. Hence when $0<z<(\sum\limits_{j=1}^{m-1} v_j-1)^2$, there is an interval of $2^{m-2}>2075$ blue points. Step 2: Use discrete continuity. Suppose I sort all $z_1<z_2<\cdots<z_{6\times 2^m}$ such that $1+az_i=b_i^2$ is a perfect square for all $i$. Then notice $b_{i+2^m}=b_i+a$ because there are $2^m$ solutions to $x^2\equiv 1(\bmod\; a)$ in $\mathbb{Z}_a$. Consider $z_{j+t2^m}$ for $0\le t\le 5, 1\le j\le 2^m$. We can see $z_{j+t2^m} = \frac{b_{j+t2^m}^2-1}{a} = \frac{(b_j+ta)^2-1}{a}$ We know $a$ is either $1$ or $-1$ mod 6. For any value of $b_j$, we can set $t \in \{0,\cdots,5\}$ such that $3\mid b_j+ta$ and $2\nmid b_j+ta$, which forces $\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 $z_1<\cdots<z_{6\times 2^m}$ is at least $2^m$, while the number of blue points is at most $5\times 2^m$. Let $c_j$ be the number of blue points among $z_j,\cdots,z_{j+2074}$. Observe $|c_{j+1}-c_j|\le 1$ and $c_t=2075$ for some $t$. Therefore, by discrete continuity, there exists $c_j=2017$, finishing the problem.