A Line in a Square GridOn squared paper, draw a rectangle and one of its diagonals. How many grid squares are crossed by the diagonal?
 |Activities| |Contact| |Front page| |Contents| |Algebra| |Geometry| |Store| Copyright © 1996-2012 Alexander BogomolnySolutionThe best way to approach this problem seems to start with a few small rectangles 2×3, 2×5, 3×5, etc. Tabulate the results and next try to generalize. There are going to be exceptional cases, like 2×4, 3×6, 4×6. These would need a special treatment and further generalization.
What makes some cases exceptional? The fact that the diagonal passes through grid nodes. When this happens the number of crossed squares appears to be less than for the grids with nearby dimensions. Let's disregard such cases for a moment and focus on the grids where the diagonal does not pass through any of the grid points. How can we count the crossed squares in that (simple) case? The upper left square is always crossed. This is 1. Next, on its way to the next square the diagonal crosses one of the (internal) grid lines. In fact, this happens every time we move from one crossed square to the next. When we move from one crossed square to the next we step over their common side which is necessarily crossed by the diagonal. It follows that The number of crossed squares is 1 more than the total number of internal grid lines - both vertical and horizontal - crossed by the diagonal. But on its way from the upper left corner of the rectangle to the lower right corner, the diagonal crosses all internal vertical as well as horizontal lines. Naturally, each line is crossed only once. How many of these lines are there? For the M×N rectangle, there are (M-1) horizontal and (N-1) vertical lines. Thus the total number of internal lines crossed by the diagonal is
It's a good idea now to check this formula by counting for a few additional cases of (relatively) small M and N. In preparation for the next step, pay attention to those M and N, for which the formula fails, i.e., M and N for which the diagonal passes through (internal) grid points. It's hard to miss the point that this happens when M and N have non-trivial common divisors, i.e., when It is easy to generalize again. How many internal grid points lie on the diagonal? S = M + N - 1 - (gcd(M, N) - 1) = M + N - gcd(M, N). In other words, the general formula for the number S of crossed squares is
Since gcd(M, N) = 1 when M and N have no common factors, meaning geometrically that no grid points lie on the diagonal, (2) is a clear generalization of (1). (Further generalization would be to consider the configuration where the grid lines are not distributed evenly. In this case, the formula (1) is still true as long as no grid points lie on the diagonal, whereas (2) loses its significance. From this point of view, (1) which is applicable in a more broad context, is more general than (2).) References
|Activities| |Contact| |Front page| |Contents| |Algebra| |Geometry| |Store| Copyright © 1996-2012 Alexander Bogomolny |
| 40618790 |
