Marcos

Posted on Friday, 11 June, 2004 - 07:20 am:

You've have an

n \times 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 \times k

subboard (

1 \leq 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 $β (n)$ .

We have $β (2) = β (3) = 0$

It's also not very difficult to show that $β (5) = 1$ (where the -1 goes in the central cell: this cell works for all odd $n$ )

This of course automatically implies $β (7) \geq 5$ but I'm not sure of its exact value.

Does anybody have any ideas?

Marcos

Michael McLoughlin

Posted on Friday, 11 June, 2004 - 07:44 am:

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

Posted on Friday, 11 June, 2004 - 08:54 am:

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'


X	X		X		X	X
X	X	X		X	X	X
	X	X	X	X	X
X		X	X	X		X
	X	X	X	X	X
X	X	X		X	X	X
X	X		X		X	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

Posted on Friday, 11 June, 2004 - 09:01 am:

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

Posted on Friday, 11 June, 2004 - 09:12 am:

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

Posted on Friday, 11 June, 2004 - 09:17 am:

Oops, ignore the above post, obviously my statement doesn't hold for corners!

Kerwin Hui

Posted on Friday, 11 June, 2004 - 09:44 am:

Just have a little more play with my devices - can show that

β (6) = 36

. (Try it! It is not too difficult.)

Kerwin

Marcos

Posted on Friday, 11 June, 2004 - 01:52 pm:

That's great Kerwin! Thanks!

So we have,

$β (2) = β (3) = β (4) = 0$

$β (5) = 1$

$β (n) = n^{2}$ for $n > 5$ ?

I'm having a bit of trouble showing $β (6) = 36$ although that's probably because I haven't really tried doing it properly.

Marcos

Kerwin Hui

Posted on Friday, 11 June, 2004 - 08:37 pm:

Oops, that is not true... beta(6)=20, not 36. There are 16 impossible position


	X			X
X		X	X		X
	X			X
	X			X
X		X	X		X
	X			X

(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