I loved this question from the math prize for girls. Here it is and my solution:

**A lattice point is a point in the plane whose two coordinates are both integers. A lattice line is a line in the plane that contains at least two lattice points. Is it possible to color every lattice point either red or blue such that every lattice line contains exactly k=2017 red lattice points? Prove your answer is correct. **

At first I thought the answer is no! It’s easy to prove that if k=1 then it’s impossible: assume such a coloring exists, by construction, every lattice line contains exactly one red lattice point. Choose two red lattice points on separate lines and draw the line containing them—you now have a lattice line containing at least two red lattice points. —><—

Next, I tried to construct a coloring for k=2 and prematurely convinced myself it wasn’t possible. A day later, with the problem still fresh in my mind I kept thinking about maybe proving the problem via induction, but was troubled by the fact that it doesn’t hold for the base case k=1!

Unconvinced about the answer being no, I kept thinking that the case k=1 is somehow special, and that the real base case starts with k=2. In hindsight this is obvious, but it took me a bit to see it. The case k=1 is special because one lattice point does not uniquely determine a line; infinitely many lattice lines go through any one lattice point. For every other k, we have that the k lattice points uniquely determine the line through them. So maybe the answer is yes for all k > 1.

I couldn’t imagine a way to explicitly generate the coloring so I convinced myself that to prove it’s possible we have to do it via induction. For this we need to be able to enumerate all possible lattice lines. In order to do this we need to show that the set of all lattice lines in R^2 is countable. Basic properties of countability tell us that all pair of integers are countable, and all pairs of pairs of integers, and thus all lattice lines since each one can be specified as a pair of pairs of integers.

Great, so since the set of all lattice lines is countable then we can enumerate all lattice lines as L:={l1, l2, l3….}. Next thing I noticed is that any lattice line must necessarily contain an infinite set of lattice points on it. * We now construct the desired coloring:

- Start by coloring each lattice point blue.
- At each step t in {1,2,3,…} we will recolor a finite number of the lattice points red. At each step t, we will also partition L into two disjoint sets S1 and S2: S1:={l1,l2,…,l(t-1)} and S2:={l{t}, l(t+1),…} (for t=1 S1 is empty). So that at step t>1 each line in S1 contains
*exactly*2017 red lattice points and each line in S2 contains*at most*2017 red lattice points. Note that at step t there are a finite number of red lattice points on the lattice plane, hence there a finite number of lattice lines which contain at least two red lattice points. So that the set of lines with exactly 2017 red lattice points is also finite. Let F be the finite set of lines with exactly 2017 red points. Look at line lt, and note that every line in L (except lt) intersects it in at most one point. Let I be the finite set of points which are intersection points between lt and a line in F. Because I is finite and at most 2017 points of lt are red, there are infinitely many lattice points on lt that are neither in I nor currently red. Recolor up to 2017 of these points red until lt has exactly 2017 red lattice points. - We prove that we can repeat the previous step for every step t. We proceed by induction:
- The base case t=1 holds since by construction we start with the all-blue coloring.
- Suppose that the procedure is possible for step t.
- Consider step t+1, since every line except lt itself intersects lt in at most one point, every line except lt will gain at most one red point during time (t+1). By construction, at step t+1 the lines in S1 will still each contain exactly 2017 red points, and lt itself will have exactly 2017 red points before we move onto step (t+2) (by appropriate recoloring). Whereas every line in S2 at step (t+1) will have at most 2017 red points before we move onto step (t+2) (since we don’t recolor any lines in S2 which already contain exactly 2017 red points), completing our proof by induction.

By taking this process to its limit, i.e., repeating for infinitely many steps, we get the desired coloring of the lattice plane.

Q.E.D.

Note how the ability to enumerate all lattice lines allows us to construct such a coloring via an abstract but systematic process. Approaching this problem by trying to explicitly color the plane makes it much harder to tackle!

*By contraction, assume that there is some lattice line with finitely many lattice points. Choose the two lattice points with the smallest distance and construct the right-angled triangle containing these two points as vertices. By replicating this triangle in both directions along this line, by similar triangles, we can show that repeating vertices are all lattice points and infinitely many of them lie on the line. —><—

Thank you to Ken Fan at Girls’ Angle for initially pointing out that the induction cannot be done on the lines in set L. Can you see why not?