Friday, December 18, 2009

Merry (concurrent) Xmas

Can you solve the Santa Claus problem?
Santa repeatedly sleeps until wakened by either all of his nine reindeer, back from their holidays, or by a group of three of his ten elves.
(1) If awakened by the reindeer, he harnesses each of them to his sleigh, delivers toys with them and finally unharnesses them (allowing them to go off on holiday).
(2) If awakened by a group of elves, he shows each of the group into his study, consults with them on toy R&D and finally shows them each out (allowing them to go back to work).
(3) Santa should give priority to the reindeer in the case that there is both a gorup of elves and a group of reindeer waiting.

[source].

A longer discussion of this nice problem: How to Solve the Santa Claus Problem.

No comments:

Post a Comment