9
$\begingroup$

The problem is from an advanced 8th grade math curricula, and marked with a star:
*The topic is "Real numbers"

The plane is covered by an infinite square grid. Is it possible to draw a straight line through any node that does not pass through any other node in the grid?

A hint to the problem in the textbook:

Consider a coordinate system, the origin of which is an arbitrary grid node, and the coordinate axes are directed along the grid lines. For a unit segment, take the length of the side of the grid square. Then each grid node will have integer coordinates. Consider the line $y = \sqrt{2}x$.

Here's the graph $y = \sqrt{2}x$:

enter image description here

The textbook is not in English, and I couldn't find any relevant, helpful information regarding the problem neither in my language nor in English. Any additional hints, suggestions or help is very appreciated.

Edit*:
As @Empy2 noted, the function is actually $y = \sqrt{2}x$, not $y = \sqrt{2x}$. Now, the question remains. The textbook gives the answer right away, and as you can see on the graph below, the line $y = \sqrt{2}x$ is indeed the answer, but how to arrive at the given solution?

$\endgroup$
4
  • $\begingroup$ It will be really helpful if you define a "node" $\endgroup$
    – Gwen
    Commented May 2 at 14:21
  • $\begingroup$ 8th graders are learning these things!!!! This is mind blowing!!! $\endgroup$ Commented May 4 at 8:30
  • $\begingroup$ @MathStackexchangeIsNotSoBad very few of them. This is an advanced 8th grade curricula, + this is not a problem that can be encountered in a school test or homework. Problems marked with asterisks such as this one are usually from math Olympiads. But yeah, this is fascinating anyway. $\endgroup$ Commented May 4 at 14:54
  • 1
    $\begingroup$ @curioushuman this is absolutely fascinating...I will never expect myself as a past 8th grader, to solve this at that time, tho I can now😅 $\endgroup$ Commented May 4 at 15:13

5 Answers 5

27
$\begingroup$

Let the Node be $(X_1,Y_1)$

Let us assume , it goes through Node $(X_2,Y_2)$

We can then see that the Slope of the line is $m=(Y_2-Y_1)/(X_2-X_1)$ which is a rational number.

Hence when we choose some line with Slope $m=\sqrt{2}$ , $m=\sqrt{3}$ , $m=\pi$ etc [[ irrational numbers ]] , the line will not give the $(X_2,Y_2)$ to make the Slope rational.

$\endgroup$
3
  • $\begingroup$ Your answer blew up here. Thanks, I've never heard of solving such problems by considering the slope of the line, but it's definitely an interesting way of doing it! $\endgroup$ Commented May 3 at 13:17
  • 1
    $\begingroup$ This is a great answer. It might make it a little more beginner friendly to emphasize that your choice of (X2, Y2) is arbitrary. I know it is, but might be good to emphasize up front and at the conclusion: since the slope from the first node to any arbitrary node is rational, if you choose an irrational slope it won’t pass through any other node. $\endgroup$
    – bob
    Commented May 3 at 14:21
  • 1
    $\begingroup$ @curioushuman - another way to look at it: The equation of a line going through the origin $y = mx$ ($m$ being the slope). You can rearrange that as $y/x = m$ (ignoring the origin where $x = 0$). So, for any "node" that's on the line, $x$ and $y$ will be integers, and $y/x$ will be a rational number (and so will $m$). So you choose an $m$ that is irrational (meaning it cannot be represented as a ratio of two integers), so that there is no such $y/x$. $\endgroup$ Commented May 3 at 20:09
7
$\begingroup$

First, any line drawn on any infinite square grid can be converted to an equivalent line on the grid of all the points with integer coordinates by some combination of rotation, shifting, and scaling (an "affine transformation"). Equivalent here means: imagine that each grid point has a unique label that is preserved by the affine transformation, then the new line passes through the grid points with the same labels as the old line did. This means, if we can find a way to make a line pass through only one point of the grid with integer coordinates, then we also have a way to make a line that passes through only one point of any infinite grid.

Second, a line passing through $(0,0)$ and no other grid points can be converted to a line passing through any other one grid point $(a,b)$ by another affine transformation, so we only have to think about lines passing through the origin: $y = mx + 0$.

