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