A $ 4\times 4$ table is divided into $ 16$ white unit square cells. Two cells are called neighbors if they share a common side. A move consists in choosing a cell and the colors of neighbors from white to black or from black to white. After exactly $ n$ moves all the $ 16$ cells were black. Find all possible values of $ n$.
Problem
Source: JBMO 2008 Problem 4
Tags: linear algebra, matrix, vector, combinatorics proposed, combinatorics
jgnr
26.06.2008 06:47
By considering parity, $ n$ must be even. If $ a$ is a possible value of $ n$, then $ a+2$ is also a possible value of $ n$, because we can choose the same square for the $ a+1$-th and the $ a+2$-th move. If $ a$ is the least possible value of $ n$, then the answer is $ a,a+2,a+4,\ldots$. Now, we have to find the least possible value of $ n$. I have yet to find this least value. It is quite hard for me. By the way, I played this kind of game in my computer, and I finished it after about 80 moves.
kevinatcausa
27.06.2008 01:25
There's a (tedious if written out) solution to this problem that goes as follows: We can view this problem as a matrix equation $ Ax=b$ over the field of two elements, where $ A$ is the $ 16 \times 16$ incidence matrix representing which buttons effect which lights, and $ b$ is the vector where every entry is 1. Gaussian elimination reveals that $ A$ has rank 12, and we can explicitly write down all 16 solutions over $ F_2$. A button sequence works iff it corresponds to one of these 16 modulo 2. The answer is therefore the collection of all numbers of the form $ m+2n$, where $ m$ is the number of nonzero entries in one of our 16 finite field solutions, and $ n$ is any nonnegative integer. The actual computation of the 16 solutions in question I leave to the bored reader.
Eternica
28.06.2008 22:55
Hmn. I just used very simple casework. All deduction really. If anyone interested:
Label each square $ a_{ij}$, where $ i$ denotes the $ i$th row and $ j$ denotes the $ j$th column. We can merely consider only the squares where $ i + j$ is even because each distinct move can only change the colors of either even squares or odd squares. The case where $ i + j$ is odd is identical.
Without loss of generality, let each distinct move occur at most once (two of the same move = identity). Consider the top left square. It has two adjacent squares. We must pick exactly one of these squares in order to successfully change its color. Without loss of generality, pick $ a_{12}$ as a move. $ a_{21}$ cannot be a move.
Now consider $ a_{22}$. We have two cases:
Case 1: One adjacent square is chosen.
We already have that $ a_{12}$ changes the color of $ a_{22}$. Thus $ a_{23}$ and $ a_{32}$ cannot be chosen as moves. Consider $ a_{13}$. As its color is already black, we cannot choose $ a_{14}$. Consider $ a_{24}$. By similar reasoning, $ a_{34}$ must be chosen as a move. Consider $ a_{31}$. $ a_{41}$ must be a move. $ a_{43}$ cannot be a move. We have $ 3$ moves total in this case. (I attached a picture for those who do not want to draw it out)
Case 2: Three adjacent squares are chosen.
Tedious, but rather short. It comes out to be $ 5$ moves.
We see that both of these cases, we have an odd number of moves. Because we must perform the set of moves again on the odd parity squares, we see $ n$ cannot be odd. The smallest amount of even moves possible is $ 3 + 3 = 6$. Thus $ n$ could be any even number greater than or equal to $ 6$.
Attachments:
kevinatcausa
29.06.2008 04:11
The question as posted is rather unclear...I had been assuming that the selected square also changes color.
jgnr
29.06.2008 04:42
kevinatcausa wrote: The question as posted is rather unclear...I had been assuming that the selected square also changes color. I think your assumption is correct.
Eternica
29.06.2008 04:58
Quote: A move consists in choosing a cell and [changing] the colors of neighbors from white to black or from black to white. The sentence seems to be logically missing that verb, which means that the selected square does not change color. Can the poster clarify?
dule_00
29.06.2008 10:08
It changes selected square and neighbors squares also.
Ahiles
29.06.2008 16:15
Yes.. Sorry for my missed word. "A move" consists in choosing a cell and changing the colors of this cell and its neighbors from white to black or from black to white."
Ahiles
30.06.2008 01:57
By a move we can cover the table with 3,4 or 5 cells. Let us prove that we need at least 4 moves.
Suppose contrary... Then we can max cover $ 3\cdot 5 = 15$ cells. But we need to cover 16 cells. Contradiction.
Then next step is to prove that we can color the table in 4 moves.
Look at the picture.
Next step to prove that we can color the table in $ 2k$ moves, where $ k \ge 2$.
Color the table in black in 4 steps. Then take any cell and change it color twice. So by 2 moves you obtained again a table colored in black. You can repeat this procedure and obtain a black table in $ 4,4 + 2,4 + 4,...,4 + 2p$ moves
To take the last 5 points you need to prove that you can't obtain the black table in an odd number of moves.
Consider the figure as in the picture
Image not found
And now how you will not do a move you will always cover an odd number of cells from this figure. From this after an odd numbers of moves oyu will color an odd number of cells, but it is even, so you can't.
Consider the 4 cells as in the picture.
Image not found
How you will not do a move you will always cover only one of this cells. So after an odd number of moves you won't color all 4.
highlander
30.06.2008 14:16
i think you missread the problem or i missread the problem:)! The MOVE i think it consist in changing just the neighbours colors! the cell you have chosen is not included! This new Problem is more difficult that this trivial one:)
mszew
30.06.2008 16:56
If you do not change the color of the chosen cell then the minimum is $ 6$ by chosing the select cells: 1001 1001 0000 0110 In order to paint black the corners at least 4 are required from the following eight cells: 0110 1001 1001 0110 and you do not paint all either by picking exactly four from those eight cells or by picking an additional one to those four.
highlander
30.06.2008 17:32
try the last problem with dimension of table 2nx2n:)
Ahiles
30.06.2008 19:17
Quote: The MOVE i think it consist in changing just the neighbours colors! the cell you have chosen is not included! No, the move consists in a color changing of the cell too... I missed this word in the 1 post. So the problem isn't easy at all.
djuro
23.07.2008 00:42
I heard this problem was proposed by Dušan Milijančević from Serbia (took a silver on this year's IMO).
trigg
19.06.2009 10:51
I like this problem but it is very easy and basic
efoski1687
19.06.2009 10:56
I agree you Ufuk! When i in the comptetion i solved this problem in five minutes. I think this is too easy for Junior Balkan. I think this problem should send to "Baby Balkan"
trigg
19.06.2009 10:59
did you solve it in five minutes!!!!! when I saw this problem I solved it in twenty-thirty seconds
pab
15.06.2017 11:08
i don't understand why n must be even, can you explain me ?
MK4J
27.05.2018 11:07
Another solution for eliminating the case $n$ odd: Consider the quadrominos of the following form: |o|x|o| |x|x|x| where I denoted with “x” a square of the quadromino and “o” an other square of the table. We can cover the table with $4$ quadrominos of this type (we can turn them), for example when we put their centers in the $4$ cells we applied the operation for the case $n=4$. Now, suppose that we can cover the table with an odd number of opperations ($n$ odd). Then, we can delete the pairs of opperations which were performed on the same cell. So we obtain $n_0 \leq n$, $n_0$ odd, such that each cell was performed at most one time ($n_0$ being the number of cells on which was performed the operation and in the same time the number of operations performed). It is not hard to see that the order of which operation was performed first does not change the result. But there can’t be an odd number of cells in all the four quadrominos formed, because in that case $n_0$ will be even. So there is a quadromino from that $4$ which has an even number of cells with operation performed. Hence, the cell in the center of that quadromino will have its changed an even number of times. So that cell will be white at the end, contradiction! In conclussion, $n_0$ must be even, so $n$ must be as well.
huashiliao2020
14.04.2023 04:43
Ahiles wrote:
By a move we can cover the table with 3,4 or 5 cells.
Let us prove that we need at least 4 moves.
ProofSuppose contrary... Then we can max cover $ 3\cdot 5 = 15$ cells. But we need to cover 16 cells. Contradiction.
Then next step is to prove that we can color the table in 4 moves.
ProofLook at the picture.
Next step to prove that we can color the table in $ 2k$ moves, where $ k \ge 2$.
ProofColor the table in black in 4 steps. Then take any cell and change it color twice. So by 2 moves you obtained again a table colored in black. You can repeat this procedure and obtain a black table in $ 4,4 + 2,4 + 4,...,4 + 2p$ moves
To take the last 5 points you need to prove that you can't obtain the black table in an odd number of moves.
Officiall solutionConsider the figure as in the picture
And now how you will not do a move you will always cover an odd number of cells from this figure. From this after an odd numbers of moves oyu will color an odd number of cells, but it is even, so you can't.
Solution of an turkish studentConsider the 4 cells as in the picture.
How you will not do a move you will always cover only one of this cells. So after an odd number of moves you won't color all 4.
MK4J wrote:
Another solution for eliminating the case $n$ odd:
Consider the quadrominos of the following form:
|o|x|o|
|x|x|x| where I denoted with “x” a square of the quadromino and “o” an other square of the table.
We can cover the table with $4$ quadrominos of this type (we can turn them), for example when we put their centers in the $4$ cells we applied the operation for the case $n=4$.
Now, suppose that we can cover the table with an odd number of opperations ($n$ odd). Then, we can delete the pairs of opperations which were performed on the same cell. So we obtain $n_0 \leq n$, $n_0$ odd, such that each cell was performed at most one time ($n_0$ being the number of cells on which was performed the operation and in the same time the number of operations performed).
It is not hard to see that the order of which operation was performed first does not change the result.
But there can’t be an odd number of cells in all the four quadrominos formed, because in that case $n_0$ will be even.
So there is a quadromino from that $4$ which has an even number of cells with operation performed.
Hence, the cell in the center of that quadromino will have its changed an even number of times.
So that cell will be white at the end, contradiction!
In conclussion, $n_0$ must be even, so $n$ must be as well.
Hmm, I didn’t quite understand the last parts. I got that you can color the table in 2k moves, k$\geq$2, but nothing else about not being able to obtain the black table in an odd number of moves. I tried parity and didn’t get much. Any alternate/more clarifying solutions would be helpful, although I really want to make more progress on this myself, so maybe like 2-3 progressive hints in succession would be really preferred.