Problem A. 833. (October 2022)
A. 833. Some lattice points in the Cartesian coordinate system are colored red, the rest of the lattice points are colored blue. Such a coloring is called finitely universal, if for any finite, non-empty \(\displaystyle A \subset \mathbb{Z}\) there exists \(\displaystyle k\in \mathbb{Z}\) such that the point \(\displaystyle (x,k)\) is colored red if and only if \(\displaystyle x\in A\).
\(\displaystyle a)\) Does there exist a finitely universal coloring such that each row has finitely many lattice points colored red, each row is colored differently, and the set of lattice points colored red is connected?
\(\displaystyle b)\) Does there exist a finitely universal coloring such that each row has a finite number of lattice points colored red, and both the set of lattice points colored red and the set of lattice points colored blue are connected?
A set \(\displaystyle H\) of lattice points is called connected if, for any \(\displaystyle x,y\in H\), there exists a path along the grid lines that passes only through lattice points in \(\displaystyle H\) and connects \(\displaystyle x\) to \(\displaystyle y\).
Submitted by Anett Kocsis, Budapest
(7 pont)
Deadline expired on November 10, 2022.
a) There is such a colouring.
We can list all possible colorings of a row with finitely many red grid points. This is a known statement, it depends on the following: for each \(\displaystyle k\), it is easy to list the colorings that contain exactly \(\displaystyle k\) red grid points (for example, in ascending order by the sum of the absolute values of the coordinates of the red grid points, and where there is equality we arbitrarily decide who comes first). For each \(\displaystyle k\), let this list be \(\displaystyle a^k_1, a_k^2, \ldots\). Then we combine them together somehow, for example like this:
\(\displaystyle a^1_1, a^2_1, a^1_2, a^3_1, a^2_2, a^1_3, a^4_1, \ldots\)
So let \(\displaystyle b_1, b_2, \ldots\) be all possible colorings of a row with only finitely many red fields. Also, let's list the even numbers in the following way:
\(\displaystyle 0,2,-2,4,-4,6,-6,\ldots\)
Do the following algorithm. In each step, take the next \(\displaystyle x\) even number in the enumeration, and the next \(\displaystyle b_i\) that we haven't used yet. Color the \(\displaystyle x.\) row by \(\displaystyle b_i\). After that, if \(\displaystyle x>0\), color the \(\displaystyle (x-1).\) row so as to connect the newly colored row with the previously colored ones, this is easy to do, color enough (but finite) consecutive fields in the \(\displaystyle (x-1).\) row so as to connect the \(\displaystyle x.\) and \(\displaystyle (x-2).\) rows. Take care to color the \(\displaystyle (x-1).\) row to something we haven't used yet, but this is easily accomplished by coloring a few more fields in the row red, since we've only colored a finite number of rows so far. If \(\displaystyle x<0\), then similarly, only then the \(\displaystyle (x+1).\) row needs to be coloured as described above to link the new row to the previously coloured ones.
It's clear from the algorithm that we end up with an appropriate coloring, no two rows will be identical, and each row will be placed on some row with only a finite amount of red, which is exactly what we wanted.
b) There is also a construction here. Similarly, list all finite red colorings with at least one red, again let \(\displaystyle b_0, b_1, \ldots \) and let \(\displaystyle b_0\) be the set where only 0 is red. Now we'll put \(\displaystyle b_i\) in the row \(\displaystyle 100i.\) (\(\displaystyle 100\) is not important at all, a much smaller constant is enough, it's just more visual). Color the entire bottom half of the plain white, so that the all-white line is now definitely included. We go by induction. The first step is simple, we put \(\displaystyle b_0\) into row 0. Then suppose that we have already put \(\displaystyle b_n\) into row \(\displaystyle 100n.\) so that the red part is connected so far, and the white part is connected. Then cover all the fields that have been colored red so far with a huge rectangle so that there are no red cells on the perimeter and the top of the rectangle is in row \(\displaystyle (100n+50)\). Drive up a one-lane thin red road to here. This will guarantee the reds will be connected, and it is therefore clear that the whites will be connected, because you can get to the border of the white rectangle from anywhere. From line \(\displaystyle (100n+50)\) to \(\displaystyle (100n+99).\) take lines with enough adjacent members colored red, but with only these, so they are in a block, to avoid white members being enclosed. In the \(\displaystyle (100n+99).\) row, put enough red cells such that when we put \(\displaystyle b_{n+1}\) into the \(\displaystyle (100n+100).\) row the reds are still connected. It is clear from the construction that the whites are then also connected. Finally, we need to consider, but it is also clear, that reds and whites will be connected in the end, so we have a suitable finitely universal coloring.
Note: We wanted to pose the problem with part b) also caontaining the different row property. We also write a solution for this.
In this case the answer is negative. Indirectly suppose that there is such a coloring. There is a row where only \(\displaystyle 0\) is colored, suppose this is row \(\displaystyle 0\). We find an infinitely long path starting at \(\displaystyle (0,0)\), passing only through red grid points, and running entirely in the \(\displaystyle \{(x,y): y>0\}\) upper half-plane, and one that runs entirely in \(\displaystyle \{(x,y): y<0\}\) lower half-plane. If such a path is found, then connecting them at the origin gives a path that is infinitely long in both directions and bisects the plane, so that, for example, the points \(\displaystyle (1,0)\) and \(\displaystyle (-1,0)\) cannot be connected by a white path, which is a contradiction.
It is enough to construct an infinitely long path on the upper plane, the lower one goes in a similar way. From the point \(\displaystyle (0,0)\) you can reach all red points on the upper half-plane with a path (which does not intersect itself), since the red points are connected. It is also clear that for each such path we stay on the upper half-plane all the way, since only \(\displaystyle 0\) is coloured in row \(\displaystyle 0\). There are an infinite number of red cells on the upper half-plane, so this gives us an infinite number of (finitely long) paths. Now we use these to produce an infinitely long path.
The first step of each path is up. Since there are infinitely many paths, and the second step can only be of 3 kinds (up, right, left), we will have a 2nd step that is the 2nd step in infinitely many paths. Let's choose this 2nd step and forget the other paths where we do a different 2nd step. Repeat the same: for the 3rd step there are at most 3 different possibilities, so there are infinitely many paths with the same 3rd step, fix this 3rd step and leave the other paths. There still remain infinitely many paths whose first three steps are the same as the fixed steps. So on, for every \(\displaystyle n\) we find a step \(\displaystyle n\). Finally, with this sequence of steps, we end up with an infinitely long red path, just as we wanted. This concludes the proof.
Statistics:
23 students sent a solution. 7 points: Czanik Pál, Diaconescu Tashi, Farkas 005 Bendegúz, Molnár-Szabó Vilmos, Nádor Benedek, Németh Márton, Seres-Szabó Márton, Simon László Bence, Szakács Ábel, Tarján Bernát, Wiener Anna. 6 points: Lovas Márton, Móricz Benjámin. 4 points: 4 students. 3 points: 2 students. 2 points: 2 students. 1 point: 2 students.
Problems in Mathematics of KöMaL, October 2022