so the saying goes. I brought it up for one reason: the problem we look at today could be formulated in a “wood“ and “tree” context. But, let us start with the original problem.
The problem was given at a final of the AQJM (http://aqjm.fsg.ulaval.ca/), but a similar version was also given at the International Kangaroo Math Contest in Romania a few years back.
The problem from AQJM goes like this:
Consider you have a grid. Starting from the sixth grid-point on the horizontal axis, find the point of minimal vertical coordinate on the vertical axis such that the line between these points cuts more than 10 squares.
The problem given at the Kangaroo contest was: Consider a chess table. Draw
a line on the table such that it cuts as many squares as possible.
One can see that the two problems are not identical, but they are related and bring us to a more general question: given a grid, situated at (0,0) only using non-negative coordinates, and two points, one on each axis, can we tell exactly how many squares will be crossed by the line?
Let’s start with a drawing. Below we have a grid, just 8×8, and we can assume the lower left corner has the coordinates (0,0). We should draw some lines, just to see what kind of situations we will find.
The lines in the figure illustrate different situations: the green one passes just through grid-points, the lilac one cuts some squares and also passes through grid-points, meanwhile
the red ones are just cutting squares. There are no other types of lines, so we can ask: what is defining the type of line?
Getting back to the first problem: we need the point on the vertical axis, with smallest vertical coordinate, such that the line (starting from (6,0) position) will cut more than 10 squares. So, we need to maximize the number of intersected squares.
In problem solving, and not just in mathematics, often the most important task is to decide how to ask a question. We can explain the very same issue in different ways – we can reformulate the information, the question or any other element. And here comes the nice part: you would be asking a question equally relevant for obtaining an answer; however the new formulation will give you new insight into the problem. “Re”-formulation is essential for problem solving and we should teach how to do that or at least
motivate students to try to do it. In the same time reformulation often
requires a flexible knowledge management and that can come only after having a deep
understanding of a subject.
In our particular case, things are simpler. We can “see” that maximizing the number of intersected squares comes down to minimize the number of grid-points the line passes through.
So, now we have another thing to focus on: when will a line go through a grid-point? This question is nice for two reasons.
First, because we need to “interpret” the statement “passes through a grid-point”. What does it mean? Well, it means that we have some integer coordinates for that point of the line, so I can easily identify distances.
Second, because we have integer coordinates on one side and a geometrical illustration on the other hand, we are simultaneously in numbers and geometry. And the geometry will help us to characterize the points our line passes through.
Let’s have a closer look at the green line, in other words triangle AOB. The line passes through D’ of the grid (and E’’), therefore triangles AOB and BDD’, BDD’ and BEE’’ are similar (from Thales). From where we have that the ratio of AO and OB will be the same as DD’ and DB (and, also, E’’E and EB). Since we have integers, once again we reformulate the obtained result: we speak about equivalent fractions.
This point is worth a second of pause, perhaps filled with admiration. From geometry we arrived to equivalent fractions. We know that rational numbers are those that can be expressed as fraction of two integers (denominator can’t be zero), but here and now we have the rational numbers as ratios of distances – which was the way in which Greek mathematicians introduced them in the first place. The problem lead us to see how interconnected numbers and geometry are – and we should understand that considering geometry, algebra, arithmetic as completely separate domains (as often happens in school)
can induce a wrong conception about what mathematics is.
A similar analysis about the lilac line will bring us to the same conclusion.
In conclusion: if we have two points, one with coordinates (a,0) and the second with coordinates (0,b), the line defined by them will pass through grid points if a and b are not relative primes, and the number of grid-points it passes through is equal to the number of common divisors between a and b.
This is an important result, but how many squares will cross the line when a and b are relative primes?
We know that the total number of grid-points inside the rectangle with vertexes (0,0) (a,0) (a,b) (0,b), defined by integers a and b is (a-1)*(b-1). We also know that exactly half of these are on each side of the line that passes through (a,0) and (0,b) (this rectangle’s diagonal,) that is, (a-1)*(b-1)/2. Given that a and b are relative primes, it means that at least one of them is odd, so the above number is an integer number.
If we focus on one half of the rectangle, that is, one of the square triangles resulting when we cut the rectangle by the diagonal, we can see that the number of squares not intersected by the diagonal is equal to the grid-points inside the rectangle: (a-1)*(b-1)/2.
Therefore, the diagonal cuts all the squares that are not contained inside the square rectangles on both sides of the diagonal:
If we get back to the AQJM problem: we have a=6 and we are looking for a minimal b such that the number of intersected squares is larger than 10. First, we know that b will be minimal, if a and b are relative primes (written (a,b)=1). If we were running out of time (there is never too much time on these contests), we can try the numbers that are relative primes with 6 in order, namely: 1, 5, 7, 11, 13, … Hopefully, we’ll find the answer soon enough.
We can also develop the formula we just discovered into a + b – 1. Thus, we know that b must be greater than 5 (for 6 + 5 – 1 = 10). The first prime relative with 6, and greater than 5 is 7, which is the answer.
And, in the end: what about the trees and the wood? Well, just think about those ”planted” woods: trees are planted in grid-points. One could ask: being at one tree on the horizontal edge of the wood, how could I choose an angle to look through the wood so to see only one tree?
What to say? Math is everywhere if you look for it…