Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83; site decwrl.UUCP
Path: utzoo!watmath!clyde!akgua!mcnc!decvax!decwrl!dec-rhea!dec-hare!stan
From: stan@hare.DEC (Stanley Rabinowitz)
Newsgroups: net.math
Subject: The British Soldiers Problem
Message-ID: <577@decwrl.UUCP>
Date: Thu, 24-May-84 23:21:45 EDT
Article-I.D.: decwrl.577
Posted: Thu May 24 23:21:45 1984
Date-Received: Fri, 1-Jun-84 01:41:25 EDT
Organization: DEC Engineering Network
Lines: 34

THE BRITISH SOLDIERS PROBLEM.

I believe this problem was originally posed by Conway.
I'm sure you will enjoy it.  If no one comes up with a solution,
I'll post a solution in a few weeks.

You have n British soldiers in a line.  Each soldier is initially
at rest.  Each soldier is identical and his actions can be described
by a finite state automaton.  A soldier's new state depends only
on his previous state and the previous state of the two soldiers
next to him. (The two soldiers on the end have fictitious neighbors
to one side who are always in the fictitious state.)

Your problem is to design the states (e.g. rest, at ease, ready, attention,
aim, etc.) and the state transitions, so that it is possible for a sargeant
to come over and order one guy on the end into the attention state and so that
this will eventually cause all the soldiers to fire their guns
simultaneously.  No gun may fire prior to this occurrence.
You may only specify a finite number of states.
Your solution must work regardless of the value of n.
(In particular, I may line up more soldiers than you have states.)

---------------------------------
[Be sure to test any alleged solutions first via a computer simulation.]
I would also be interested in any references to this problem in the
literature.

	Stanley Rabinowitz
	Digital Equipment Corporation
	Nashua, NH

UUCP: ...{decvax,ucbvax,allegra}!decwrl!rhea!hare!stan
ARPA: stan%hare.DEC@DECWRL.ARPA
USPS: 6 Country Club Lane, Merrimack, NH 03054