Pretty Cells
My e-friend and coauthor, Konstantin Knop, designed the following problem for the 2011 All-Russia Olympiad:
Some cells of a 100 by 100 board have one chip placed on them. We call a cell pretty if it has an even number of neighboring cells with chips. Neighbors are the cells that share a side. Is it possible for exactly one cell to be pretty?
The problem is not easy. Only one person at the Olympiad received full credit for it.
Share:
Harry H:
Correct me if I’m wrong but this setup produces exactly one “Pretty” cell.
Place two chips in the column or row separated by one cell. The cell between them is “Pretty” but no others are. Unless a cell is “Pretty” if none of it’s neighbours contain chips?
5 August 2011, 10:41 amTanya Khovanova:
Harry,
Zero is an even number.
5 August 2011, 10:58 amChris Chang:
My guess is that the answer is no.
I would attempt the following proof strategy:
Color the cells of the board alternately white and black, like a chessboard. Let a capital letter denote a chip configuration on (WLOG) just the white cells, and f(A) denote the binary (where 0 = pretty cell, 1 = not pretty) prettiness matrix on the black cells induced by chip configuration A. Note that f(A XOR B)=f(A) XOR f(B).
Assume, toward a contradiction, that there is a chip configuration with exactly one pretty cell. From this full board configuration, we can extract two halves Y and Z where f(Y) has no pretty black cells and f(Z) has exactly one. It follows that the matrix f(Y XOR Z) has only a single 1.
Now, we note that there are 2^5000 distinct half-board chip configurations, and 2^5000 possible half-board prettiness matrices. By inspection, f is not one-to-one: putting a chip on every cell on a main diagonal yields the same prettiness matrix as having no chips at all. Thus, there must exist prettiness matrices that cannot be produced by any chip configuration.
So, if one could construct a half-board chip configuration for every cell where the prettiness matrix has a 1 at that cell and 0s everywhere else, we have the desired contradiction. Don’t have the time to try to flesh out this construction for now, but I’ll probably come back to this later.
6 August 2011, 3:50 amSiddhant:
Well here is some small progress. Suppose that such a configuration exists, then the pretty cell cannot be on the diagonal. This is true for all squares of the form 2n*2n. Proof is quite straigth forward. Just look at the entries in the superdiagonal and subdiagonal and it follows.
6 September 2011, 1:07 pmAriana Poulin:
I really liked your blog article.Much thanks again. Will read on…
22 April 2012, 7:55 amVincent:
Dear Tanya,
I have very fond memories of this puzzle. It was posted at the due date of the birth of our son (I’m not sure this is the correct English expression) but as with many first children, well before the actual birthdate. Between school holiday (I worked as a teacher back then) and no one calling us in fear of interupting labor we spent some days in a somewhat surreal emptiness that I partially filled with thinking about this puzzle. It has been said that the best way to solve a problem is think hard about it, then totally forget it and the solution will pop into your head. Well, in this case it was exactly like that. Sitting in the hospital room watching my wife and newborn son sleep after an intensive 24 hours with no room for math whatsoever something suddenly clicked and I understood the solution to this problem. I will post it here in case I forget it someday (also after two years it can hardly be considered a spoiler) and I hope you will post an equally interesting puzzle soon as our second child is due in a couple of weeks.
Thanks for all the great puzzles so far,
Vincent
Solution:
We call a set of cells H ‘happy’ if every cell on the board neighbors an even number of cells from H. The rationale behind this name is that when you are happy everyone looks pretty, some people might argue that ‘drunk’ would be a better name. (It is understood that by ‘you’ I mean here the set of cells with chips on them although in the sequel the question whether the set of chips is beautiful or not will play no role)
Pick a happy set H. Denote the set of cells with chips by C. We count the number n of boarders between a cell in C and cell in H in two ways. First, by looking at every chip and counting the number of cells from H it sees we conclude that n is even (by the happiness of H). Next by looking at every cell of H and counting the number of chips it sees, we conclude that the parity of n equals the parity of the number of non-pretty cells in H, which, by the previous counting method must be even. We infer that the parity of the number of pretty cells in H is then equal to the parity of the total number of cells in H.
In the scenario where there is exactly one pretty cell x, we conclude that x is contained in EVERY happy set with an odd number of cells and in NONE of the happy sets with an even number of cells.
The first remark implies that for odd values of 100 a solution can only exist with x at the very center of the board (as both the diagonal and the anti-diagonal are happy) and indeed it is not hard to construct such a solution. However we are interested in the case of even values of 100 and in this case no solution exists. We show this by showing that every cell on the board is contained in a happy set of even size and applying the second of our two observations. (I don’t think a proof by means of the first observations i.e. by exhibiting two disjoint happy sets with an odd number of elements is possible in this case but I’m not sure)
Construction of the happy set containing an arbitrary cell y:
24 June 2013, 2:33 pmTake the diagonal through y parallel to the main diagonal. Say it has length m. Translate this diagonal parallel to the anti-diagonal (so both north-east and south-west) but while keeping its length. If you can’t shift any further without having two of the m cells falling of the board you stop. You end up with a m-by-(101-m) rectangle consisting entirely of black or entirely of white cells (in the usual coloring). This set is happy and since its number of cells is m(100 + 1 – m) for some number m it is always even for every even value of 100.