1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Are there both red and blue dots at the endpoints $0,1$? $\endgroup$ – coffeemath Nov 15 '18 at 22:46
  • 1
    $\begingroup$ No, only within the interval. $\endgroup$ – jeremiah Nov 15 '18 at 22:57
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This is a very elegant solution, clear and well written. I was on a completely wrong track. Could you provide an idea or hint how to figure out the number of red and blue dot pairs?Thanks so much. $\endgroup$ – jeremiah Nov 15 '18 at 23:30
  • $\begingroup$ I think (without proof) that the number of such pairs is the number of whichever dots there are less of. At this point it's important that $1000$ and $1111$ are relatively prime so that the dots never overlap in the interval (only at the endpoints). Therefore you can guarantee that at least one blue dot lies strictly between every consecutive pair of red dots, so every red dot is a solution. $\endgroup$ – M. Nestor Nov 15 '18 at 23:35
  • $\begingroup$ Thank you - helps me a lot (and shows me that I´ve got to learn a lot too) $\endgroup$ – jeremiah Nov 15 '18 at 23:37
1
$\begingroup$

If my understanding of the question is correct, since the distance between blue dots are smaller than the distance between red dots, you cannot place 2 red dots without having at least 1 blue dot in between. In other words, the number of pairs should be equal to the number of red dots 999.

Regarding the first part of the question, it could be converted into a minimization problem by minimizing the absolute value of ( a/1000 - b/1111).

Another simpler approach could be by using mod. (stretching the 0-1 interval to 0-1000*1111 to avoid writing in divisive form)

Now for first dots the difference is 111. The difference between nth blue dot and nth red dot is 111n. We need to now think in terms of 111n mod(1000) and 111n mod(1111) as that distance between nth dots would be closed by either a blue or red dot. Intuitively, when n is 9, 111n mod 1000 becomes -1, which means the next dot with smaller interval (blue) is 1 place after the 9th red ball. Thus we can say the distance between 9th red ball and 10th blue ball is the smallest (10000 - 9999 = 1). Back in absolute terms, 10/1111 - 9/1000 would be the smallest answer possible.

You can confirm that this is indeed the smallest possible, since distance between nth red dot and mth blue dot would be m/1111 - n/1000

Since both n and m are integers we know that 1000n - 1111m would be integer as well. This leaves us with the final answer of (1000n-1111m) / (1000*1111) which cannot be smaller than 1/(1000*1111) as the top part of the division is an integer and 1000 and 1111 don't have any common divisor but 1.

hope it helps

$\endgroup$
  • 1
    $\begingroup$ And indeed it helps! Very well written. I much appreciate your effort thank you. $\endgroup$ – jeremiah Nov 15 '18 at 23:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.