Rosenfeld's $7 \times 7$ square puzzle
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.
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.
- Each of the $32$ linear combinations of $T$ with $0, 1$ coefficients are mutually distinct.
- 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.
