Originally posted by David113
We have a square divided into n^2 small identical squares.
1: Draw an "X" in n-1 of the little squares.
2: If there is an empty little square which has at least 2 neighbors with an "X" in them, you may draw an "X" in this square. Two little squares are neighbors if they have a common edge.
3: Return to step 2, until there are no more empty little s X" in them.
it is not possible that all n^2 little squares will get an "X".
this may not be perfectly formal, but it gets at the crux of the problem:
the optimal strategy, given the method of construction, for getting the most X's is to create a diagonal of X's whose corners touch. For example, given a 3x3 section of any given square, if you were to place an X in each box along the diagonal, then the two squares above the diagonal and the two below the diagonal would get an X from the adjacency rule... and then using the rule again the last two squares would get X's as well. So filling in the diagonal of a square inherently fills in the entirety of the square.
But given only n-1 X's to place within an n by n square, you couldn't fill in the whole diagonal. the best you could do is a diagonal of length n-1 (omitting one of the corners of the original square), and you end up with X's in all (n-1)^2 squares, with one row and one column of the original
square empty. i.e. 2n-1 of the squares will not have an X in them.
If given only one more initial X placement, however, one could fill in the whole square.