4. Let there be a square $ABCD$. We cut the square $ABCD$ into four congruent squares (along the lines that connect the midpoints of opposite sides). Then we choose one of the resulting squares and cut it into four congruent squares. Then we choose one of (a total of seven) resulting squares and cut it into four congruent squares. We call a quad-partition the collection of squares obtained by repeating this process a finite number of times. Two squares in a quad-partition are adjacent if one of their sides contains a side of the other (it is possible for the sides to coincide). We say that a quad-partition is balanced if the ratio of the sides of any two adjacent squares is 1, 2, or $\frac{1}{2}$. Determine the smallest natural number $k$ such that the squares of any balanced quad-partition can be colored with $k$ colors so that any two adjacent squares are always colored differently.

## Fourth Grade - A Category
4. Let us note that, starting from the square $ABCD$, after two cuts in the thus obtained quad-partition (which is balanced), there are three squares among which any two are adjacent, so at least 3 colors are needed to color this quad-partition, i.e., $k \geqslant 3$. Let us prove that 3 colors are also sufficient, i.e., that every balanced quad-partition can be colored with 3 colors.

Let the vertices of the square $ABCD$ have coordinates $(0,0),(0,1),(1,1)$, and $(1,0)$. The squares in each quad-partition have side lengths $\frac{1}{2^{m}}$ for a non-negative integer $m$ (not necessarily the same for all squares in the quad-partition), and the center of a square with side length $\frac{1}{2^{m}}$ is located at the point $\left(\frac{i}{2^{m+1}}, \frac{j}{2^{m+1}}\right)$ for some odd numbers $i$ and $j$. This is easily proven by induction: for the square $ABCD$, the statement is satisfied, and during one cut of a square with side length $\frac{1}{2^{m}}$ and center at $\left(\frac{i}{2^{m+1}}, \frac{j}{2^{m+1}}\right)$, we obtain four squares with side length $\frac{1}{2^{m+1}}$ and centers at $\left(\frac{i}{2^{m+1}} \pm \frac{1}{2^{m+2}}, \frac{j}{2^{m+1}} \pm \frac{1}{2^{m+2}}\right)$, i.e., at $\left(\frac{2i \pm 1}{2^{m+2}}, \frac{2j \pm 1}{2^{m+2}}\right)$, which completes the inductive step.

Now we will construct a coloring of any balanced quad-partition with 3 colors. Let the colors be 0, 1, and 2. A square with center at $\left(\frac{i}{2^{m+1}}, \frac{j}{2^{m+1}}\right)$ (its side length is $\frac{1}{2^{m}}$) will be colored with the color $(-1)^{m}(i-j)$, where the color is calculated modulo 3. Let us prove that this coloring satisfies the conditions of the problem. Consider two adjacent squares (say one next to the other; analogously if one is above the other). If they have the same side length, say $\frac{1}{2^{m}}$, then they have centers at $\left(\frac{i}{2^{m+1}}, \frac{j}{2^{m+1}}\right)$ and $\left(\frac{i}{2^{m+1}} + \frac{1}{2^{m}}, \frac{j}{2^{m+1}}\right)$, i.e., $\left(\frac{i+2}{2^{m+1}}, \frac{j}{2^{m+1}}\right)$, and are colored with the colors $(-1)^{m}(i-j)$ and $(-1)^{m}(i+2-j)$, which are clearly different colors. If they have different side lengths, say $\frac{1}{2^{m}}$ and $\frac{1}{2^{m+1}}$ (they must be two consecutive powers of two due to the balanced nature), then they have centers at $\left(\frac{i}{2^{m+1}}, \frac{j}{2^{m+1}}\right)$ and $\left(\frac{i}{2^{m+1}} \pm \left(\frac{1}{2^{m}} - \frac{1}{2^{m+2}}\right), \frac{j}{2^{m+1}} \pm \frac{1}{2^{m+2}}\right)$, i.e., $\left(\frac{2i \pm 3}{2^{m+2}}, \frac{2j \pm 1}{2^{m+2}}\right)$, and are colored with the colors $(-1)^{m}(i-j)$ and $(-1)^{m+1}(2(i-j) \pm 3 \pm 1)$ (the signs represented by “, ” can be chosen independently of each other); the second color modulo 3 reduces to $(-1)^{m}(i-j \mp 1)$, so the colors are different in this case as well. Thus, the problem is solved.

## Fourth Grade - A Category