1. Draw a rectangle on squared paper.
2. Draw a diagonal across your rectangle.
3. 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, the answer’s 6.

So we’re on to something:

Number of squares = Length + Width – 1

Now consider the 4×2 rectangle:  4 + 2 – 1 = 5, but there are only 4 coloured squares in that rectangle so the formula isn’t right.  It’s not wrong, it just isn’t right yet.

We have already identified why the 4×2 is different from the 8×5: it jumps between rows.  That’s clearly the cause of the issue.  Is it that both 2 and 4 are even?  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 jumps:

If we can identify the cause of the jumps, we can modify our formula to suit.

Think about the length-width pairs considered so far that 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!  Halve both numbers and consider a 3×2 rectangle – you can see from the last diagram that 6×4 is an extension of 3×2, and if we extended further it would be 9×6, which would give us another pair featuring jumps.

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 tells us how many jumps there are because the rectangle could be divided into that many smaller rectangles.  8×5, right back at the beginning does have a jump: it’s the start and finish of the diagonal, which is why we have to subtract the 1.  In cases where the HCF is 2, we subtract the extra one because there’s one jump in the middle of the diagonal. If the HCF of the length and width is 3, there are two jumps plus the one at the start/end of the diagonal, so we subtract 3.

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?

Easy?

What about the 3 dimensional version of this problem?

Answer next week!