7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Do you at least know how to reach $32$? At least you can confirm that $32$ is doable, right? $\endgroup$ – user593746 Nov 23 '18 at 15:25
  • $\begingroup$ @Zvi Yes I know as you can infer from my post. $\endgroup$ – seoneo Nov 23 '18 at 15:28
  • 2
    $\begingroup$ I just tried to do it myself and by looking at my solution it seems that you have also to account not only for rotation but for mirror symmetries as well. $\endgroup$ – Matthias Klupsch Nov 23 '18 at 15:40
  • 1
    $\begingroup$ The March 2007 paper by Moshe Rosenfeld quoted from is behind a paywall (Electronic Notes in Discrete Mathematics, vol. 28, pp. 409-415), but it references an earlier note by the same author, A Dynamic Puzzle (Am. Math. Monthly, vol. 98, 1991). $\endgroup$ – hardmath Nov 23 '18 at 15:55
  • 1
    $\begingroup$ While the 2007 paper goes into the toroidal setting, the earlier note (in the Monthly's Unsolved Problems section) does concern the problem on a rectangular grid and specifically mentions the $7\times 7$ case (among others). $\endgroup$ – hardmath Nov 23 '18 at 16:05
5
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Good job. Yours coincides with mine. @Zvi $\endgroup$ – seoneo Nov 23 '18 at 15:51
  • $\begingroup$ I wonder if the set of translations used is also unique up to symmetry (and up to reversing any subset of the translations, which corresponds to choosing a different starting point among the marked cells). $\endgroup$ – Misha Lavrov Nov 23 '18 at 16:00
  • $\begingroup$ @MishaLavrov: The sequence of translations provides some additional symmetries that would have to be discounted. For example, two "mirrored" translations might be done leading to identical marked squares, after which the two sequences could continue in the same translations. $\endgroup$ – hardmath Nov 23 '18 at 17:16
2
$\begingroup$

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$.

Figure 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.

Figure 2

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.

enter image description here

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ While I also discovered the commutativity of duplication-and-translation moves, I couldn't find a way to use this result easily. Congrats! $\endgroup$ – user593746 Nov 27 '18 at 13:21
  • $\begingroup$ @Zvi The comment in your solution helped me to figure out what's important. Thanks. $\endgroup$ – seoneo Nov 30 '18 at 5:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.