1
$\begingroup$

The below exercise appears in a book in section of GCD, and linear Diophantine equation (LDE).

A square of side $1$ is divided in $a$ strips by equally spaced $(a-1)$ red lines parallel to a side, and is divided in $b$ strips by equally spaced $(b-1)$ blue lines parallel to red strips. What is the minimum distance between the red and blue lines.

For application of GCD, need form linear Diophantine equations(LDEs) to use the properties, assume WLOG (hoping that this would not affect the solution in other cases), that $a \nmid b, b\nmid a$.
So, $(a,b)=1$ and this should help to form the LDE $ax + by =1$.

To get the minimum distance, may be the book's answer helps: it is given as $(a,b)/ab.$

I want to at least see the logic of this answer, if there is division of a side of unit length into $5$ and $6$ parts by $4$ red and $5$ blue lines respectively, then how come the minimum distance is $1/30$.
If I draw on a graph paper, then the lines are as shown below :

$$ \begin{align} 0.2 <--> & \ 0.166 \\ 0.4 <--> & \ 0.332 \\ 0.6 <--> & \ 0.498 \\ 0.8 <--> & \ 0.664 \\ none <--> & \ 0.830 \\ \end{align} $$

The minimum distance is between $0.830, 0.8 => 0.030 = 1/30.$
So, the author wants to take the linear combination (in my example) of $-a'.4 + b'.5$ to arrive at the minimum value of $1/30$, where $a'$ is for red strip length ($=0.2 = 1/a $), and $b'$ is for blue. Note that $a$ = #red strips = #red lines +1, $b$ =#blue strips= #blue lines +1, even though the distance is between lines only.

So, effectively the question reduces to finding the Bezout's coefficients for the smallest possible linear combination, which for my example is :$a=0.2, b = 0.166$. So, is $(a,b) = 1/(5.6)$ an example of $\gcd$ for rational numbers.

$\endgroup$
  • $\begingroup$ I've been trying to make sense of the question, and have not yet succeeded. You use the term "strips" at first to mean the regions between the red lines and between the blue lines. There is no mention of color for the strips themselves, and obviously each set of strips contains almost all the points in the square. But then the question asks about the minimum distance between the "red strips" and "blue strips", that quite evidently overlap, so that distance would be $0$. Apparently we are now using "strips" to mean the lines, not the regions between? $\endgroup$ – Paul Sinclair Dec 25 '17 at 3:29
  • $\begingroup$ @PaulSinclair Yes you are correct, I am sorry for the confusion. Will edit soon. $\endgroup$ – jiten Dec 25 '17 at 3:30
  • 1
    $\begingroup$ The first thing I noticed is that $\frac 13 \neq 0.333$ This is math, not engineering, and equals means equals. If you are working with fractions you should work with fractions because they are exact. Then I noticed there is not a question here. What are you asking? $\endgroup$ – Ross Millikan Dec 25 '17 at 4:13
  • 1
    $\begingroup$ I think my answer is that there is no GCD in the rationals because they are a field so every number divides every other. You can express two rationals in lowest terms and ask about the GCD of the numbers in those two expressions. That is productive in some cases. Does that answer your question? $\endgroup$ – Ross Millikan Dec 25 '17 at 4:45
  • 1
    $\begingroup$ All of these are pointing at the same thing. In a ring like the integers you can add, subtract, multiply and sometimes divide. In a field you can always divide (except by $0$). You lose the concept of primes because every element is a unit. When you say rationals are closed under division that says you can always divide (and you need to exclude zero). I haven't thought about the subtleties that may lurk in the distinctions of wording. $\endgroup$ – Ross Millikan Dec 25 '17 at 5:16
1
$\begingroup$

You are really asking about $\min \left(\frac k{a-1}, \frac m{b-1}\right)$ where $k,m$ are naturals and $k \lt a-1, m \lt b-1$. It will be $\frac 1{\operatorname{lcm}(a-1,b-1)}=\frac {\gcd(a-1,b-1)}{(a-1)(b-1)}$ and your approach is the right way to find them.

$\endgroup$
  • $\begingroup$ But, one hitch: $k,m$ are not factored in your formula, only the denominators are. It seems logical that the entire proper fraction is factored in. $\endgroup$ – jiten Dec 25 '17 at 5:14
  • $\begingroup$ Hopefully, I was clear in my last comment. $\endgroup$ – jiten Dec 25 '17 at 5:30
  • 1
    $\begingroup$ No, they are not. They are just the stripe numbers. The point is that you will be able to find one pair of stripes that are as close as possible using Bezout $\endgroup$ – Ross Millikan Dec 25 '17 at 5:46
  • 1
    $\begingroup$ Your question asks about the distance between lines, not between the strips. The strips will overlap, so it only makes sense to talk about the distance between the lines. The use of $a-1,b-1$ comes because the spacing of the lines is $\frac 1{a-1}, \frac 1{b-1}$. We don't care if $a-1$ and $b-1$ are prime or not. In your example with $a=5, a-1=4$ is not prime. We only care if $a-1$ and $b-1$ are coprime. If so, there will be a place they are within $\frac 1{(a-1)(b-1)}$. The general statement is the minimum spacing will be $\frac {\gcd(a-1,b-1)}{(a-1)(b-1)}$ $\endgroup$ – Ross Millikan Dec 25 '17 at 14:43
  • 1
    $\begingroup$ To find the pair of lines with minimum spacing, you use the extended Euclidean algorithm. $\endgroup$ – Ross Millikan Dec 25 '17 at 14:44

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.