Re: [math-fun] looking for state-of-knowledge logic puzzles
Scott asks: << ... Then two mathematicians iterate for awhile, A: I can't deduce the answer. B: Neither can I. A: I still can't deduce the answer. ... and after a few rounds of this one of them can deduce the answer. Can anyone supply some puzzles of this flavor? (without answer :-)
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. The book is, I fear, out of print, but many local libraries may have copies. Dan Asimov
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
As it was originally told to me . . . A traveler passes through a small village, each of whose inhabitants has a single colored dot on his or her forehead. Some have a blue dot, some have a red dot, some have a green dot, etc. Each person can see every other person's dot, but cannot see his own. Because the village is small, every person knows the color of every other person's dot, except his own. It is taboo in the village to know the color of one's own dot. The village's strict rule is that anyone discovering the color of his own dot must leave the village within 24 hours, never to return. As the traveler passes through, he casually remarks, "Some people in this village have blue dots". Ten days later, the ten people from the village who had blue dots have all vanished. The problem is to explain how the departure of the ten people occurred. JSS asimovd@aol.com wrote:
Scott asks:
<< ... Then two mathematicians iterate for awhile, A: I can't deduce the answer. B: Neither can I. A: I still can't deduce the answer. ...
and after a few rounds of this one of them can deduce the answer.
Can anyone supply some puzzles of this flavor? (without answer :-)
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.
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
Here are some more subtle examples. 1.You and I have numbers on our foreheads and are told (truthfully) that their total is either 5, 8 or 15. A bell rings every ten seconds and after each ring if either of us knows our number we announce it and win. Prove: For any pair of forehead numbers one of us will know our number after at most 10 rings. (Curiously, if the numbers are 5,9,15 then the bell can ring until the cows come home and there will be no winner). 2. (Conway-Paterson) In the three player game with forehead numbers 2,2,2 and possible totals 6,7,8 the players will know their numbers after on the 15th ring. To see why buy my book. (Amazon usually ships in 24 hours) David At 04:52 PM 1/5/04 -0800, you wrote:
As it was originally told to me . . .
A traveler passes through a small village, each of whose inhabitants has a single colored dot on his or her forehead. Some have a blue dot, some have a red dot, some have a green dot, etc. Each person can see every other person's dot, but cannot see his own. Because the village is small, every person knows the color of every other person's dot, except his own. It is taboo in the village to know the color of one's own dot. The village's strict rule is that anyone discovering the color of his own dot must leave the village within 24 hours, never to return. As the traveler passes through, he casually remarks, "Some people in this village have blue dots". Ten days later, the ten people from the village who had blue dots have all vanished.
The problem is to explain how the departure of the ten people occurred.
JSS
asimovd@aol.com wrote:
Scott asks:
<< ... Then two mathematicians iterate for awhile, A: I can't deduce the answer. B: Neither can I. A: I still can't deduce the answer. ...
and after a few rounds of this one of them can deduce the answer.
Can anyone supply some puzzles of this flavor? (without answer :-)
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.
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
You wouldn't believe what you get when you are searching for David Gale on Amazon ("The Life of David Gale" included!). What is the name of your book? Helger On Mon, 5 Jan 2004, David Gale wrote:
Here are some more subtle examples.
1.You and I have numbers on our foreheads and are told (truthfully) that their total is either 5, 8 or 15. A bell rings every ten seconds and after each ring if either of us knows our number we announce it and win. Prove: For any pair of forehead numbers one of us will know our number after at most 10 rings. (Curiously, if the numbers are 5,9,15 then the bell can ring until the cows come home and there will be no winner).
2. (Conway-Paterson) In the three player game with forehead numbers 2,2,2 and possible totals 6,7,8 the players will know their numbers after on the 15th ring.
To see why buy my book. (Amazon usually ships in 24 hours)
David
At 04:52 PM 1/5/04 -0800, you wrote:
As it was originally told to me . . .
A traveler passes through a small village, each of whose inhabitants has a single colored dot on his or her forehead. Some have a blue dot, some have a red dot, some have a green dot, etc. Each person can see every other person's dot, but cannot see his own. Because the village is small, every person knows the color of every other person's dot, except his own. It is taboo in the village to know the color of one's own dot. The village's strict rule is that anyone discovering the color of his own dot must leave the village within 24 hours, never to return. As the traveler passes through, he casually remarks, "Some people in this village have blue dots". Ten days later, the ten people from the village who had blue dots have all vanished.
The problem is to explain how the departure of the ten people occurred.
JSS
asimovd@aol.com wrote:
Scott asks:
<< ... Then two mathematicians iterate for awhile, A: I can't deduce the answer. B: Neither can I. A: I still can't deduce the answer. ...
and after a few rounds of this one of them can deduce the answer.
Can anyone supply some puzzles of this flavor? (without answer :-)
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.
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
My article Formalization of two Puzzles Involving Knowledge http://www-formal.stanford.edu/jmc/puzzles.html covers both the wise man puzzle and Mr S and Mr P. The point of the article is to express the puzzles in first order logic and push an interactive theorem prover to their solutions. There is a variant of the wise men puzzle called the puzzle of the 40 unfaithful wives in Baghdad. There is obviously a solution beginning "if my wife were faithful there would be only 39 unfaithful wives and each of the husbands would have reasoned ...". However, Arabs, at least before the Mongols wiped out Baghdad in 1258 were capable of mathematical induction. I don't have and would like to see a formalization in which the Arabs use mathematical induction. A judicious use of the word "etc." should do it.
My latest column, on Cubic Symmetric Graphs, is now available at http://maa.org/editorial/mathgames/mathgames_12_29_03.html I particularly like how my picture of the Coxeter Graph turned out. Find cycles of length 7, 8, 9, 10, ... -- and look at the distribution of colors. I find this property amazing. I'd like to hear the reactions of some children shown this graph, and asked to find 7 and 8 cycles. --Ed Pegg Jr, www.mathpuzzle.com
What are the constraints on the numbers that can be on our foreheads? I am assuming the only candidates are the positive integers 1, 2, ... ,14, with no zeros or negative numbers allowed? JSS David Gale wrote:
Here are some more subtle examples.
1.You and I have numbers on our foreheads and are told (truthfully) that their total is either 5, 8 or 15. A bell rings every ten seconds and after each ring if either of us knows our number we announce it and win. Prove: For any pair of forehead numbers one of us will know our number after at most 10 rings. (Curiously, if the numbers are 5,9,15 then the bell can ring until the cows come home and there will be no winner).
2. (Conway-Paterson) In the three player game with forehead numbers 2,2,2 and possible totals 6,7,8 the players will know their numbers after on the 15th ring.
To see why buy my book. (Amazon usually ships in 24 hours)
David
At 04:52 PM 1/5/04 -0800, you wrote:
As it was originally told to me . . .
A traveler passes through a small village, each of whose inhabitants has a single colored dot on his or her forehead. Some have a blue dot, some have a red dot, some have a green dot, etc. Each person can see every other person's dot, but cannot see his own. Because the village is small, every person knows the color of every other person's dot, except his own. It is taboo in the village to know the color of one's own dot. The village's strict rule is that anyone discovering the color of his own dot must leave the village within 24 hours, never to return. As the traveler passes through, he casually remarks, "Some people in this village have blue dots". Ten days later, the ten people from the village who had blue dots have all vanished.
The problem is to explain how the departure of the ten people occurred.
JSS
asimovd@aol.com wrote:
Scott asks:
<< ... Then two mathematicians iterate for awhile, A: I can't deduce the answer. B: Neither can I. A: I still can't deduce the answer. ...
and after a few rounds of this one of them can deduce the answer.
Can anyone supply some puzzles of this flavor? (without answer :-)
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.
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
In fact the forehead numbers need not be integers. Any non-negative real is ok. Zero is legal and the game ends after two dings. Negative numbers are not allowed.; DG At 12:18 PM 1/6/04 -0800, you wrote:
What are the constraints on the numbers that can be on our foreheads? I am assuming the only candidates are the positive integers 1, 2, ... ,14, with no zeros or negative numbers allowed?
JSS
David Gale wrote:
Here are some more subtle examples.
1.You and I have numbers on our foreheads and are told (truthfully) that their total is either 5, 8 or 15. A bell rings every ten seconds and after each ring if either of us knows our number we announce it and win. Prove: For any pair of forehead numbers one of us will know our number after at most 10 rings. (Curiously, if the numbers are 5,9,15 then the bell can ring until the cows come home and there will be no winner).
2. (Conway-Paterson) In the three player game with forehead numbers 2,2,2 and possible totals 6,7,8 the players will know their numbers after on the 15th ring.
To see why buy my book. (Amazon usually ships in 24 hours)
David
At 04:52 PM 1/5/04 -0800, you wrote:
As it was originally told to me . . .
A traveler passes through a small village, each of whose inhabitants has a single colored dot on his or her forehead. Some have a blue dot, some have a red dot, some have a green dot, etc. Each person can see every other person's dot, but cannot see his own. Because the village is small, every person knows the color of every other person's dot, except his own. It is taboo in the village to know the color of one's own dot. The village's strict rule is that anyone discovering the color of his own dot must leave the village within 24 hours, never to return. As the traveler passes through, he casually remarks, "Some people in this village have blue dots". Ten days later, the ten people from the village who had blue dots have all vanished.
The problem is to explain how the departure of the ten people occurred.
JSS
asimovd@aol.com wrote:
Scott asks:
<< ... Then two mathematicians iterate for awhile, A: I can't deduce the answer. B: Neither can I. A: I still can't deduce the answer. ...
and after a few rounds of this one of them can deduce the answer.
Can anyone supply some puzzles of this flavor? (without answer :-)
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.
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Tue, Jan 06, 2004 at 01:57:53PM -0800, David Gale wrote:
In fact the forehead numbers need not be integers. Any non-negative real is ok. Zero is legal and the game ends after two dings. Negative numbers are not allowed.;
Which game are you talking about when you say the game ends after two dings with a zero? With the 6, 8, 15 game I found that the game can take up to 6 dings when there is a zero. Unless I made some mistake? Peace, Dylan
Sorry again. I was thinking of the two-person, two-number game. If the public numbers are a<b and if my number is zero then you will know you are either a or b but if you were b then I would have won after the first ding. You are right, in the 6,8,15 game the forehead pair (0,8) takes 6 dings. DG At 06:53 PM 1/6/04 -0500, you wrote:
On Tue, Jan 06, 2004 at 01:57:53PM -0800, David Gale wrote:
In fact the forehead numbers need not be integers. Any non-negative real is ok. Zero is legal and the game ends after two dings. Negative numbers are not allowed.;
Which game are you talking about when you say the game ends after two dings with a zero? With the 6, 8, 15 game I found that the game can take up to 6 dings when there is a zero. Unless I made some mistake?
Peace, Dylan
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Tue, Jan 06, 2004 at 01:57:53PM -0800, David Gale wrote:
In fact the forehead numbers need not be integers. Any non-negative real is ok. Zero is legal and the game ends after two dings. Negative numbers are not allowed.;
Which game are you talking about when you say the game ends after two dings with a zero? With the 6, 8, 15 game I found that the game can take up to 6 dings when there is a zero. Unless I made some mistake?
Peace, Dylan
The 5,8,15 game with 0 allowed can last 10 rounds. Games with 0 last 5 or 6 rounds. With 0 not allowed the longest game is 4 rounds. Different deductions, so 0-possibly is important in specifying the game. Nice family of puzzles! I'm still stumped by the 3-player 6,7,8 games with 2,2,2 showing. - Scott
--- Joshua Singer <singer@stanford.edu> wrote:
As it was originally told to me . . .
A traveler passes through a small village, each of whose inhabitants has a single colored dot on his or her forehead. Some have a blue dot, some have a red dot, some have a green dot, etc. Each person can see every other person's dot, but cannot see his own. Because the village is small, every person knows the color of every other person's dot, except his own. It is taboo in the village to know the color of one's own dot. The village's strict rule is that anyone discovering the color of his own dot must leave the village within 24 hours, never to return. As the traveler passes through, he casually remarks, "Some people in this village have blue dots". Ten days later, the ten people from the village who had blue dots have all vanished.
The problem is to explain how the departure of the ten people occurred.
JSS
This can't be right. The information provided by the traveler was already known to everybody. In the case of the problem of the unfaithful wives, the king issues an edict, which starts the clock ticking. Gene __________________________________ Do you Yahoo!? Yahoo! Hotjobs: Enter the "Signing Bonus" Sweepstakes http://hotjobs.sweepstakes.yahoo.com/signingbonus
On Tuesday 06 January 2004 08:56, Eugene Salamin wrote:
--- Joshua Singer <singer@stanford.edu> wrote:
As it was originally told to me . . .
A traveler passes through a small village, each of whose inhabitants has a single colored dot on his or her forehead. Some have a blue dot, some have a red dot, some have a green dot, etc. Each person can see every other person's dot, but cannot see his own. Because the village is small, every person knows the color of every other person's dot, except his own. It is taboo in the village to know the color of one's own dot. The village's strict rule is that anyone discovering the color of his own dot must leave the village within 24 hours, never to return. As the traveler passes through, he casually remarks, "Some people in this village have blue dots". Ten days later, the ten people from the village who had blue dots have all vanished.
The problem is to explain how the departure of the ten people occurred.
JSS
This can't be right. The information provided by the traveler was already known to everybody. In the case of the problem of the unfaithful wives, the king issues an edict, which starts the clock ticking.
Gene
Of course the problem is to determine under what condition this occurs. Certain conditions can be eliminated --- Such as single person with a red dot hears the statement and reports it to everyone else. If we choose the right group of people to be present when the traveler makes the statement, the the solution is more obvious. All the problem asks is that we explain how it happened. It is crucial that everyone knows the color of everyones dot. For instance, if only one person had a blue dot and they heard the statement either directly or indirectly, they would have to leave town. Now consider the case of two people with blue dots who hear it directly. Regards Otto otto@olympus.net
__________________________________ Do you Yahoo!? Yahoo! Hotjobs: Enter the "Signing Bonus" Sweepstakes http://hotjobs.sweepstakes.yahoo.com/signingbonus
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (11)
-
asimovd＠aol.com -
David Gale -
dpt＠lotus.bostoncoop.net -
Ed Pegg Jr -
Eugene Salamin -
Helger Lipmaa -
John McCarthy -
Joshua Singer -
Michael B Greenwald -
Otto Smith -
Scott Huddleston