A Communication Problem to think about ...

A spy working under cover needs to pass messages to a colleague. He does this by leaving coded messages on several different notice boards, at different locations. The colleague never leaves any messages for the spy, so the message passing is one way. The latest message left by the spy supersedes all previous messages and thus the colleague should try to read the most up to date message available, and not any earlier ones. Therefore if the colleague is unable to read a message for some period, and the the spy has updated several messages, he should aim to read the most up to date message available. This means that some messages may not be read by the colleague at all, but this is acceptable.

So that the spy and his colleague are never associated, they must both lead independent lives, never meet or be seen together, and they must never know who the other person is. This means that the spy can never change a message on a notice board that the colleague is likely to visit, and the colleague can never visit a board where the spy could be updating a message. This limitation has the effect that the spy should never update consecutive notices at the same notice board, because if the spy is currently updating a message, then the colleague must still be able to pick up the last message. They must be free to post / read messages at their own convenience, waiting is not acceptable because this will disrupt their rythme of daily life and may look suspicious.

If the colleague reads the same message more than once then this is an indicator that the spy has no new information.

The problem is this:- What is the minimum number of notice boards for the messages needed to guarantee the spy and the colleague never meet?

You will find that there needs to be some other form of communication between them, i.e. to indicate where the most up to date notice is, where the colleague is currently visiting, etc. What form of communication could be used for this? (hint - this comminication will probably need to be two way, but the spy and colleague must still never meet).

Picture showing the spy, his colleague and noticeboards.

Please email possible solutions to me. Thanks!
[Back to HomePage]

Copyright © - Ian G. Clark
Last modified 4/8/98