Home > Uncategorized > The Diagonal Problem (2 dimensions)

The Diagonal Problem (2 dimensions)

  1. Draw a rectangle on squared paper.
  2. Draw a diagonal across your rectangle.
  3. How many squares does it pass through?

Diagram 1

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

Thanks to Jose Alavedra for making this applet. I made one but Jose’s is more efficient and more flexible ūüôā

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….

5x8 with yellow

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.

4x3 with yellow

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:

9x3

This greedy little number has two jumps.  And what about the 6×4 which features both steps and a jump:

6x4

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?

Easy?

What about the 3 dimensional version of this problem?

  1. chloe
    October 6th, 2013 at 10:44 | #1

    Oops sorry that was 6. @chloe

  2. chloe
    October 6th, 2013 at 10:39 | #2

    Thank you for your post. I tried with 2×5 rectangle. And I can find 5 squares does a diagonal pass through. Would you explain for this?

  1. June 24th, 2010 at 09:41 | #1