Five madmen hide in an infinite square grid of trees, each uprooting one tree and standing in its place.

geometry/lattice/madmen.in.forest New

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

Problem

Five madmen hide in an infinite square grid of trees, each uprooting
one tree and standing in its place.  Can they stand so that each of
them sees the other four?

Here is a tough puzzle, with a very elegant solution (I promise!):

FIVE madmen escape from an insane asylum (started out good!?).  To
escape the authorities, they flee into an infinite forest with trees
planted evenly in rows and columns, like this:

T  T  T  T  T  T  T ...

T  T  T  T  T  T  T ...

T  T  T  T  T  T  T ...

T  T  T  T  T  T  T ...

where a T represents a tree, and the spacing is 1 meter apart in every
direction.

Now, the (FIVE) madmen are trying to hide in this (INFINITE) forest, by
uprooting one tree each, and standing in its place.  The only problem
is that these five are afraid of getting bored, so each of them wants
to have the other four in sight.  Of course, two madmen will not see
each other if a tree or another madman is in the way.

QUESTION: can the five find a way to stand so no one is bored?

TIP: this is not a "wiseguy" solution, as in one madman standing on top
of another, or something to this effect.

HAPPY HIDING!

-- Meir Guttman <mguttman@netvision.net.il>, September 1995

Show solution

Answer:  No

Proof:

Pick a tree as the origin, (0,0) and number all trees from that point.
If a man is standing at (x,y), then no man can be standing at
(x+2i,y+2j), because the view would be blocked by the man or tree at
(x+i,y+j).  In other words, no man can be at coordinates where the x
and y both share the same even/odd combination as another man.  There
are only 4 ways to select different even/odd combinations of x and y
coordinates, so at most 4 men will be able to find locations where they
will be able to all see each other.

-- Stephen H. Landrum <slandrum@ntg.com>

Ignoring "wiseguy" solutions, I believe the answer is NO.

My reasoning goes as follows:-

The X or Y difference between any pair of madmen who can see each other
must be odd.  The differences may both be odd, but they can't both be
even.

(Whenever the differences are both even, then the point exactly half
way between them has integer coordinates and therefore must be occupied
by a tree or another madman.)

Four madmen can position themselves with X,Y values which are
respectively:-

   Even, Even
   Even, Odd
   Odd,  Even
   Odd,  Odd

There is no other combination for the fifth madman to choose.  If, for
example, he stands at a position which is (Even,Odd) then he cannot see
the other madman who is standing in an (Even,Odd) position because both
the X and Y differences are even.

-- Mike Williams <mike@econym.demon.co.uk>

Walter Prager <wprager@Newbridge.COM> wrote:
>The "solution" (included below) assumes that the forest is infinite
>in both the number of rows and columns, but in the original diagram
>it looks like there are just four rows, and an infinite number of
>columns.  That's the part that makes it difficult.

Can't be done in four rows, I think.  Here's an outline of a proof.

1. If two men are on the same row, they must be adjacent

2. Since we have four rows and five men, at least two of the men must
   be on the same row and thus adjacent -- call this row A.

Lemma: at least one man must be somewhere on a row two rows away from
   row A.
Proof:  Assume not.  Then the three remaining men can't all be on
   different rows, since one of them would be two rows away from row
   A.  This means another row (B) has two men on it, and they're
   adjacent.  By hypothesis, this row is either adjacent to row A or
   three rows away.  If it's adjacent, then the fifth man cannot be
   placed, since it would be two away from one or the other.  If A and
   B are three rows away (bookends on the forest, as it were), then the
   fifth man would be on a middle row, and again would be two rows away
   from one or the other.

3. Now we're done, because no man cannot be placed on a row two rows
   away from a row with two adjacent men without having a tree blocking
   his view from one or the other adjacent man, because his distance is
   an even number of columns away from one of the two men, and thus
   there'll be a tree blocking his view on the single intervening row.

So the forest can't be any narrower than five rows deep.  Here's a
fiver, I think.

T T m T T T T T T
m T T T T T T T T
T T T m T T T T T
T m T T T T T T T
T T T T T T T T m

-- Jim Gillogly <jim@acm.org>

[ Editor: by the parity argument above the fiver cannot work: numbering
rows and columns from 0, the men in row 0, column 2 and row 4, column 8
are 4 rows and 6 columns apart, and the tree at row 2, column 5 is
halfway between them. ]

gw@cdc.hp.com (Gordon Wilson) wrote:
>Is this it?
>
>: T  m  T  T  T  T  T ...
>     ^
>: T  T  T  T  T  T  T ...
>
>: T  T  T  T  T  T  T ...
>
>: T  T  T  m  T  T  T ...
>
>: T  T  m  m  T  T  T ...
>           ^
>: m  T  T  T  T  T  T ...

No, the indicated men can't see each other.

Proof that no solution exists:

1) Two madmen in the same row or column must be adjacent.
   Proof:  Otherwise there's at least one tree between them in that row
           or column.

2) Three madmen can't be in the same row or column.
   Proof:  One must be between the other two, blocking their view of
           each other.

3) If two madmen are an even number of rows apart, no third madman can
   be an even number of rows apart from both.
   Proof:  To avoid a tree at their halfway point, the first two madmen
           must be an odd number of columns apart.  Any third madman
           must be in a different row (by #2), must be an even number
           of columns apart from one or the other, and his view of that
           one is blocked by a tree at the halfway point.

4) If two madmen are adjacent in a row, no third madman can be an even
   number of rows apart from them.
   Proof:  The first two are an odd number of columns apart, and the
           rest is the same as the second half of #3.

5) For a given row R, define S(R) as the set consisting of row R plus
   all rows an even number of rows away from it.  At most two madmen
   can be in S(R).
   Proof:  The first two are either in the same row (thus adjacent by
           #1, thus no third madman can be in S(R) by #4) or in
           different rows (thus no third madman can be in S(R) by #3).

6) At most four madmen can occupy an infinite forest under the
   conditions described in the puzzle.
   Proof:  Consider row R1 and an adjacent row R2.  We can assign at
           most two madmen to each of S(R1) and S(R2), and S(R1) +
           S(R2) = the entire forest.

-- Ed Murphy ("Ford Prefect") <ford@ee.tulane.edu>

They must be mad.  (2^d)+1 lattice points (integral coordinates) in a
d-dimensional lattice imply that two points are identical when if you
reduce coordinates mod 2.  This means that there is a tree (or madman)
exactly half-way between those two.

Related problems:

1) How many lattice points does it take to imply that there exist
   madmen with at least n trees between them?

2) How many lattice points imply that some triple (or n-tuple) has a
   lattice point as a center of mass (coordinate-wise average)?

3) Suppose the madmen can see through trees, but require that they can
   face in one direction and see all others (in a 180 degree field of
   vision).  What is the smallest area/volume of the region between k
   madmen in d dimensions?

The first is not hard, the second is open for large parameters, and I
don't know about the third.

-- Douglas J. Zare <zare@cco.caltech.edu>