Now we can restate the problem algebraically: find a real number $m$ such that, for all integers $i$ except zero, $i\cdot m$ is not an integer. Then the line $y = mx$ will pass through the origin ($m\cdot0 = 0$) but it will miss every other grid point, because whenever $x$ is an integer, $y$ will not be, and vice versa.

And "a real number $m$ such that, for all integers $i$ except zero, $i\cdot m$ is not an integer" is one way to define an irrational number, so we're done! Any line passing through the origin, whose slope is an irrational number, will pass through no other points of the grid with integer coordinates.

$\sqrt2$ is, from one point of view, the simplest possible example of an irrational number; but there are infinitely many more.

$\endgroup$
1
  • $\begingroup$ Thanks for the answer, it's an interesting way of phrasing the proof!) I added an answer to my question, and mentioned you, too. $\endgroup$ Commented May 3 at 13:14
4
$\begingroup$

If one understands the indicated topic of real numbers, the difference between rationals and irrationals, and lines in the coordinate plane, then the answer that immediately jumps to mind is: any line with an irrational slope.

The point is that if a line has any rational slope $a \over b$, then when you move over to integer position $b$ on the horizontal axis, the vertical distance moved will be the integer ${a \over b} \times b = a$, so on one of those integer grid nodes. But if one chooses an irrational slope, then this product is never an integer (roughly speaking, it has no integer denominator which can be canceled out), i.e., never on a grid node.

The hint given in the book just uses the first irrational number most people might think of.

$\endgroup$
1
$\begingroup$

There is an entirely different approach to answering this question that applies to much more general collections of points than regular grids. However, it is definitely not "8th-grade math", or truly "algebra-precalculus", even though it does not involve any calculus. So it is not a good answer to the question. None-the-less, I'll give a brief review of it here, simply because it is one of the cooler things to be found in mathematics. (Note that there are some steps I describe as requiring performing an infinite number of tasks. This was done to avoid also having to discuss induction. In truth the results can be proven in a finite number of steps.)

