Rosenfeld's $7 \times 7$ square puzzle

Question

A $7 \times 7$ square puzzle may be described as following.

Start with a $7 \times 7$ square divided into $7 \cdot 7$ unit squares. First select a unit square and mark it. And then, in each subsequent step duplicate the current marked squares by translating them onto a set of unmarked squares; mark the new squares so that the number of squares marked is doubled at each step. Determine the maximum number of squares marked repeating this process.

The answer is, amazingly, $32$. I do not include the solution for users pleasure. This puzzle is due to M. Rosenfeld. He wrote in his paper titled 'A "simple" rectangular puzzle'(2007), that

Many mathematicians tried to solve the $7 \times 7$ square puzzle. Some succeeded others did not. Stan Wagon showed Raphael Robinson the puzzle. Raphael contacted me and told me that he solved it while taking a bath. He was wondering why some people had difficulties solving the puzzle. He discovered that if you make a wrong selection in the initial step then it will be impossible to mark 32 squares on the 7×7 square. He sent me a sketch of a very nice proof showing that the final shape of the 32 marked squares is unique (modulo rotations by 90, 180, 270 degrees). The pattern is ($\cdots$ ommited $\cdots$). I hope to publish the proof in the near future.

And as far as I know, he never published the proof. I have tried to prove the uniqueness of the final configuration for several hours in vain. So my question is the following.

The Question Prove that the final configuration of the $7\times 7$ square puzzle with maximum number of marked squares is unique up to rotations and reflections.

Edit: As pointed by @hardmath, the problem has introduced Rosenfeld's article titled 'a dynamic puzzle.'(1991) For the links to the paper quoted and mentioned, see the comment below by hardmath.

Answer 1

I have an answer of how to reach $32$, but I can't prove uniqueness. But I figure it might help other people (especially to confirm uniqueness). See the spoiler if you want to know how to get $32$.

The numbers $k\in\{0,1,2,3,4,5\}$ represent the cells in the $7\times 7$ table below that are marked in the $k$th step, the number $0$ being the original cell. Asterisks $\color{gray}{*}$ or stars ${\color{red}{\star}}$ denote unmarked cells. The table is $$\begin{array}{|c|c|c|c|c|c|c|}\hline{\color{red}{\star}} & \bf 0 & \bf 3&{\color{red}{\star}} &\color{gray}{*}& \color{gray}{*}& {\color{red}{\star}}\\\hline\bf 2 & \bf 3& \bf 1&\bf 3 &\bf \bf 4 & \bf 4& \color{gray}{*}\\\hline\color{gray}{*} &\bf 2&\bf 3 &\bf 4 &\bf 4 & \bf 4&\bf 4\\\hline{\color{red}{\star}} & \bf 5&\bf 5 & {\color{red}{\star}}& \bf 4&\bf 4 & {\color{red}{\star}}\\ \hline\bf 5&\bf 5&\bf 5 &\bf 5 &\bf 5 &\bf 5 & \color{gray}{*}\\\hline\color{gray}{*} & \bf 5&\bf 5 &\bf 5 & \bf 5& \bf 5& \bf 5\\\hline{\color{red}{\star}} & \color{gray}{*}& \color{gray}{*}& {\color{red}{\star}}&\bf 5 &\bf 5 &{\color{red}{\star}}\\\hline\end{array}.$$ I think a uniqueness proof will somehow follow if we can verify that the cells with ${\color{red}{\star}}$ cannot be the starting point, and at any step, these cells must remain untouched.

Answer 2

We will show that $32$ squares are mark-able and the final state is essentially unique. Let $T=\left\{ v_j| j=1,2,3,4,5 \right\}$ be the corresponding translating vectors. We choose orientation so that the right and upward directions are positive. For example, in the following figure, the black square indicates the initial position. For each translation, mark red the corresponding square to the black square. Then the vectors are obtained by reading the relative positions of red squares with respect to the black square. So the vectors are $(0,1)$, $(1,-1)$, $(1,1)$, $(1,3)$, $(3,0)$. Each square corresponds to the linear combination of those vectors with coefficients $0$ or $1$.

The order of the vectors applied is not important. Moreover, changing initial square acts on the set of vectors so that some of the vectors changes its sign. Reflection about the vertical line acts on the vectors so that all the $x$ components of the vectors change their signs. The action of transposing the $x$ and $y$ components corresponds to the reflection about one of the diagonal. This two reflection generates other rigid transformations. Therefore we can rewrite the problem as the following

The set of translation vectors $T$ with the properties is unique up to the action of changing signs of some of members of $T$ and changing all the signs of $x$-components.

1. Each of the $32$ linear combinations of $T$ with $0, 1$ coefficients are mutually distinct.
2. The length of the ranges of $x$ and $y$ components of those $32$ resulting vectors does not exceed $6$.

We want to prove that the set of vectors corresponds to the above figure is the unique one up to the actions. Now let $T$ be the set of vectors with the properties. Changing signs of vectors if necessary, we may assume that all the $x$ components are non-negative, without loss of any generality. This corresponds to choose the left most square as the initial square. Now the multiset $X$ of $x$-components forms a partition of a positive number no largen than $6$. If the sum of $X$ is less than $4$, then $\frac{32}{4} =8$ indicates that there is at least one column where $8$ or more squares are marked which is impossible. Hence the sum of $X$ is either $5$ or $6$. If it were $5$, the number of $0$ in $X$ is less than $3$ since $2^3 = 8$. If the number of $0$ were $2$, the only possibilities are $X=\{3,1,1,0,0,\} $ or $X =\{ 2,2,1,0,0 \}$. The former is impossible since $1$ is expressible in $8$ 'different' ways.(Choosing one of two $1$s and some of two $0$s). The later is impossible by the similar reason. If there were no zeros then $X = \{1,1,1,1,1 \}$. But then $2$ is expressible in $10$ different ways. If there were exactly one zero, then $X = \{2,1,1,1,0\}$ and $2$ is expressible in $8$ different ways. Therefore the sum of $X$ is $6$.

Similar argument tells us that the only posibility is $X = \{ 3,1,1,1,0 \}$. Now we have $T = \{ (0,a),(1,b), (1,c), (1,d), (3,e) \}$. Moreover, among $a,b,c,d,e$, there are one zero, one $\pm 3$ and three $\pm 1$s. Since they are all different, we may assume that $b<c<d$. Note that $a \neq 0$. By changing signs of $y$ component if necessary, we may assume that $a>0$.

Suppose $a=1$. Noting that $1=1+0$, $b,c,d,b+a, c+a,d+d$ are all different. If there were zero among $b$, $c$, $d$, then there should not be $1$ among them. But then there should be $-1$ and the other one is $\pm 3$. But then one of $b+a$, $c+a$, $d+a$ is zero which is an absurdity. Hence $e=0$. Now we have $(b,c,d) = (-3,-1,1)$ or $(-1,1,3)$. The later results the above figure. The former result on the figure below. Ofcourse, we may argue by means of actions on vectors, but figures are more handy.

Now suppose $a=3$. Necessarily, we have $b=-1$, $c=0$, $d=1$ and $e= \pm 1$. These two are possible and result on the following figures. This completes the existence and uniqueness proof.