JP Ikäheimonen:
8 by 8: six blocks:
OOOOOOOO
OOOOOOOO
OOXOOXOO
OOOXOOOO
OOOOXOOO
OOXOOXOO
OOOOOOOO
OOOOOOOO
9 by 9: nine blocks:
OOOOOOOOO
OOOOOOOOO
OOXXOOXOO
OOOOOOXOO
OOOOXOOOO
OOXOOOOOO
OOXOOXXOO
OOOOOOOOO
OOOOOOOOO
10 by 10: twelve blocks:
OOOOOOOOOO
OOOOOXOOOO
OOXOOOOXOO
OOOOOOXOOO
OOOOOXOOXO
OXOOXOOOOO
OOOXOOOOOO
OOXOOOOXOO
OOOOXOOOOO
OOOOOOOOOO
11 by 11: thirteen blocks:
OOOOOOOOOOO
OOOOOXOOOOO
OOXOOOOOXOO
OOOOOOXOOOO
OOOXOOOOOOO
OXOOOXOOOXO
OOOOOOOXOOO
OOOOXOOOOOO
OOXOOOOOXOO
OOOOOXOOOOO
OOOOOOOOOOO
Scott Purdy
My conjecture
says that any mxn grid will require at least floor(m/3) * floor(n/3).
While
we're at it, though, I don't think it's a conjecture, I believe I can
prove it.
Beginning in one corner, section 3x3 sub-grids until no more can
be drawn. Discard the remainder (hence 11x11 is treated the same
as
9x9). Consider the central square of each of these grids.
Either it is
obstructed or the QORS can stop there. If the QORS can stop there,
one of the 8 adjacent squares is obstructed. Therefore, one of
the squares
in each 3x3 square (either the central square or one of those surrounding
it)
is obstructed. This is not to suggest that this many are sufficient,
only
necessary.
David Speyer
I can (and will below) show that the answer is between (1/7)*n^2+O(n)
and
(1/9)*n^2+O(n). Moreover, the method used to obtain the 1/7 bound lends
it
self to improvement by computer searching, although I have reason to
believe that some fairly high cases will have to be reached to improve
on
these numbers. Do you know of any improvements on these results?
OK, the 1/9 bound is easy: every square must border an obstacle. For
the
1/7 bound, suppose we have a square grid, kXk with o obstacles, which
solves the Wrap Around Queens with Roller Skates problem (a wrap around
queen with roller skates wraps around in stead of stopping when she
hits a
wall.) Suppose this grid has the additional property that the plane
is
tesselated with it, it is possible to move from any square in one grid
to
the corresponding square in any of the other grids that borders it
(trial
and error indicates that the first implies the second, but I don't
know
why.) Then o*n^2/k^2+O(n) can be achieved by tesselating this grid
over
and over. (If you like, I'll fill in details, but I think this should
be
intuitive.)
Anyways, I believe this grid, 7X7 with seven obstacles, has the required
properties:
XOOOOOO
OOXOOOO
OOOOXOO
OOOOOOX
OXOOOOO
OOOXOOO
OOOOOXO.
I'd be curious to know if you can extend these ideas, or whether you
know
the correct asymptopics.