Gift for Anton#396

Gift for Anton (Editorial)

Problem Author:

Kostiantyn Lutsenko

Prepared by:

Kostiantyn Lutsenko

Matviy Strechen

Pavlo Tsikalyshyn

Analysis written by:

Kostiantyn Lutsenko

10pt

Block 0

If there is at least one "4", then all adjacent to it are also "4", all adjacent to this "4" are also "4", and so on. And since the table is finite, this cannot happen.

If there is at least one "3", then consider the highest of all "3"s. Then in all directions except upwards, it borders with other "3"s. Consider the "3" that is to the right of the initial one. Similarly, it has other "3"s to the left, below, and to the right. And so on, we can expand to the right to infinity, but the table is finite, which is a contradiction.

Twos form cyclic structures. Ones are arranged in dominoes. Zeros are isolated from other zeros. This is clearly visible from the example in the problem statement.

The reflections described above are not mandatory, but such analysis of the problem greatly helps in finding a solution.

Block 1 (n = 1)

It is easy to notice that by alternating dominoes "1-1" and isolated "0"s, one can obtain a chain of arbitrary length.

Block 2 (n = 2)

If we duplicate the solution from Block 1 and increase all numbers by 1, it will work for this block.

Block 2 (n = 3)

If we frame it with "2"s, we will have a strip of 1 \times (m-2), for which we can invoke the solution for Block 1.

Block 3

Let's take the example from the problem statement. We will cut off the leftmost and rightmost columns. We will change the corners from "1" to "0".

Blocks 5-11

If we place two dominoes with "1" and an isolated "0" next to a square with "2", we will get a pattern of 3 \times 3, which can be repeated infinitely.

Moreover, if we consider a specific row, we will notice that we always have a situation like in Block 1: two identical digits, one different, two identical, one different... This means that just like in Block 1, we can choose a segment of columns so that there are no issues at the boundaries. Similarly, we can choose a segment of rows so that there are no issues at the boundaries. The answer is a table formed by the intersection of these rows and columns.

Block 8