2
$\begingroup$

About half a year ago I posted a problem: "Coloring grid points with two colors" (The problem)

I found it really interesting, so I thought I make some research. Now I need help with my following question. I am thankful for every idea, hint and solution.

Let $S$ be a set of finite many grid points (points in the coordinate system with integer coordinates).

Is it always possible to color them with three colors, red, green and blue , such that in each vertical and horizontal line the following statements is true:

if there are $R$ number of red, $G$ number of green and $B$ number of blue points, than $|R-G|\leq 1, \ |G-B|\leq 1 \ |B-R|\leq 1$?

$\endgroup$
1
$\begingroup$

Yes, this can always be done.

Lemma. This can be done when every vertical and horizontal line with points on it contains exactly $3$ points.

Proof. In this case, all three points on a line must receive different colors.

We can think of this problem as a graph theory problem. Consider the bipartite graph with vertices on one side corresponding to the horizontal lines, and vertices on the other side corresponding to the vertical lines. Put an edge between two vertices when the corresponding lines intersect.

This is a regular graph, since every vertex has three edges out of it. Every regular bipartite graph has a perfect matching (this can be proven using Hall's theorem, for example here): a set of edges covering each vertex exactly once. Back in the grid, this corresponds to a set of points such that every line (vertical or horizontal) contains exactly one of them.

Color this set of points red, and remove the corresponding edges from the graph. The remainder is still regular and bipartite (every vertex has two edges left coming out of it), so there is another perfect matching, giving us another set of points with this property.

Color this second set of points green, and the leftover points blue. Now every line has exactly one red, blue, and green point on it.


In general, we can reduce the problem for an arbitrary grid to an instance of the lemma above.

First of all, we can get rid of horizontal lines with more than $3$ points on them. If a line has $k>3$ points, split it up into $\lfloor \frac k3\rfloor$ lines with $3$ points on them, and maybe a leftover line with $1$ or $2$ points. To do this, move the points so that they still have their old $x$-coordinates (and therefore lie on their old vertical lines) but instead of all having the same $y$-coordinate, only share $y$-coordinates in groups of $3$ or less.

If we can color the new arrangement of points, we could color the old arrangement. On each line with $3$ points, each color is used once; if there is a leftover line of $1$ or $2$ points, no color repeats on it. So each color is used at least $\lfloor \frac k3\rfloor $ times, with $1$ or $2$ colors possibly used $\lfloor \frac k3\rfloor + 1$ times, which still satisfies the conditions.

Then do the same thing for the vertical lines.

Second, we can get rid of horizontal lines with $1$ or $2$ points on them. On every such line, add new points to get up to $3$, making sure not to reuse $x$-coordinates (so that every point added lies on a new vertical line). The condition on the resulting line is that all $3$ points must be different colors, so if we get rid of the new points, the old line still satisfies the coloring condition.

Then do the same thing for the vertical lines. Now all vertical lines have exactly $3$ points on them, but there are some horizontal lines with $1$ point on them (the rest have $3$).

The total number of points must be a multiple of $3$ now. So the number of horizontal lines with $1$ point on them is also a multiple of $3$. Group them up in threes, and for every three points $(x_1, y_1)$, $(x_2, y_2)$, $(x_3,y_3)$ we group together, add more points $(x_4,y_1)$, $(x_4,y_2)$, $(x_4,y_3)$ and $(x_5,y_1)$, $(x_5,y_2)$, $(x_5,y_3)$. This creates two new vertical lines with $3$ points on them, and fills the horizontal lines with $1$ point up to $3$.

Now we are in the case of the lemma, and so we can color the points in a way that satisfies the condition. Undo everything we've done (deleting points we added, and merging together lines we split up) and we get a coloring of the original grid.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.