1. Joined
    25 Aug '06
    Moves
    0
    28 Jan '08 13:01
    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".
  2. Standard memberTheMaster37
    Kupikupopo!
    Out of my mind
    Joined
    25 Oct '02
    Moves
    20443
    28 Jan '08 13:14
    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 ...[text shortened]... X" in them.

    PROVE:
    it is not possible that all n^2 little squares will get an "X".
    Well, for n = 3 it's easy;

    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
  3. Joined
    02 Mar '06
    Moves
    17881
    28 Jan '08 23:151 edit
    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.

    PROVE:
    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.
  4. Joined
    25 Aug '06
    Moves
    0
    29 Jan '08 11:52
    Originally posted by Aetherael
    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.
    This is not a proof... And there are many ways to fill the square with n X's without filling a diagonal. For example:
  5. Joined
    05 Jun '07
    Moves
    906
    30 Jan '08 05:121 edit
    Never mind, I think Aetheral got the right solution.
  6. Joined
    12 Sep '07
    Moves
    2668
    04 Mar '08 17:10
    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)
  7. Joined
    23 Oct '07
    Moves
    2831
    05 Mar '08 04:03
    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 ...[text shortened]... X" in them.

    PROVE:
    it is not possible that all n^2 little squares will get an "X".
    since you draw only one X there won't any squares that have 2 x around them!!!!
    NICE
    ๐Ÿ˜€
  8. Joined
    31 May '07
    Moves
    696
    05 Mar '08 18:42
    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.
  9. Joined
    25 Aug '06
    Moves
    0
    05 Mar '08 22:46
    Originally posted by Dejection
    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)
    Yes, this is a correct proof๐Ÿ™‚
Back to Top

Cookies help us deliver our Services. By using our Services or clicking I agree, you agree to our use of cookies. Learn More.I Agree