1
$\begingroup$

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?

3 Answers 3

1

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.

0

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.

0

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