| Marcos |
You've have an n×n board with 1's in each cell. You make one of them into a -1. You're only allowed to change the signs of a whole k×k subboard (1 £ n). Your aim is to have 1's in every cell. My question is, what is the number of initial configurations (i.e. in how many cells can the -1 go) so that you can get a solution. I'm going to call this number b(n). We have b(2)=b(3)=0 It's also not very difficult to show that b(5)=1 (where the -1 goes in the central cell: this cell works for all odd n) This of course automatically implies b(7) ³ 5 but I'm not sure of its exact value. Does anybody have any ideas? Marcos |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Michael
McLoughlin |
I don't quite understand the question. What do you mean when you say "You're only allowed to change the signs of a whole k x k subboard"? |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Kerwin
Hui |
Here are my thoughts so far: The 5 by 5 case shows the central 3 by 3 in the 7 by 7 are doable (find a 5 by 5 square which contains it in the middle). Also, we have the following `device':
Turning all 3 by 3 gives
Now turn the three 2 by 2's that doesn't contain the top left corner, we get
So we can move any -1 down the a diagonal to get 2 -1's. We can also iterate this process again, which gives us: if we have a 4 by 4 square with a -1 at a corner, we can move this -1 to the opposite corner. So we can do the 37 squares marked by an 'X'
(and this implies all 8 by 8 and above are doable). I have no idea how to tackle the remaining 12 squares at this moment. Kerwin |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Kerwin
Hui |
We also have the device:
changing the two left hand side 2 by 2 and then the 3 by 3 gives
So the remaining 12 are also doable. Kerwin |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| George
Barwood |
Answer in white: B(n) = (n-4)^2 ( n > = 5 ) Since B(5) = 1, we can manipulate any square than is not in the 2-cell wide border. For any cell in the border there is an adjacent square that is always flipped at the same time. Therefore we can never find a solution for a border cell. |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| George
Barwood |
Oops, ignore the above post, obviously my statement doesn't hold for corners! |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Kerwin
Hui |
Just have a little more play with my devices - can show that b(6)=36. (Try it! It is not too difficult.) Kerwin |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Marcos |
That's great Kerwin! Thanks! So we have, b(2)=b(3)=b(4)=0 b(5)=1 b(n)=n2 for n > 5? I'm having a bit of trouble showing b(6)=36 although that's probably because I haven't really tried doing it properly. Marcos |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Kerwin
Hui |
Oops, that is not true... beta(6)=20, not 36. There are 16 impossible position
(any nontrivial subboard contains an even number of those). The other 20 are possible (the only slightly nontrivial ones are those in the middle of the edge). Kerwin |