Planning for the inevitable
Suppose nine two dimensional integer lattice points are chosen such that no three of them lie on the same line.
Out of all possible line segments between pairs of those nine points, some line segments may contain integer lattice points besides the original nine points and we call them the " inevitable lines ". What is the minimum number of "inevitable lines"?
- Yet another question from USAMTS but has been paraphrased, try to see if you can solve that.
The answer is 6.
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
All points can be categorized into - (even, even) - (odd, odd) - (even, odd) - (odd, even) Base a common sense in the following cases an "inevitable line" would occur when two points from the same category are connected . By Pigeonhole Principle there are at least 3 points in 1 category. Thus segments would contain at least C 3 2 + C 2 2 + C 2 2 + C 2 2 = 6 "inevitable lines"