Mon, 05 Jan 2004 18:48:04 -0500 asimovd@aol.com I vaguely recall one of this type (in a 1958 book, "Puzzle-Math", by G. Gamow & M. Stern) which concerned determining which wives were cheating on their husbands, but I can't recall the details -- except that it took 40 days to deduce who the cheaters were. There are many variants of this problem. The basic outline runs roughly: There is an omniscient and omnipotent king in a village with N couples. The king announces [something like]: "One wife in this village is unfaithful. I command the husband of that wife to kill her on the day he deduces that he has been cuckolded." Exactly when the poor husband figures out that he is the cuckold depends on what partial knowledge each man has, and on the value of N, and on the precise announcement the king makes. For example, suppose every man knows whether every wife other than his own is having an affair, and everyone hears (and can count) the executions. Then, if the king's announcement is exactly as I described above, then the man who thinks that no one is having an affair, knows immediately that he is the cuckold and follows the king's order on the first day. Alternatively, if the king simply says: "Some wives in this village are unfaithful. I command each husband of an unfaithful wife to kill her on the day he deduces that he has been cuckolded", then if K wives are unfaithful, there are K husbands who think that only K-1 wives are unfaithful. If day K-1 passes with no one being executed then all the K husbands kill their wives on day K. (Or, if the King announces the value of K, then they can decide on the first night. Or...). I use less gruesome versions of these problems when I teach distributed systems; I pose them as puzzles about how independent nodes can reach certain kinds of decisions in synchronous systems with almost no communication. The book is, I fear, out of print, but many local libraries may have copies. Dan Asimov _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun