# Diagonal Crossing

#### mathmaniac

##### Active member
Challenge:
How many boxes are crossed by a diagonal of an 800 X 200 rectangle?

Solution with proof required...

#### caffeinemachine

##### Well-known member
MHB Math Scholar
Challenge:
How many boxes are crossed by a diagonal of an 800 X 200 rectangle?

Solution with proof required...

Hello Mathmaniac
I don't understand the question. What us meant by 'boxes are crossed'.

Also, if this is a challenge problem then shouldn't this go in the 'Challenge and Puzzles' forum?

#### MarkFL

Staff member
Yes, I sent the OP a VM asking if this is a challenge or if it is a problem for which he needs help shortly after it was posted, but have not gotten a response yet. Once the matter is settled, I will move it if need be, then remove this post so that the topic is not cluttered.

#### MarkFL

Staff member
Its a challenge,Mark...
I have thus moved the topic to the Challenge Questions and Puzzles sub-forum. I know you used the word "Challenge" but wanted to make sure it fit the criteria, i.e., you have the correct solution ready to post in the event no one solves it. Last edited:

Yes!!!

#### Bacterius

##### Well-known member
MHB Math Helper
[JUSTIFY]The rectangle is made of $800 \times 200$ "boxes". The diagonal thus has gradient $\pm \frac{200}{800} = \pm \frac{1}{4}$, where a "box" has unit dimensions. Note the diagonal starts at the top left corner of the top-left-most box. This is important. So, after 4 units of width travelled, the diagonal will intersect the top left corner of another box:[/JUSTIFY] [JUSTIFY]And this section of the diagonal intersects four boxes. Since the rectangle is 800 boxes wide, this section of the diagonal will repeat $\frac{800}{4} = 200$ times, and so the diagonal intersects $4 \times 200 = 800$ boxes.[/JUSTIFY]

[HR][/HR]

[JUSTIFY]A more interesting problem is to consider a rectangle of dimensions $p \times q$ where $p$ and $q$ are distinct primes. Then the diagonal never intersects the top-left corner of a box within the rectangle, and a different approach is called for:[/JUSTIFY] Last edited:

#### mathmaniac

##### Active member
Thats right,Bacterius...
And can you show your approach for distinct primes?

#### Bacterius

##### Well-known member
MHB Math Helper
Thats right,Bacterius...
And can you show your approach for distinct primes?
[JUSTIFY]It's simple enough, in fact. Because we know that the diagonal will, in this case, never intersect a corner, we can count the number of boxes crossed by simply counting the number of times the diagonal intersects both the vertical sides and the horizontal sides of the boxes. The diagonal will intersect $p - 1$ horizontal sides, and $q - 1$ vertical sides, simply by virtue of being a line crossing the rectangle from top-left to bottom-right (or top-right to bottom-left).

But not so fast - the diagonal always starts inside the rectangle, and so automatically intersects the top-left box (or whichever corner of the rectangle you start your diagonal from), which we haven't yet considered, giving a total of $(p - 1) + (q - 1) + 1 = p + q - 1$ boxes intersected. Checking with the diagram above gives $11 = 7 + 5 - 1$ boxes intersected, as expected.

Not very rigorous, just a proof sketch showing the general approach.[/JUSTIFY]

Last edited:

#### mathmaniac

##### Active member
Here we have a winner!!!