A particular restaurant is known for being a place spies like to hang out when discussing covert ops and contracts. The tables in this restaurant are set up by a grid, 7 by 7.

The spies, being secretive, pick the table furthest away from everyone else, and won't sit down next to an occupied table (not counting diagonally) for fear of being oveheard.

Naturally this presents a problem for the owner, as most of the seats where the first person sits, he won't be able to fit half or more in.

What seats should the owner mandate the first spy to sit?

If the owner's business grows and he uses a larger square grid, what sizes will be impossible for him to fit half or more?

For other grids, where should the first person sit to maximize the grid?

Clearly for any size grid the owner needs the tables to be used in a checkerboard pattern.  For an odd grid size they specifically need to take up the 4 corners.

For an even grid (except 2x2) it is not possible to keep at least 3 corners from being filled.  So this can never work.

For 3x3 and 5x5 grids, putting the first spy dead center will fill the grid nicely.

7x7 is not so nice and I'm not completely sure how to determine how far apart two tables are or how the seating spy chooses.  (I'm guessing pythagorean distance but what about ties?)  Ptting the first spy dead center wont work anyway because after the next four pick the corners, spy 6 will choose the middle of a side which breaks the checkerboard pattern.  (All NxN boards of the form N=4n-1 will have this problem except 3x3).

Call the opposite corners (0,0) and (6,6).  Placing the first at (2,2) seems to put the next four spies at (0,6), (6,0) and (6,6).  The appears to pick (6,3) is this right?

Not sure how to proceed.

Posted by Jer on 2007-07-30 16:55:43