Re: [math-fun] looking for state-of-knowledge logic puzzles
Eugene Salamin <gene_salamin@yahoo.com> 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 .... ... As the traveler passes through, he casually remarks, "Some people in this village have blue dots". Ten days later, ....
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.
I believe the phrase "he casually remarks" should read "he publically announces," meaning that he states it in a way that (1) everyone hears and believes him, (2) everyone knows that (1) occurs, (3) everyone knows that (2) occurs, (4) everyone knows that (3) occurs, etc. all at the same time. It takes about N such pieces of information to make the clock tick for N days. Dan
Yes, I believe Dan's reply to Gene has it exactly right. In order for the puzzle to work, everyone must hear the traveler's statement. Gene comments that the information provided by the traveler was already known to everybody. I find this the most fascinating aspect of the puzzle. For it is true that everybody already knows that "Some people in this village have blue dots", since everybody can see at least nine blue dots in the village. The traveler, however, must be providing new information; otherwise, the deductions that play out as a consequence would have played out long ago. And, as Dan points out, the information that the traveler is unwittingly providing is that now everybody knows that everybody knows that everybody knows . . . that some people have blue dots. This is clearest in the case of a village with just two blue dots, B1 and B2: prior to the utterance by the traveler, B1 did not know that B2 knew that there were some blue dots. JSS Dan Hoey wrote:
Eugene Salamin <gene_salamin@yahoo.com> 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 .... ... As the traveler passes through, he casually remarks, "Some people in this village have blue dots". Ten days later, ....
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.
I believe the phrase "he casually remarks" should read "he publically announces," meaning that he states it in a way that (1) everyone hears and believes him, (2) everyone knows that (1) occurs, (3) everyone knows that (2) occurs, (4) everyone knows that (3) occurs, etc. all at the same time.
It takes about N such pieces of information to make the clock tick for N days.
Dan
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Tuesday 06 January 2004 11:22, Joshua Singer wrote:
Yes, I believe Dan's reply to Gene has it exactly right. In order for the puzzle to work, everyone must hear the traveler's statement.
Case 1. All reds and one blue happen to hear the statement. Blue must leave town. Case 2. All reds and one two blues happen to hear the statement. A blue deducts that other would have left town if he was red so he leaves town. Other blue catches on and leaves. Case 3. All reds and three blues. No blue leaves, a blue deducts that another blue would have figured out case two if he had a red dot. etc. These kinds of problems require that each blue dot have confidence in every other blue dots reasoning ability and the time it takes to solve a not very tractable problem. Assume a clock work reasoning technique on all of the blue dots and knowledge about how long it would take another to figure out a simpler problem. I am not sure that this kind of reasoning sequence can even be modeled well on a computer. How long does the computer blue dot program wait to determine to have confidence that the other blue dot program has solved the problem? Do all the blue programs exit the town at once, or does the smartest (or dumbest) program exit first? If the blue programs are are equally intelligent, then there is an apparent inconsistency since none can reach the conclusion first, yet if they are unequally intelligent, who leaves town first? Does he smartest machine, machine 10, wait until the next smartest machine, machine 9 has solved the simpler problem? Unfortunately, machine nine is faced with the same problem as 10. Therefore machine 10 has to wait a sufficient amount of time to insure that everyone else has figured out the problem. I am not sure it would not work if we allowed the machines to solve the problem in a random amount of time. What if the machines are smart enough to follow the above reasoning. My suspicion is that on carefull analysis this kind of problem might in reality fall into the undecidable class of problems and has no solution. My suspicion is that there really is no group of people (or automatons-programs) that could be built that could with confidence reach a conclusion and vacate the town. The problem of determining when another automaton may solve a problem of this sort, may be similar to deciding when a touring machine will stop when given an arbitrary program. Are there any studies of undecidability or theorems that might throw light on this problem? I am very suspicious of the solution when we can not say who the first blue-person is to deduce that he is the last blue-person to deduce the solution. Regards Otto otto@olympus.net
Gene comments that the information provided by the traveler was already known to everybody. I find this the most fascinating aspect of the puzzle. For it is true that everybody already knows that "Some people in this village have blue dots", since everybody can see at least nine blue dots in the village. The traveler, however, must be providing new information; otherwise, the deductions that play out as a consequence would have played out long ago. And, as Dan points out, the information that the traveler is unwittingly providing is that now everybody knows that everybody knows that everybody knows . . . that some people have blue dots. This is clearest in the case of a village with just two blue dots, B1 and B2: prior to the utterance by the traveler, B1 did not know that B2 knew that there were some blue dots.
JSS
Dan Hoey wrote:
Eugene Salamin <gene_salamin@yahoo.com> 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 .... ... As the traveler passes through, he casually remarks, "Some people in this village have blue dots". Ten days later, ....
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.
I believe the phrase "he casually remarks" should read "he publically announces," meaning that he states it in a way that (1) everyone hears and believes him, (2) everyone knows that (1) occurs, (3) everyone knows that (2) occurs, (4) everyone knows that (3) occurs, etc. all at the same time.
It takes about N such pieces of information to make the clock tick for N days.
Dan
_______________________________________________ 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
Tue, 6 Jan 2004 12:50:28 -0800 Otto Smith <otto@olympus.net> ....If the blue programs are are equally intelligent, then there is an apparent inconsistency since none can reach the conclusion first, yet if they are unequally intelligent, who leaves town first? ... My suspicion is that on carefull analysis this kind of problem might in reality fall into the undecidable class of problems and has no solution. My suspicion is that there really is no group of people (or automatons-programs) that could be built that could with confidence reach a conclusion and vacate the town. The problem of determining when another automaton may solve a problem of this sort, may be similar to deciding when a touring machine will stop when given an arbitrary program. There are problems that are unsolvable in asynchronous systems, but solvable in synchronous systems. If you take the statement "within 24 hours" to mean that the system is broken up into discrete day-long intervals, then this problem becomes synchronous, and the race condition you worry about doesn't exist. If there are N blue dots, then each of the blue programs knows that there are either N-1 blue dots and his is not blue, or there are N blue dots and his *is* blue (the truth). If there were N-1 blue dots, then the other blue programs would be trying to determine whether there were N-2 or N-1 dots. Once the "clock starts running" (after the announcement), then the N-1 blues would have left on the N-1st day. Once the N-1st day is complete, and no one has departed, then the N blue programs now know there are N blue dots and that they are blue and they have 24 hours in which to depart. There is no race condition, and it doesn't matter who figures it out first.
On Tuesday 06 January 2004 13:12, Michael B Greenwald wrote:
There are problems that are unsolvable in asynchronous systems, but solvable in synchronous systems. If you take the statement "within 24 hours" to mean that the system is broken up into discrete day-long intervals, then this problem becomes synchronous, and the race condition you worry about doesn't exist.
OK, so they must leave at sunup on the following day, also it must be taboo for anyone in any circumstance to mention the color of a dot on anyones head. If someone in the town says, "some of the town folks have blue dots", and all the town folk know who spoke this way and believe it, it is equivalent to a stranger saying it. Thanks for the observation about synchronous systems vs asynchronous. Maybe the physical world is really synchronous not asynchronous. There is some current evidence that time is discrete. Regards Otto otto@olympus.net
Tue, 6 Jan 2004 12:50:28 -0800 Otto Smith <otto@olympus.net>
....If the blue programs are are equally intelligent, then there is an apparent inconsistency since none can reach the conclusion first, yet if they are unequally intelligent, who leaves town first? ... My suspicion is that on carefull analysis this kind of problem might in reality fall into the undecidable class of problems and has no solution. My suspicion is that there really is no group of people (or automatons-programs) that could be built that could with confidence reach a conclusion and vacate the town. The problem of determining when another automaton may solve a problem of this sort, may be similar to deciding when a touring machine will stop when given an arbitrary program.
There are problems that are unsolvable in asynchronous systems, but solvable in synchronous systems. If you take the statement "within 24 hours" to mean that the system is broken up into discrete day-long intervals, then this problem becomes synchronous, and the race condition you worry about doesn't exist.
If there are N blue dots, then each of the blue programs knows that there are either N-1 blue dots and his is not blue, or there are N blue dots and his *is* blue (the truth). If there were N-1 blue dots, then the other blue programs would be trying to determine whether there were N-2 or N-1 dots. Once the "clock starts running" (after the announcement), then the N-1 blues would have left on the N-1st day. Once the N-1st day is complete, and no one has departed, then the N blue programs now know there are N blue dots and that they are blue and they have 24 hours in which to depart. There is no race condition, and it doesn't matter who figures it out first.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (4)
-
Dan Hoey -
Joshua Singer -
Michael B Greenwald -
Otto Smith