A semi-tough question I came accross

[DyslexicHobo]

I was helping my friend do his basic skills math when he asked me help on this question:

Write a formula to determine how many boxes in an n x m grid will be intersected by a diagonal drawn from one corner to its opposite.

 

[out of whack]

...uhhh... n?

If the grid is 1x1 then the diagonal crosses 1 box.
If the grid is 2x2 then the diagonal crosses 2 boxes.
If the grid is 3x3 then the diagonal crosses 3 boxes...

Maybe I misunderstand the question.

 

[theCandyman]

If it's basic math skills, it's probably just n and not some type of trick question. Most likely it's so the students see that the line is longer but the number of boxes the line intercepts is the same as a straight line along the side.

 

[DyslexicHobo]

Sorry, I meant n x m

The dimensions do not have to be equal.

 

[out of whack]

Sorry, I meant n x m

That's more interesting. I have found a solution that is not exactly a formula but a recursive algorithm that can probably be expressed as a formula by the math inclined (not me). Let N <= M. Switch the numbers around if needed, the problem is symmetric. Visualize it with M on the horizontal for the explanation:

The line touches at least M blocks since it traverses the horizontal. For each of these M blocks, it also touches an additional block whenever it crosses the boundary between two vertical blocks. This happens if and only if the line does not also cross a horizontal boundary at the same time (the intersection of two lines on the grid). So if the line never crosses at an exact intersection, we can add N-1 blocks and the solution is M + N - 1.

If however the line crosses at an exact intersection, the problem is reduced to a smaller one: an integer number of smaller grids. For example, the solution for a 2x10 grid is twice the solution for a 1x5 grid (10); the solution for a 5x10 is five times the solution for a 1x2 (also 10). How to identify this?

If N and M have no common factors (if N/M does not simplify) then the line does not cross any exact intersection and we subtract nothing. The answer is M + N - 1.

If on the other hand N/M simplifies then let P/Q be the simplified ratio and F the factor (N/P). This is a decomposition of the problem into F smaller grids of size P x Q. We solve recursively for one P x Q grid and multiply by F. For this case, the answer is F * (P + Q - 1).

 

[DyslexicHobo]

That's more interesting. I have found a solution that is not exactly a formula but a recursive algorithm that can probably be expressed as a formula by the math enclined (not me). Let N <= M. Switch the numbers around if needed, the problem is symmetric. Visualize it with M on the horizontal for the explanation:

The line touches at least M blocks since it traverses the horizontal. For each of these M blocks, it also touches an additional block whenever it crosses the boundary between two vertical blocks. This happens if and only if the line does not also cross a horizontal boundary at the same time (the intersection of two lines on the grid). So if the line never crosses at an exact intersection, we can add N-1 blocks and the solution is M + N - 1.

If however the line crosses at an exact intersection, the problem is reduced to a smaller one: an integer number of smaller grids. For example, the solution for a 2x10 grid is twice the solution for a 1x5 grid (10); the solution for a 5x10 is five times the solution for a 1x2 (also 10). How to identify this?

If N and M have no common factors (if N/M does not simplify) then the line does not cross any exact intersection and we subtract nothing. The answer is M + N - 1.

If on the other hand N/M simplifies then let P/Q be the simplified ratio and F the factor (N/P). This is a decomposition of the problem into F smaller grids of size P x Q. We solve recursively for one P x Q grid and multiply by F. For this case, the answer is F * (P + Q - 1).

Well done. :)

What about a 3-dimensional block? How many cubes would be intersected by a diagonal going through an m x n x o cube?