Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83; site mit-eddie.UUCP
Path: utzoo!watmath!clyde!akgua!mcnc!decvax!genrad!mit-eddie!smh
From: smh@mit-eddie.UUCP (Steven M. Haflich)
Newsgroups: net.math
Subject: Re: The British Soldiers Problem
Message-ID: <1946@mit-eddie.UUCP>
Date: Sat, 26-May-84 09:24:19 EDT
Article-I.D.: mit-eddi.1946
Posted: Sat May 26 09:24:19 1984
Date-Received: Fri, 1-Jun-84 21:11:33 EDT
References: <577@decwrl.UUCP>
Organization: MIT, Cambridge, MA
Lines: 19

This problem is also known as the "firing squad synchronization
problem."  It appears as a problem in Marvin Minsky [Computation:
Finite and Infinite Machines] (1967) who quotes the problem verbatim
from Edward Moore [Sequential Machines: selected Papers] (1964).
A brief synopsis:

Moore claimed the problem was originaly devised about 1957 by John
Myhill, and was first solved by John McCarthy and Minsky.  Moore claims
that once the problem was known to have a solution, almost everyone can
solve it.  He emphasizes the beauty of working out the problem for
oneself, so I will not spoil the trick.  Moore adds, however, that most
people do not come close to the minimal-time solution, which for N
soldiers has the firing occur 2N-2 clock ticks after the order is given.

Minsky discusses the nature of the solution (without giving it
completely) "in the back of the book."  If urged, I could be convinced
to post a similar description in a couple weeks.

Steven Haflich, MIT