The approach is a simple counting argument, though it involves counting past infinity. (When Toy Story came out, Buzz-Lightyear's catch-phrase "To Infinity And Beyond!" was intended as a joke, a nonsensical gung-ho statement. But mathematicians had been going beyond infinity for about 150 years by then.) Given two sets, we say that they are the same size if you can match up all the elements of each in a 1-1 correspondence. A set that is the same size as some proper subset of itself is called "infinite".

The simplest example of an infinite set is the natural numbers $\Bbb N$. The entire set of natural numbers is in 1-1 correspondence with just the even natural numbers, as can be seen by matching each number $n$ with the even $2n$. Sets that are the same size or smaller than the natural numbers are called "countable". Sets are smaller than the natural numbers if and only if they are finite. Countably infinite sets are the same size as the natural numbers.

Are there any sets that are not countable? Yes. Georg Cantor showed that the real numbers are "uncountable" by his famous diagonal argument: Suppose there was some one-to-one correspondence between the natural numbers and the real numbers. Then you could list those real numbers off in order of their corresponding natural numbers: $$1:\ 12.\color{red}1097590751423723475904\dots\\ 2:\ 15.2\color{red}743590872354772345234\dots\\ 3:\ 11.85\color{red}73429075893427589755\dots\\ 4:\ 31.823\color{red}6457289076287634970\dots\\ 5:\ 63.3875\color{red}638297548349873443\dots\\ 6:\ 12.34657\color{red}68976204760953985\dots\\\vdots$$

Now, start choosing digits from $1,2,3,4,5,6,7,8$ in this fashion: for each natural number $n$, choose a digit that differs from the $n$-th decimal place to the right of the decimal point in the $n$-th number. In the example, the digits to be avoided are $1,7,7,6,6,6,\dots$ so we might choose $2,8,3,6,4,7,\dots$. Now we form a real number from the list of chosen digits: $$0.283647\dots$$ This number cannot be in the list, because it differs in one of its decimal places from each number in the list. And since we avoided $0$ and $9$, we know that this number has only one decimal expansion, so it cannot be in the list in a different form. This contradicts our assumption that the list contains every real number. So it is impossible for such a list to exist. There cannot be a one-to-one correspondence between the natural numbers and the real numbers.

Since the points on a line can be put in one-to-one correspondence with the set of real numbers, by their distance from a given point on the line, lines contain an uncountable number of points.

Now suppose you have a set $G$ of points in the plane with the property that there is some number $r> 0$ such that each pair of points in $G$ are at least a distance of $r$ apart. $r$ could be large, or it could be incredibly small, say $r = 10^{-100}$. It does not matter. And we place no other restriction of the points in $G$. Then $G$ is a countable set. To see why, for each $n > r$, let $B_n = \{(x,y) \mid x^2 + y_2 \le (n-r)^2\}$ be the disk of radius $n$ about the origin. No matter the value of $n$, only a finite number of points of $G$ can be in $B_n$. If we draw a circle of radius $\frac r2$ around each of the points of $G$, these circles do not overlap, since the distance between any of the points is at least $r$. For the points in $G$ that lie inside $B_n$, their circles are contained within the larger circle of radius $n$ about the origin, which means their combined area is less than $\pi n^2$, the area of the large circle. But the ratio $\frac{\pi n^2}{\pi(r/2)^2}$ of the area of the larger circle to the areas of of each of the small circles is finite. So there can only be a finite number of points of $G$ inside $B_n$. But every point is in some $B_n$, So $G$ is the union of all the $B_n\cap G$ for $n \in \Bbb N$. The countable union of finite sets is countable. So $G$ is countable.

On the other hand, for a point $P$ in the plane, there are an uncountable number of lines that pass through it. To see this, just draw any line $\ell$ that doesn't pass through $P$. Every line through $P$ will intersect $\ell$ is a unique point, except for the one line parallel to $\ell$. Since there are uncountably many points on $\ell$, there are uncountably many lines through $P$.

And this finally gets to the result. If $P$ is any point on the plane (whether in $G$ or not), each point of $G$ other than $P$ forms a unique line with it. As $G$ has only countably many points, but there are uncountably many line passing through $P$, there is guaranteed to be one (actually, uncountably many) which do not intersect $G$ in a point other than $P$.

$\endgroup$
-1
$\begingroup$

It seems to me that @Prem and @zwol both have valid answers.

After thinking on the problem, I believe, the hint from the textbook is basically the answer, and the proof is very simple:
  Any line $y = kx$, where $k$ is an irrational number can pass through only a single node $(x;y)$, where $x, y \in \mathbb{Z}$, — which is $(0;0)$. That's because assuming otherwise would lead to a contradiction, because it would imply that an irrational number $k$ can be represented as a ratio of two integers — $k = \frac{y}{x}$($y$, and $x$ are not equal to $0$) — which contradicts the very definition of an irrational number.

$\endgroup$
9
  • $\begingroup$ You should still accept one of the two answers provided by the others. $\endgroup$ Commented May 3 at 14:57
  • $\begingroup$ @PaulSinclair why? My answer is the answer I'm going to write down in my notebook. $\endgroup$ Commented May 3 at 15:09
  • 2
    $\begingroup$ You have been given good help. Are you ungrateful? The site itself functions better when an answer is accepted. Then the question no longer shows up as unanswered. As for the two answers given, if either were deficient in some way, then it would be appropriate to accept your own answer instead. But I at least see no such deficiency. You should acknowledge their efforts by accepting one of them, and if you haven't already done so, upvoting the other. To do otherwise is just rude. $\endgroup$ Commented May 3 at 15:20
  • $\begingroup$ I am always grateful for the time people dedicate to answer my questions or at least help me in any way. I wouldn't add my own answer if I thought the other two answers suffice as a exhaustive proofs considering the curricula level. The answer of zwol is hard to understand for me personally, and I wouldn't use this proof among others. The answer of Prem uses line slopes, which I've never heard of, even though it's interesting and I understand it. Maybe because we learn math in completely different ways, and in different languages. Yet I thanked both of them and upvoted both of their answers. $\endgroup$ Commented May 3 at 16:17
  • $\begingroup$ I also mentioned both of the users in my answer in the first row, so the accusation about me being ungrateful is false. And yes, I believe the answer I give here is the easiest to understand for an 8th-grader, since this problem is from an 8th grade math curricula. $\endgroup$ Commented May 3 at 16:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .