Place 16 people in a 4x4x4 grid of rooms so that the smallest distance between any two of them is as large...

geometry/lattice/sixteen.geeks New

New entry, edited from material collected for the archive and not yet in a released version.

Problem

Place 16 people in a 4x4x4 grid of rooms so that the smallest distance
between any two of them is as large as possible.

Sixteen computer geeks work in an otherwise-vacant office building.
It has 4 floors and each floor has 16 rooms arranged in a 4 x 4 grid.
The rooms are numbered 1A1 thru 4D4 in the normal griddy way.  Since
these guys are all working on top-secret government projects, they
need to keep as far apart as possible by simple distance =
sqrt((f1-f2)^2 + (h1-h2)^2 + (r1-r2)^2).  How to assign them to the
rooms so they will all be as far apart as possible?  Score each
solution by the smallest geek-to-geek distance.

-- Woody Brison <william.w.brison@den.mmc.com>

Show solution

My assumptions:  Every office is a cube, the location of a geek within
his office is irrelevant, and "distance" really means linear distance
from office to office in 3-space.  So we're really talking about
choosing 16 of 64 3D lattice points, such that the shortest distance
between two points is maximized.

I'll make the obvious first guess, which seems so ridiculously easy
that there must be something better.

Asterisks represent geek offices:

* - * -     - - - -     * - * -     - - - -
- - - -     - * - *     - - - -     - * - *
* - * -     - - - -     * - * -     - - - -
- - - -     - * - *     - - - -     - * - *

Shortest distance between two geeks is sqrt(3), which occurs for quite
a number of pairs of geeks.

ObPuz1:  How many?
ObPuz2:  What's the average distance between two geeks?

-- Tom Magliery <mag@ncsa.uiuc.edu>

[ Editor: no better placement, proof of optimality, or answers to the
  two ObPuzzles were found in the collected postings. ]

Woody Brison wrote:
> Sixteen computer geeks work in an otherwise-vacant office
> building.  It has 4 floors and each floor has 16 rooms arranged in
> a 4 x 4 grid.  The rooms are numbered 1A1 thru 4D4 in the
> normal griddy way.  Since these guys are all working on top-secret
> government projects, they need to keep as far apart as possible by
> simple distance = sqrt((f1-f2)^2 + (h1-h2)^2 + (r1-r2)^2).  How to
> assign them to the rooms so they will all be as far apart as
> possible?  Score each solution by the smallest geek-to-geek
> distance.

A best solution is such that the smallest distance is sqrt(3).

Where X represents a Geek:

levels 1,3:O X O X
           O O O O
           O X O X
           O O O O

levels 2,4:O O O O
           X O X O
           O O O O
           X O X O

A solution with smallest length 2 is impossible, as no more than 4 may
fit on the first level with this constraint, placing exactly one in
each quadrant of the square.
Level two would then need to be empty if one were to avoid a length
less than two, as each quadrant must be empty due to the presence of a
geek in the immediate lower quadrant.
So, no solution of length > sqrt(3) [Editor: "<" in the original]
exists.

-- Tim Firman <firman@lombardi.chem.wisc.edu>, October 1996