Beelines
Problem
Take a look at the video below:
If you can't see the video, click below for a description.
If I choose the point (5, 5) and draw a line segment joining the point to the origin, my line passes through 5 grid squares.
If I choose the point (4, 3) and draw a line segment joining the point to the origin, my line passes through 6 grid squares.
If I choose the point (6, 4) and draw a line segment joining the point to the origin, my line passes through 8 grid squares.
Draw some line segments of your own, and record how many grid squares each one passes through.
You may wish to explore this using the GeoGebra applet below.
Can you find a relationship between the coordinates of the end of the line segment and the number of squares it passes through?
If I draw the line segment joining the origin to the point (50, 37) how many grid squares will it pass through?
If I draw the line segment joining the origin to the point (96, 72) how many grid squares will it pass through?
Can you find a line segment that passes through exactly 24 squares?
Can you find more than one?
Can you work out how many grid squares a line segment passes through, if you are given the coordinates of the two endpoints, where neither is at the origin?
You could also investigate the number of grid lines crossed...
Working out which grid squares a straight line crosses allows you to create algorithms for drawing straight lines on a computer, where each pixel is a grid square. Read more about line drawing algorithms here.
Getting Started
Start by drawing some lines and recording how many squares they cross.
What do you notice about the coordinates of lines that pass through the corners of grid squares?
Alternatively, you can install GeoGebra on your computer and download and run the GeoGebra file yourself.
Student Solutions
No one sent us a complete solution to this problem, but here is the start of a solution which shows some good mathematical thinking and a systematic way of working.
We decided to investigate what happens if you keep the $x$ coordinate the same and change the $y$ coordinate. Here is our table to show the number of squares and gridlines crossed when the $x$ coordinate is $5$.
We noticed a pattern for the number of squares crossed, which works for every $y$ coordinate we tried except $5$. If you add together the $x$ and $y$ coordinates and take away 1, you get the number of squares crossed. This is because for example to get from (0,0) to (5,3) you go along 5 squares and up 3 squares, meaning that you travel through 8 squares altogether, but that counts the corner square twice so you need to take away 1.
It doesn't work for (5,5) because you go diagonally through the corners of the squares instead of cutting through the edges.
Can anybody build on this thinking and explain the patterns found?
Update: Jacky from Merici College in Canberra, Australia, drew some diagrams and compiled tables to try to notice some patterns.
Alex (also from Merici College) sent us the following solution that offers a formula. Does it always work?
I have found through investigation that we can predict the number of squares a line passes through starting at 0 using the formula:
(A) Number of squares = ( x + y ) - (highest common factor of x and y)
This is why:
In my investigation I found the common pattern of:
(B) Number of squares = (x + y ) - 1 worked for some of the coordinates. I then tried to spot a pattern within these numbers and found that it occurred if either x or y was a prime number. Using this fact I investigated further and found that a common relationship with all the numbers was x and y's highest common factor.
After I figured this out, I could see that the absolute highest amount of squares a line could go through used the formula B.
Here's an example: Imagine line goes from (0,0) to (4,12). The highest common multiple of (4,12) is 4. This line goes through the intersection point of squares at point (1,4), (2,8) and (3,12).
Because this line goes through these intersections instead of crossing squares, 3 squares are 'missed', plus the original 1 in the formula B, which reduces the number of squares by 4.
Well done, Alex and Jacky!
Teachers' Resources
Why do this problem?
Working on this problem will give students an opportunity to make and justify conjectures that link numerical and geometrical ideas. It offers students valuable experience of working on coordinate geometry and will develop their understanding of factors and multiples.
Possible approach
This printable worksheet may be useful: Beelines.
You may be interested in our collection Dotty Grids - an Opportunity for Exploration, which offers a variety of starting points that can lead to geometric insights.
Show the video below, or introduce the problem in the same way. You could use this Geogebra applet or download this Geogebra file.
"In a while I'm going to give you the coordinates of the point at the end of a line, and challenge you to tell me how many squares the line will pass through."
Students could work in pairs, choosing coordinates and keeping a record of their results.
Once students have a selection of results, invite them to look for patterns.
If they find it hard to spot any relationships, here are some prompts:
"Group together all your results where the x and y coordinate are the same. What do you notice? Will it always happen?"
"What about results where the x coordinate is twice the y coordinate? Or three times?"
"What about results when the two coordinates have no factors in common?"
To finish off, choose some pairs of coordinates and challenge students to work out quickly how many squares the line will pass through. This is a very good activity for students to display their answers on mini-whiteboards.
Finally, take some time to discuss the geometrical reasons why a straight line joining the origin to a point with coprime coordinates will not go through any grid squares, and the reason why we are able to calculate the number of squares the lines will go through without needing to draw and count.
Possible extension
This Wikipedia article about line-drawing algorithms may be of interest to students who are keen on computer programming.
You could challenge students to find a way to work out whether a given line passes through a given square on the grid (without drawing!).
Possible support
Coordinate Patterns might provide a suitable preliminary activity.