Rosenfeld's $7 times 7$ square puzzle
up vote
7
down vote
favorite
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 $7times 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.
combinatorics discrete-mathematics puzzle discrete-geometry tiling
|
show 9 more comments
up vote
7
down vote
favorite
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 $7times 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.
combinatorics discrete-mathematics puzzle discrete-geometry tiling
Do you at least know how to reach $32$? At least you can confirm that $32$ is doable, right?
– Zvi
Nov 23 at 15:25
@Zvi Yes I know as you can infer from my post.
– seoneo
Nov 23 at 15:28
2
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.
– Matthias Klupsch
Nov 23 at 15:40
1
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).
– hardmath
Nov 23 at 15:55
1
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 $7times 7$ case (among others).
– hardmath
Nov 23 at 16:05
|
show 9 more comments
up vote
7
down vote
favorite
up vote
7
down vote
favorite
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 $7times 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.
combinatorics discrete-mathematics puzzle discrete-geometry tiling
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 $7times 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.
combinatorics discrete-mathematics puzzle discrete-geometry tiling
combinatorics discrete-mathematics puzzle discrete-geometry tiling
edited Nov 24 at 16:59
asked Nov 23 at 14:46
seoneo
482213
482213
Do you at least know how to reach $32$? At least you can confirm that $32$ is doable, right?
– Zvi
Nov 23 at 15:25
@Zvi Yes I know as you can infer from my post.
– seoneo
Nov 23 at 15:28
2
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.
– Matthias Klupsch
Nov 23 at 15:40
1
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).
– hardmath
Nov 23 at 15:55
1
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 $7times 7$ case (among others).
– hardmath
Nov 23 at 16:05
|
show 9 more comments
Do you at least know how to reach $32$? At least you can confirm that $32$ is doable, right?
– Zvi
Nov 23 at 15:25
@Zvi Yes I know as you can infer from my post.
– seoneo
Nov 23 at 15:28
2
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.
– Matthias Klupsch
Nov 23 at 15:40
1
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).
– hardmath
Nov 23 at 15:55
1
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 $7times 7$ case (among others).
– hardmath
Nov 23 at 16:05
Do you at least know how to reach $32$? At least you can confirm that $32$ is doable, right?
– Zvi
Nov 23 at 15:25
Do you at least know how to reach $32$? At least you can confirm that $32$ is doable, right?
– Zvi
Nov 23 at 15:25
@Zvi Yes I know as you can infer from my post.
– seoneo
Nov 23 at 15:28
@Zvi Yes I know as you can infer from my post.
– seoneo
Nov 23 at 15:28
2
2
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.
– Matthias Klupsch
Nov 23 at 15:40
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.
– Matthias Klupsch
Nov 23 at 15:40
1
1
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).
– hardmath
Nov 23 at 15:55
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).
– hardmath
Nov 23 at 15:55
1
1
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 $7times 7$ case (among others).
– hardmath
Nov 23 at 16:05
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 $7times 7$ case (among others).
– hardmath
Nov 23 at 16:05
|
show 9 more comments
2 Answers
2
active
oldest
votes
up vote
5
down vote
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 $kin{0,1,2,3,4,5}$ represent the cells in the $7times 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}}\hlinebf 2 & bf 3& bf 1&bf 3 &bf bf 4 & bf 4& color{gray}{*}\hlinecolor{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}}\ hlinebf 5&bf 5&bf 5 &bf 5 &bf 5 &bf 5 & color{gray}{*}\hlinecolor{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}}\hlineend{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.
1
Good job. Yours coincides with mine. @Zvi
– seoneo
Nov 23 at 15:51
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).
– Misha Lavrov
Nov 23 at 16:00
@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.
– hardmath
Nov 23 at 17:16
add a comment |
up vote
3
down vote
accepted
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.
While I also discovered the commutativity of duplication-and-translation moves, I couldn't find a way to use this result easily. Congrats!
– Zvi
Nov 27 at 13:21
@Zvi The comment in your solution helped me to figure out what's important. Thanks.
– seoneo
21 hours ago
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
5
down vote
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 $kin{0,1,2,3,4,5}$ represent the cells in the $7times 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}}\hlinebf 2 & bf 3& bf 1&bf 3 &bf bf 4 & bf 4& color{gray}{*}\hlinecolor{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}}\ hlinebf 5&bf 5&bf 5 &bf 5 &bf 5 &bf 5 & color{gray}{*}\hlinecolor{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}}\hlineend{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.
1
Good job. Yours coincides with mine. @Zvi
– seoneo
Nov 23 at 15:51
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).
– Misha Lavrov
Nov 23 at 16:00
@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.
– hardmath
Nov 23 at 17:16
add a comment |
up vote
5
down vote
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 $kin{0,1,2,3,4,5}$ represent the cells in the $7times 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}}\hlinebf 2 & bf 3& bf 1&bf 3 &bf bf 4 & bf 4& color{gray}{*}\hlinecolor{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}}\ hlinebf 5&bf 5&bf 5 &bf 5 &bf 5 &bf 5 & color{gray}{*}\hlinecolor{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}}\hlineend{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.
1
Good job. Yours coincides with mine. @Zvi
– seoneo
Nov 23 at 15:51
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).
– Misha Lavrov
Nov 23 at 16:00
@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.
– hardmath
Nov 23 at 17:16
add a comment |
up vote
5
down vote
up vote
5
down vote
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 $kin{0,1,2,3,4,5}$ represent the cells in the $7times 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}}\hlinebf 2 & bf 3& bf 1&bf 3 &bf bf 4 & bf 4& color{gray}{*}\hlinecolor{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}}\ hlinebf 5&bf 5&bf 5 &bf 5 &bf 5 &bf 5 & color{gray}{*}\hlinecolor{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}}\hlineend{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.
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 $kin{0,1,2,3,4,5}$ represent the cells in the $7times 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}}\hlinebf 2 & bf 3& bf 1&bf 3 &bf bf 4 & bf 4& color{gray}{*}\hlinecolor{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}}\ hlinebf 5&bf 5&bf 5 &bf 5 &bf 5 &bf 5 & color{gray}{*}\hlinecolor{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}}\hlineend{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.
edited Nov 23 at 17:36
answered Nov 23 at 15:37
Zvi
3,825328
3,825328
1
Good job. Yours coincides with mine. @Zvi
– seoneo
Nov 23 at 15:51
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).
– Misha Lavrov
Nov 23 at 16:00
@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.
– hardmath
Nov 23 at 17:16
add a comment |
1
Good job. Yours coincides with mine. @Zvi
– seoneo
Nov 23 at 15:51
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).
– Misha Lavrov
Nov 23 at 16:00
@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.
– hardmath
Nov 23 at 17:16
1
1
Good job. Yours coincides with mine. @Zvi
– seoneo
Nov 23 at 15:51
Good job. Yours coincides with mine. @Zvi
– seoneo
Nov 23 at 15:51
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).
– Misha Lavrov
Nov 23 at 16:00
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).
– Misha Lavrov
Nov 23 at 16:00
@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.
– hardmath
Nov 23 at 17:16
@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.
– hardmath
Nov 23 at 17:16
add a comment |
up vote
3
down vote
accepted
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.
While I also discovered the commutativity of duplication-and-translation moves, I couldn't find a way to use this result easily. Congrats!
– Zvi
Nov 27 at 13:21
@Zvi The comment in your solution helped me to figure out what's important. Thanks.
– seoneo
21 hours ago
add a comment |
up vote
3
down vote
accepted
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.
While I also discovered the commutativity of duplication-and-translation moves, I couldn't find a way to use this result easily. Congrats!
– Zvi
Nov 27 at 13:21
@Zvi The comment in your solution helped me to figure out what's important. Thanks.
– seoneo
21 hours ago
add a comment |
up vote
3
down vote
accepted
up vote
3
down vote
accepted
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.
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.
edited Nov 24 at 17:06
answered Nov 24 at 15:05
seoneo
482213
482213
While I also discovered the commutativity of duplication-and-translation moves, I couldn't find a way to use this result easily. Congrats!
– Zvi
Nov 27 at 13:21
@Zvi The comment in your solution helped me to figure out what's important. Thanks.
– seoneo
21 hours ago
add a comment |
While I also discovered the commutativity of duplication-and-translation moves, I couldn't find a way to use this result easily. Congrats!
– Zvi
Nov 27 at 13:21
@Zvi The comment in your solution helped me to figure out what's important. Thanks.
– seoneo
21 hours ago
While I also discovered the commutativity of duplication-and-translation moves, I couldn't find a way to use this result easily. Congrats!
– Zvi
Nov 27 at 13:21
While I also discovered the commutativity of duplication-and-translation moves, I couldn't find a way to use this result easily. Congrats!
– Zvi
Nov 27 at 13:21
@Zvi The comment in your solution helped me to figure out what's important. Thanks.
– seoneo
21 hours ago
@Zvi The comment in your solution helped me to figure out what's important. Thanks.
– seoneo
21 hours ago
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3010441%2frosenfelds-7-times-7-square-puzzle%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Do you at least know how to reach $32$? At least you can confirm that $32$ is doable, right?
– Zvi
Nov 23 at 15:25
@Zvi Yes I know as you can infer from my post.
– seoneo
Nov 23 at 15:28
2
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.
– Matthias Klupsch
Nov 23 at 15:40
1
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).
– hardmath
Nov 23 at 15:55
1
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 $7times 7$ case (among others).
– hardmath
Nov 23 at 16:05