The Diagonal Problem (2 dimensions)
- Draw a rectangle on squared paper.
- Draw a diagonal across your rectangle.
- How many squares does it pass through?
Note: If your diagonal goes exactly through a point, like in the 2×4 example, then it is not considered to pass through either of the diagonally adjacent squares.
Problem: How many squares does a diagonal pass through in a 190×884 rectangle?b
Solution in 2 dimensions
I was pleased to receive a number of correct answers to this. This is a classic example of an investigation that requires you to draw lots and lots of different examples to see what’s going on. I filled two sides of A4 with rectangles before a path to the solution began to form in my mind. Here’s the gist of it:
Consider the 8×5 rectangle shown above. Each time the line passes from one row to the next, there’s a nice ‘step’ down. Yes, the pattern appears complicated (2 squares, then 3, then 2, then 3, then 2) but don’t get bogged down with this. Just be happy with the ‘step’ downs.
Now consider the 4×2 rectangle. How is it different from the 8×5? The answer is simple: it doesn’t ‘step’ down, rather it ‘jumps’. Why is this? What’s special about the 4×2 rectangle that gives it this clever property? Or maybe it’s the 8×5 rectangle that’s special. Let us investigate….
Here, the 8×5 rectangle has been redrawn highlighting additional squares caused by the ‘step’ downs. In your mind, push all the green squares to the top row. They fill the row, so there are 8 green squares. Now push all the yellow squares to the left column. This time, they don’t quite fill the column; we’re one short.
What have we done? Well we’ve figured out that 12, which is the number of coloured squares in the 8×5 rectangle, comes from 8+5-1. That is to say, length plus width minus 1.
Does it work with another example? Let’s try 4×3. Clearly it does work: 4 + 3 – 1 = 6.
So we’re on to something. Here’s our model:
Number of squares = Length + Width – 1
But we can refine this model…
-
The Jumps
Consider the 4×2 rectangle at the top of the page. According to our current model, 4 + 2 – 1 = 5, but there are only 4 coloured squares in that rectangle. We have already identified why the 4×2 is different from the 8×5: it jumps between rows. The jumps are where we need to focus to refine the model.
Is it because both 2 and 4 are both even numbers? Apparently not: have a look at this 9×3 rectangle:
This greedy little number has two jumps. And what about the 6×4 which features both steps and a jump:
If we can identify the cause of the jumps, we can refine and perfect our formula.
Think about the length-width pairs considered so far which contain jumps: (2,4) (3,9) (4,6). 2 divides into 4, and 3 divides into 9. Important? Well those examples gave nice, clean rectangles featuring only jumps and no steps. In the third pair, 4 doesn’t divide into 6 but we’ve still got a jump right in the middle. 4 might not divide into 6, but 4 and 6 are both even!
What do (2,4), (3,9), (4,6) and (9,6) all have in common? Answer: THEY ALL SHARE A COMMON FACTOR GREATER THAN 1.
Highest common factor is often expressed as HCF, so
HCF(2,4)=2, HCF(3,9)=3, HCF(4,6)=2, HCF(9,6)=3.
The highest common factor of the two lengths is one more than the number of jumps. It gives us one more than the the number of jumps because the start/end of the diagonal is considered to be a jump – imagine the rectangle repeated over and over:
In cases where the HCF is 2 there’s one jump in the middle of the diagonal, plus the hidden one at the start/end. In cases where the HCF is 3 there are two jumps inside the rectangle, plus the hidden one at the start/end. Each jump results in a ‘lost’ square, so we subtract.
Our solution:
Where S is the number of squares traversed by the diagonal: S = Length + Width – HCF(length,width)
In more algebraic terms, for an x × y rectangle, we could say this:
S = x + y – HCF(x,y)
To finish off then, for the 190×884 rectangle we calculate as follows:
S = 190 + 884 – HCF(190,884)
S = 190 + 884 – 2
S = 1072
Subpuzzle: Can you guess why I picked 190×884?
