I wanted to make a test bank of graphs of linear equations for my algebra classes. I want the $y$-intercept of each graph to be an integer no less than $-10$ and no greater than $10$. Generally, you want these graphs to be small, so i've decided on a $20 \times 20$ grid (10 units from the origin). Additionally, i would like students to be able to see a second integral point on this grid, so they can find the slope. How many possible graphs would be in this test bank? How did you get the solution?
Number of distinct graphs with y-intercepts that are integers between $-10$ and $10$
3 Answers
Here's a simple upper bound. There are 21 points on the $y$-axis, and there are 420 points in your grid that are not on the $y$-axis, so there are at most $21\times420$ lines. Of course, there are actually fewer, because lines with 3 or more points are getting counted more than once. Two random integers less than $n$ are relatively prime with probability $6/\pi^2$ for large $n$, so my guess is that $(6/\pi^2)\times21\times420$ is a decent estimate for the answer.
As a start, we compute exactly the number of such lines with $y$-intercept $0$.
There are $2$ (the axes) plus twice the number with positive slope. How positive slopes are possible? There is the special case slope $1$. Then there are the proper (reduced) fractions such as $7/9$ and $1/3$, plus their reciprocals $9/7$ and $3$. So we first count the reduced proper fractions $a/b$ where $1\le a.
For any $b \ge 2$, the number of such fractions is the number of positive integers $ which are relatively prime to $b$. This is $\varphi(b)$, where $\varphi$ is the Euler $\varphi$-function.. There is a formula for $\varphi(n)$ in terms of the prime factorization of $n$, but for small numbers we can easily determine $\varphi(b)$ directly from the definition.
Thus the number of reduced proper fractions as $b$ goes from $2$ to $10$ is $\varphi(2)+\varphi(3)+\varphi(4)+\cdots+\varphi(9)+\varphi(10).$ This is $31$. Multiply by $2$ to include the reciprocals. We are at $62$. Add $1$ for the line with slope $1$. Double to include negative slopes. Add $2$ for the axes. We get $128$. Nice number! Often, when we get a nice number in a complicated way, the number is trying to tell us that we are overlooking a much better solution. I believe that is not true in this case.
This is just a small start. We need to count the lines with intercepts $-1$, $-2$, and so on up to $-10$, and double to take care of the positive intercepts. For each of $-1$, $-2$, up to $-10$ we can take a limited advantage of symmetry, since there are just as many lines with positive slope as with negative slope.
The $7/9$, $9/7$ symmetry breaks down, however, and the work becomes more unpleasant. For intercept $-3$, for instance, the numerators of the slopes can go to $13$, while the denominators stay at $10$ or below.
Unless one is very motivated, it is excessively tedious to do the work by hand. But it would be easy to write a computer program that does the job.
If you happen to count (by hand) the number with intercept say $-10$, I can verify that you are right.
If you extended by $11$ in all directions (instead of $10$), then your grid is a picture of $\mathbb{F}_{23}^2$. (It's nicer to work with the field $\mathbb{F}_{23}$ than the non-field $\mathbb{F}_{21}$.) Your question translates to counting how many affine lines are there in this vector space. Lines in this space wrap around the edges. Possible slopes are $0$ through $22$. After wrapping, every line encounters $23$ integral points on your grid.
Edit: As Gerry points out in the comments, this whole argument doesn't work. It's in this next paragraph that I say something that can't be backed up.
First, if $b=0$, every (non $y$-axis) point in the grid is on a unique line. So whatever line you imagine for $\mathbb{R}^2$ translates to a unique line in $\mathbb{F}_{23}^2$ by focusing on the integral point with the smallest positive $x$-value.
We have $23$ lines through the origin in $\mathbb{F}_{23}^2$, counting the $23$ possible slopes. Coupled with translation by $23$ possible $y$-intercepts, there are $23^2$ such lines. If you like, add vertical lines, of which there are $23$.
So either $23^2$ or $23\cdot24$, depending on what you are after. (This argument does not work exactly the same for $\mathbb{F}_{21}$, since lines with different slopes can cross at more than one point.)
-
0@Gerry Ah, you're right. The lines in the modular space don't genuinely correspond to the lines in $\mathbb{R}^2$ that hit integral points. Some of the $\mathbb{F}^2$ lines "correspond" to multiple $\mathbb{R}^2$ lines, and then we will have the same counting issue as from the start - no progress made. It seemed like a good viewpoint, but I guess it's not helping. – 2012-01-26