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?

I think the best way to define the distance is as follows:
Let x be the side to side distance in the grid between two tables and let y be the front to back distance.  Then define the overall distance be y + x/2 if y>x and x + y/2 otherwise.

For example consider:
# A # B
# # # #
# # # #
C # # #

For pair A,B: x=2 and y=0 which makes the distance 2 + 0/2 = 2
For pair A,C: x=1 and y=3 which makes the distance 3 + 1/2 = 3.5
For pair B,C: x=3 and y=3 which makes the distance 3 + 3/2 = 4.5

Posted by Brian Smith on 2007-08-03 20:55:54