A diagonal through a rectangular grid of squares

August 20th, 2006 admin Posted in Tidbits |

Question

Anant asked me this question. He had heard it in a talk by an executive at Cisco Systems.

“There is a rectangular grid composed of 1×1 squares (i.e unit squares). The grid measures m squares by n squares. How many squares will a diagonal pass through?”

There are potentially many ways to compute a solution to this one. A deep dive into discrete mathematics is one way to tackle the problem, but the fact that an executive asked the question made be believe that there had to be a more elegant approach to solving it. The lesson the executive wanted to share with his colleagues was, probably, that a problem may have only one solution, but there may be a more elegant way to get to it and a less elegant way. Elegance of a solution is probably as important an aspect as correctness. Elegance not only saves time, but it also makes the solution easy to implement, understand and sell. I believe elegance should be a criterion to further qualify a solution beyond it’s correctness.

Getting back to the question, here is a figure showing an example scenario where mxn is 5×9.

Each square in the grid is 1×1.Draw a diagonal through the grid, as shown in the next figure.

The diagonal goes through some number of the 1×1 squares. These squares are highlighted in the next figure.

In this example it is easy to count that there are 13 squares that the diagonal goes through. What is the general solution in terms of m and n?

Solution

Read this solution only after you have either solved the problem in your way or have at least given it a good think. Keep an eye on how you approached the problem. The first step in the solution is to realize that the answer is not a trivial answer such as max(m,n), i.e. the bigger of m and n, or a non-integeral sqrt(m*n), or some variation there of. To prove it to youself, draw a 2×3 grid, and see that in this case the diagonal passes through 4 squares. Now draw a 2×4 grid and notice that the diagonal again passes through 4 squares! So the solution, though increasing in general as m and n grow, might sometimes give the same answer for two different mxn values.

I will dive straight into my solution without going into other approaches. I feel that my solution is relatively straightforward, quite thorough and yet, not too hard to explain. The main observation that gets us started is to notice that m and n can have two kinds of relationships. In one case, they might be relatively prime. That means there is no common factor between the two larger than 1. Highest Common Factor of m and n = HCF(m,n) = 1. The other case is that there is a common factor larger than 1. Taking examples, if mxn is 2×3, there is no common factor other than 1. If mxn is 2×4, then 2 is a common factor. The reason this is important is that the diagonal, in its journey from one corner of the rectangular grid to the other, only passes through a grid-point (i.e the corner where 4 1×1 squares meet) if m and n are not relatively prime! Several questions arise here. First is “Why?” and the second is “So what?”. To prove this, let us use a contradiction approach. Say m and n are relatively prime. There is no common factor between m and n other than the obvious 1. Say the diagonal passes through a grid-point. Let’s pick the first grid point it passes through and call it GP. Let C1 be the corner the diagonal “starts” at, and C2 be the corner the diagonal “ends” at. Since the diagonal is a single line and has a constant slope, the slope from C1 to GP is the same as the slope from GP to C2. This implies that, treating GP as C1, the diagonal will meet another grid-point in relatively the same position from GP as GP was from the original C1. Eventually since the diagonal must hit the ending corner C2, C2’s co-ordinates (m,n), must be a multiple of the co-ordinates of the first grid-point GP, say (m’, n’). m is k*m’ and n is k*n’, for some k, which therefore is a factor. This implies that m and n cannot be relatively prime. Putting it another way, if m and n are relatively prime the diagonal cannot pass through grid-points.

Once the effect of relative primality between m and n is established, it is a very easy problem to solve. Say m and n are relatively prime. Then the diagonal never goes through any of the intermediate corners of the 1×1 squares. Only corners it touches are those of the square the diagonal starts from and the square the diagonal ends at. Only way the diagonal enters a new square is from the top or side of a 1×1 square, never from a corner. Another way to say this is, each time the diagonal cuts either a horizontal or vertical grid line it enters a new square. That means to calculate the number of squares the diagonal passes through, the only thing we need to calculate is the number of vertical and horizontal grid lines the diagonal cuts. And that is easy to calculate. Imagine for a second that the horizontal grid lines vanished. The number of vertical lines the diagonal has to cut across to reach the other corner is … well, all the vertical lines there are, which is n - 1. This is shown in the figure. Now, for a second imagine that the horizontal lines are back, but the vertical lines have vanished. The diagonal must cut through the m - 1 horizontal lines.


The diagonal, even before it starts cutting any of the horizontal or vertical lines, must start from the first square, so it touched that one square without cutting any grid lines. So we add 1 to the total count of grid lines cut by the diagonal. This gives us,

The number of squares the diagonal passes through when m and n are relatively prime is
= (n-1) + (m-1) + 1
= m+n-1 : let’s call this Equation 1

So that brings us back to the case where m and n have a common factor. The largest common factor is HCF(m,n). If you look at the mxn grid, it is basically a replication of the problem k times where k is the HCF(m,n). This is shown in the figure. Therefore the answer is to solve the problem for the smallest relatively prime grid of size m/k x n/k and just multiply that answer by k, since the problem repeats k times across the length of the diagonal, as shown in the next figure.

This gives us the final solution to this problem.
Solution for the m/k x n/k grid
= m/k + n/k - 1 (from Equation 1)

Solution for the m x n grid
= k*(m/k + n/k -1)
= m + n - k
= m + n - HCF(m,n) : let us call this Equation 2

Equation 2 is the final answer.