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?

Certain sizes and certain starting points will lead to spys sitting in seats that are not on pure diagonals, ie not all on the black squares of the chessboard.  Spys sitting a knights move away from each other makes a less efficient seating.  At first glance, if there are 2^n+1 on each side then a total fill of all black squares might be possible.

Posted by Larry on 2007-07-31 01:51:26