Let be a set of points in a line. Choose arbitrarily of these points and paint them blue; the other points are painted green. Prove that there exists a line segment that contains exactly points from , of them blue and of them green.
Solution
Let be the segment with exactly points from , the leftmost being the -th point from left to right of , . Define as the number of blue points in . We have to prove that for some .
Notice that since and have common points and because the disjoint segments and cover .
If we are done. So suppose without loss of generality that . So and, since increases or decreases at most 1, there must exist a number such that .
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.