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 squares which have at least 2 neighbors with an "X" in them.
PROVE:
it is not possible that all n^2 little squares will get an "X".
Originally posted by David113Well, for n = 3 it's easy;
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 ...[text shortened]... X" in them.
PROVE:
it is not possible that all n^2 little squares will get an "X".
you are allowed to place two X's. Next step you can put at most 1 X in the grid. Next step, no more X's.
This proves that is doesn't work for all n.
For the general proof i'm thinking along the lines of the following, the break indicates where I'm not certain of the validity anymore:
First step n-1 X's
Next step at most n-2 X's
-----
Next step at most n-3 X's
Next step st most n-4 X's
and so on.
In total at most n-1 + n-2 + n-3 + .... + 3 + 2 + 1 < (n-1)(n-1) < n^2
Originally posted by David113this may not be perfectly formal, but it gets at the crux of the problem:
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.
PROVE:
it is not possible that all n^2 little squares will get an "X".
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.
Originally posted by AetheraelThis is not a proof... And there are many ways to fill the square with n X's without filling a diagonal. For example:
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 diag ...[text shortened]...
If given only one more initial X placement, however, one could fill in the whole square.
Here is a more rigorous proof of the result.
Observe the total perimeter of the little squares that have X's. By looking at each case, we can see that after each step the perimeter is non-ascending. The maximum perimeter to begin with is 4(n-1), and the perimeter needed to cover the whole square is 4n. As 4(n-1)
Originally posted by David113since you draw only one X there won't any squares that have 2 x around them!!!!
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 ...[text shortened]... X" in them.
PROVE:
it is not possible that all n^2 little squares will get an "X".
NICE
😀
Consider a 2 by 2 square. This cannot be completely filled as only one square will be coloured in at the start. Now, ignore the 2 by 2 square, but add another 5 squares to make it 3 by 3. You would be allowed one more x, which can completely fill in the 5 new squares, but only supposing that the initial 2 by 2 square is completed. As the square is made bigger still to allow one more x, the additional squares can all be coloured, but only if the square already in place has been completely coloured, and as this isn't true for the initial 2 by 2 square, it can never be true.
Originally posted by DejectionYes, this is a correct proof🙂
Here is a more rigorous proof of the result.
Observe the total perimeter of the little squares that have X's. By looking at each case, we can see that after each step the perimeter is non-ascending. The maximum perimeter to begin with is 4(n-1), and the perimeter needed to cover the whole square is 4n. As 4(n-1)