In the closed interval [0, 1] there are 999 equally spaced red dots and 1,110 equally spaced blue dots (not on the endpoints). Thus the red dots divide the interval into 1,000 subintervals and the blue dots divide the interval into 1,111 subintervals.
What is the smallest distance beween any two points within this interval and how many pairs $(r_i, b_k)$ exist, i.e. pairs in which a red dot is followed by a blue dot?
My tentative thoughts (that didn´t get me any further): Draw a square $ABCD$ with coordinates $A(0, 0), B(0,1), C(1,1)$ and $D(0,1)$ into a cartesian coordinate system. Draw a grid (wlog) with 1,110 parallel lines to the x-axis and 999 lines parallel to the y-axis. The diagonal $y = x$ intersects the grid lines at $(x_i, y_j)$ and the minimum distance to the grid line ist he solution. How can I solve this?
Best Answer
If we have $n\in\mathbb N$ dots equally spaced in $(0,1)\subseteq\mathbb R$, not including the endpoints, they must have distance $1/(n+1)$ apart. Thus, the sets of dots have the following positions:
$$\text{red dots}:\Big\{\frac{1}{1000},\frac{2}{1000},\frac{3}{1000},\dots,\frac{999}{1000}\Big\}$$
$$\text{blue dots}:\Big\{\frac{1}{1111},\frac{2}{1111},\frac{3}{1111},\dots,\frac{1110}{1111}\Big\}$$
The distance between any two red and blue dots is $|\frac{m}{1000}-\frac{n}{1111}|$ for integers $m$ and $n$. The question becomes, what is the minimum value of $|\frac{m}{1000}-\frac{n}{1111}|$ for positive integers $m\leq 999$ and $n\leq 1110$?
$$\Big|\frac{m}{1000}-\frac{n}{1111}\Big|=\frac{|1111m-1000n|}{1000\cdot1111}$$
To minimize this fraction is to minimize its numerator. And it is known that the $\gcd$ of two integers is their smallest positive integral linear combination (Bézout's identity). That is, the minimum value of the numerator is $\gcd(1111,1000)$, which is $1$ since they are relatively prime. Thus the minimal distance is $1/(1000\cdot1111)$. For example, take $m=9$ and $n=10$, the points $9/1000$ and $10/1111$ are of the proper distance apart.