In the plane, there is a figure in the form of an $L$-tromino, which is composed of $3$ unit squares, which we will denote by $\Phi_0$. On every move, we choose an arbitrary straight line in the plane and using it we construct a new figure. The $\Phi_n$, obtained in the $n$-th move, is obtained as the union of the figure $\Phi_{n-1}$ and its axial reflection with respect to the chosen line. Also, for the move to be valid, it is necessary that the surface of the newly obtained piece to be twice as large as the previous one. Is it possible to cover the whole plane in that process?
Problem
Source: Serbia TST 2024, P6
Tags: combinatorics
R8kt
25.05.2024 13:35
Bumpbump
YaoAOPS
08.06.2024 11:55
Here's a localization of the official solution as can be found at here.
The answer is in fact yes.
First, construct the following figure consisting of four $2 \times 3$ rectangles.
[asy][asy]
import geometry;
size(10cm);
int W=5;
int H=6;
for (int i=-W; i<=W; ++i) {
draw( (i,-H+1)--(i,H), rgb("333333")+dotted );
}
for (int i=-H+1; i<=H; ++i) {
draw( (-W,i)--(W,i), rgb("333333")+dotted );
}
pen purpleL = purple+white+white;
pen pinkL = pink+white+white;
void drawL(real a, real b, pen c=pinkL, pen d=pinkL) {
filldraw(shift(0,0.5+b*-0.5)*((2*a,2*b)--(4*a,2*b)--(4*a,4*b)--(3*a,4*b)--(3*a,3*b)--(2*a,3*b)--cycle), c);
filldraw(shift(0,0.5+b*-0.5)*((2*a,3*b)--(2*a,5*b)--(4*a,5*b)--(4*a,4*b)--(3*a,4*b)--(3*a,3*b)--cycle), d);
}
drawL(1,1);
drawL(-1,1, purpleL);
drawL(1,-1);
drawL(-1,-1);
draw(line((0,0), (1,1)), dashed+red);
draw(line((0,0.5), (1, 0.5)), dashed+red+blue);
draw(line((0,0), (0, 1)), dashed+red+blue+blue);
[/asy][/asy]
This can be done by reflecting about the red, pink, purple lines in that order starting from the purple $L$-tromino.
For simplicity, we can then take a scaling that instead makes it so we are considering $1 \times 1$ squares that are placed as follows.
[asy][asy]
import geometry;
size(5cm);
int W=3;
int H=3;
for (int i=-W; i<=W; ++i) {
draw( (i,-H+1)--(i,H), rgb("333333")+dotted );
}
for (int i=-H+1; i<=H; ++i) {
draw( (-W,i)--(W,i), rgb("333333")+dotted );
}
pen pinkL = pink+white+white;
filldraw(shift(1,1)*unitsquare, pinkL);
filldraw(shift(1,-1)*unitsquare, pinkL);
filldraw(shift(-2,-1)*unitsquare, pinkL);
filldraw(shift(-2,1)*unitsquare, pinkL);
[/asy][/asy]
Afterwords, we can then solve covering the plane vertically and horizontally separately now by reflecting along the red lines drawn and repeating.
Claim: In the one dimensional case of covering $\mathbb{Z}$ and reflecting across some real $r + x \to r - x$, both the tuples $(1, 0, 1)$ and $(1, 0, 0, 1)$ tile where the tuples represent consecutive elements of $\mathbb{Z}$.
Proof. The $(1, 0, 1)$ follows immediately by reflecting to get $(1, 1, 1, 1)$, and then reflecting to get a tuple $(\underbrace{1, 1, \dots, 1, 1}_{2^n \ \text{ones}})$. The $(1, 0, 0, 1)$ is a similar. Reflect to get $(1, 0, 1, 1, 0, 1)$, which then ends up repeating into $(1, 0, \underbrace{1, 1, \dots, 1, 1}_{2^n - 4 \ \text{ones}}, 0, 1)$. $\blacksquare$
Here's the first two reflections shown:
[asy][asy]
import geometry;
size(5cm);
int W=4;
int H=3;
for (int i=-W; i<=W; ++i) {
draw( (i,-H)--(i,H), rgb("333333")+dotted );
}
for (int i=-H; i<=H; ++i) {
draw( (-W,i)--(W,i), rgb("333333")+dotted );
}
pen pinkL = pink+white+white;
pen purpleL = purple+white+white;
filldraw(shift(2,1)*unitsquare, purpleL);
filldraw(shift(2,-1)*unitsquare, purpleL);
filldraw(shift(-1,-1)*unitsquare, purpleL);
filldraw(shift(-1,1)*unitsquare, purpleL);
filldraw(shift(2,0)*unitsquare, pinkL);
filldraw(shift(2,-2)*unitsquare, pinkL);
filldraw(shift(-1,-2)*unitsquare, pinkL);
filldraw(shift(-1,0)*unitsquare, pinkL);
filldraw(shift(0,1)*unitsquare, purpleL+blue+purpleL);
filldraw(shift(0,-1)*unitsquare, purpleL+blue+purpleL);
filldraw(shift(-3,-1)*unitsquare, purpleL+blue+purpleL);
filldraw(shift(-3,1)*unitsquare, purpleL+blue+purpleL);
filldraw(shift(0,0)*unitsquare, pinkL+blue+pinkL);
filldraw(shift(0,-2)*unitsquare, pinkL+blue+pinkL);
filldraw(shift(-3,-2)*unitsquare, pinkL+blue+pinkL);
filldraw(shift(-3,0)*unitsquare, pinkL+blue+pinkL);
draw(line((0,0),(1,0)), red+dashed);
draw(line((0,0),(0,1)), red+dashed);
[/asy][/asy]
I overlooked the $(1, 0, 0, 1)$ case and thus died on this problem for an embarassing long period of time.
In hindsight, the fact that there's no good way of proving impossibility should've been a sign of the opposite.
It's not hard to convince yourself that it is impossible tough; if you trick yourself into believing that a construction is only possible if the reflected figure is continguous at some point in time, it's probably joever.
By considering adjacent $L$ trominos, it's not hard to prove that all reflections must be at multiples of $45^\circ$ wrt the orientation of the base tromino.
I want to say this is 40 MOHS but I mostly just skill issued majorly lmao.