Lines covering all lattice points
is a set of lines in , each of which passes through the origin. Every lattice point such that is on at least one line in . What is the minimum size of ?
Details and assumptions
A lattice point satisfies the condition that and are integers.
The answer is 21.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Moderator note:
Good simple approach which works because we are looking at small values. What would be your answer if 5 was replaced by 50? Is there another way which avoids listing out all 2601 pairs?
Since, the lines passes through the origin. Each point must be on a line in the form y = mx.
For m = 1, the points obtained are (0,0),(1,1),(2,2),(3,3),(4,4),(5,5). For m = 2, the points obtained are (0,0),(1,2),(2,4) For m = 0.5, the points obtained are (0,0),(2,1),(4,2) For m = 0, the points obtained are (0,0),(1,0),(2,0),(3,0),(4,0),(5,0). The equation x = 0 gives (0,0),(0,1),(0,2),(0,3),(0,4),(0,5).
Thus, this 5 equations cover 20 of the 36 points. Since, all the values of x and y in each of the other pairs of (x,y) are co-prime, there exists no line that connects two of these points together(along with the origin).
Thus, for the 16 other points, we need 16 more lines.
Thus, size of S = 16 + 5 = 21