Aleph-Naught Wizards
Eg, if you number the groups 1, 2, 3, ... , and group n has a probability of 1/2^n of answering, that's not sufficient.
Quote: AxiomOfChoiceIt's not quite enough for each group to have a non-zero probability of answering. You also need the sum of the probabilities to diverge (it's possible for infinitely many non-zero probabilities to sum to a finite number -- which would not be enough).
Eg, if you number the groups 1, 2, 3, ... , and group n has a probability of 1/2^n of answering, that's not sufficient.
Yeah your right I was thinking about having the sequence of probabilities have a positive limit. Though think your right and you just need the sum to diverge.
Quote: kubikulannPfff! I'm tired of people who, not understanding a result and being explained several times, continue to brag about how their little personal intuition still must be correct against all reasoning and it must henceforth be science that is wrong! No offence intended,but please take a 1O1 course in probabilities before talking about "voodoo pseudo-math". When all scientists say A and you think not-A, isn't it time to accept you are making the mistake?
Two things:
1. You're talking from the wrong end.
2. You're right.
1. My frustration with this thread goes back mainly to that other "riddle" thread, where you and others bang on ad infinitum about how "I flip two coins until one comes up tails and show you that one" is the same problem as "I flip two coins once and you see that one came up tails," and act like I'm the idiot for not getting it. They aren't the same. They won't be. And I don't think I'll be seeing a "Project Steve" on that any time soon.
2. In this thread, though, I was so on edge by the fact that practically everyone had demonstrated a bald-faced inability to recognize the gambler's fallacy dancing naked in front of you just because the events weren't arranged chronologically that I assumed this was that, not taking into account how the wizards' probabilities of guessing could be manipulated; I hadn't even opened the Wizard's solution, so I wasn't sure what you were talking about. In fact...
But that kid could still be as easily a boy as a girl.
Quote: 24Bingo1. My frustration with this thread goes back mainly to that other "riddle" thread, where you and others bang on ad infinitum about how "I flip two coins until one comes up tails and show you that one" is the same problem as "I flip two coins once and you see that one came up tails," and act like I'm the idiot for not getting it. They aren't the same. They won't be. And I don't think I'll be seeing a "Project Steve" on that any time soon.
Sorry, but I never said that. On the contrary, I (and others) state that it IS different. Hence the difference between 50% and 33.33%, according to the (different) available info.
Note: what is "Project Steve"?
Evidently, it is you here who are saying both situations are the same (namely, 50%).Quote: 24BingoBut that kid could still be as easily a boy as a girl.
Quote: kubikulannSorry, but I never said that. On the contrary, I (and others) state that it IS different. Hence the difference between 50% and 33.33%, according to the (different) available info.
No, you're being confronted with the latter and saying it's the former, again and again, because I don't know whether the coin I saw was flipped first or second. That's exactly what you're saying.
EDIT: Actually, looking at the asymptotic behavior of those integrands and their derivatives, I'm starting to think the answer probably involves power towers. I'll work it out in more detail when I'm not typing on a phone, but right now I just don't want to lose bragging rights in case someone else figures it out before then.
Quote: kubikulannI'm answering off the head, here, but remember that asking that the probability of ALL answers being correct be 90% is not asking that there be a 90% proportion of correct answers.
Quite so. Now I have a dilemma on my hands. Several people in this thread have made critically important contributions to the solution, but independently! I think if someone could combine the essentials of what's already been said, a complete and correct answer would result. [Again, harder than it sounds.]
I'm tempted to offer another hint, but I don't want to spoil the fun, unless the fun has already dissipated for most people! [If so, no harm no foul. If this were an easy problem I'm pretty sure it would have been solved days ago.]
OK, for those still determined enough to pursue it, I'll cite below what I believe to be facets of the solution, trying not to "give away the store" in the process.
This is a different problem, but its solution provides significant hints for solving the original (harder) problem.
"You collect ten wizards in a room, each (you guessed it) wearing a randomly chosen white or black hat. Again, all wizards must simultaneously either (a) declare their own hat color, or (b) remain silent. Thousands of rounds are conducted, but only rounds in which one or more wizards declare are counted toward the final score.
I claim they can collectively win 90% of the "qualifying rounds" using this strategy, based on the first two entries of the tenth row of Pascal's triangle (which is simply and easy source of binomial coefficients).
WARNING -- READ FURTHER ONLY IF YOU WISH TO SEE THE SUGGESTED GROUP STRATEGY
Only when all of his neighbors' hats are the same color, should a wizard declare the opposite color for his own hat, otherwise he should abstain. Clearly there will be many rounds for which nobody declares anything, but as mentioned earlier, those "silent" rounds do not count in the scoring.
Let me guess... You are a frequent contibutor to Wikipedia? I used to mix up their < > with the [ ] of this forum, too.Quote: dblanch256<item>Wizards should work in groups with a single "spokes-Wizard" for each group</item>
<item>Nothing prevents the wizards from forming a single infinite line corresponding to the natural numbers</item>
etc.
e.g., although I don't know where it would start, 10, 11, 12, 14, 19, 95, 46203914573123975852867, and so on...
...yeah, that seems a bit random, doesn't it? My reasoning is so sloppy I was reluctant to share it, but I guess I probably should.
Quote: kubikulannLet me guess... You are a frequent contibutor to Wikipedia? I used to mix up their < > with the [ ] of this forum, too.
Sadly no. I wish I were, but all I do is send them small donations in exchange for the unspeakable volumes of data I shamelessly suck down from them.
I rushed this reply ... so I need to fix that. Meanwhile, I thought of an easier, but very related problem that might be a good stepping stone. Give me an hour or so, and advise whether you think it's the "right kind of help".
Quote: 24BingoI think I may have figured out the general form of the answer, although I can't prove it rigorously (never was too great with series), and I'd have to work out the size of the first group (at least 10, though). Are the groups such that...
...the size of each group is the size of the previous - call it N - plus ⌊2N/N3⌋?
e.g., although I don't know where it would start, 10, 11, 12, 14, 19, 95, 46203914573123975852867, and so on...
...yeah, that seems a bit random, doesn't it? My reasoning is so sloppy I was reluctant to share it, but I guess I probably should.The reason I thought it was a power tower was looking at those integrands above. I wanted the convergent one to asymptotically approach 1/x2 to make it as likely as possible that the divergent one should diverge. To that end, I worked out the derivatives of the integrands, for the convergent one, ln 2 * f'(x)/(2f(x)-1-1), for the divergent one (ln 2 * f'(x) * f(x) - f'(x))/(2f(x)-1-f(x)). Seeing the second, I thought I probably didn't have to worry about it, as long as the first was reasonably close, so... yeah.
I think you may be "over-thinking" it. May I suggest you take a look at the Easier But Related Button I recently added? I'm pretty sure it's the logical starting point for designing the rest of the answer.
As far as I know, nobody has solved it yet. It must not be one of those deja vu problems. <wink>
Quote: MathExtremistIn that case, the strategy is something along the lines of:
a) The wizards divide themselves beforehand into a first group of N, a second group of N^2, a 3rd group of N^3, etc. Something exponential, and something such that product[1-1/2^(N^M)] as M->infinity converges to more than 90%.
b) One wizard in each group is selected to be the spokesperson for that group.
c) If the spokeswizard in each group sees an entire group of white hats, they guess black, and vice versa. Otherwise, they abstain. This is done simultaneously at the count of 3.
There are an infinite number of groups and a much smaller (but still infinite) number of guesses. If the product in (a) converges to more than 90% they will (in total) make one or more wrong guesses less than 10% of the time. If I did that right, N=5 (groups of 5, 25, 125, etc.) converges on a 96.875% success rate.
This is the closest post I've seen so far to (a) comprehending the problem (b) constructing the answer. Not quite "there" yet, but really good insights!
Quote: dblanch256I know an infinite number of wizards. If I add our own beloved Wizard to the group, that makes a grand total of, well, an infinite number of wizards! I asked them (nicely, because you don't want to piss off even a single wizard if you can help it) to prepare for a contest. They must derive a method that guarantees a winning probability of at least 90 percent given the following rules:
Each wizard will be assigned a random hat, black or white, with a probability of 1/2 for each choice. The wizards can see everyone's hat, except for their own. At the count of three, each wizard must either guess the color of his hat or abstain from guessing. The wizards collectively win if, among them, there are an infinite number of correct guesses and zero wrong guesses. What strategy do they use?
Well, it's been quite a ride. Congratulations to all who gave this problem "the good old college try". But now before this problems slips into oblivion, I'll present my own answer for peer review.
The few members either who insisted it "has no solution" or that the problem statement was "mal-formed" should know that I found it in respected Scientific Journal that is not known for making casual mistakes. Further, my solution (below) is my own, not the result of reading any published answer. Hence I'd appreciate a "peer review" for any of you willing to offer an opinion. I hope it was fun for at least some of you. If not, take heart. They're building taller and taller bridges every day ...
As I said, the cornerstone to my answer can be found along the edge and adjacent values of Pascal's triangle.
Consider the case of four wizards locked in a room wearing either black or white hats. For each round of play, a new random distribution of hats are placed on their heads. At the count of 3, looking only at each others hats, they must either declare the color of their own hat, or say nothing. For this finite-wizard example, there is no collective penalty for rounds in which all of them abstain from answering. They collectively win a round when all who do answer are correctly. They collectively loose a round if even one wizard answers incorrectly.
Their strategy should be as follows:
For each round, each wizard should declare only when he sees the same color worn by the other three. Using the fourth row of Pascals triangle ("1 4 6 4 1") shows the binomial coefficients for all 16 hat combinations, we can see immediately that the many of the rounds 6/32 will be a "wash" with all wizards abstaining. At the other extreme, (1 + 1)/16 = 1/8 of the time the hats will all be the same color (either WWWWW or BBBBB) in which case all wizards will declare, incorrectly, and collectively lose the round.
The key lies with the remaining (4 + 4)/16 = 1/2 cases for which only one wizard will guess, and guess correctly, that his hat is different. Ignoring the non-declaration (no harm no foul) cases, we see that the win/loss ratio is 8/2 = 4. In other words, for four wizards, the win percentage is 80% because the loss percentage is 2/10 or 20%.
Now it's time to "lather, rinse, repeat" (an odd shampoo instruction because it doesn't say anything about stopping ...)
Assuming that a 20% loss rate is unacceptably high, we need only to increase the number of wizards in our finite experiment. Let's use 19 this time. Using the 19th row of Pascal's triangle above gives a win percentage of 95% and a loss percentage of only 5%.
Here's the final proposal:
(1) The wizards huddle (but only for 30 seconds, to avoid a "delay of game" penalty).
(2) The wizards "break" and form an a single infinite line (effectively mapping each of them to a positive integer).
(3) Their strategy is to form well-defined groups along this line with exactly one spokes-wizard (the first of each group) speaking for the entire group.
(4) The start of the first group is the first spokes-wizard who sees the next (20-1) = 19 ahead of him wearing the same color hat. He will always guess that his hat is different from the other hats in his group and will be wrong, on average, 5% of the time. The second group will likely lie much further down the line. It starts with the first wizard to see (40-1) of same colored hats who, again speaking for the entire group, likewise guesses his hat is different, and will be wrong 2.5% of the time.
(5) Generalizing the strategy for wizard groups described above implies that successive qualifying spokes-wizards are always be the first of the nth sequenced group whose length is 20(2^n). Therefore, the upper bound for collective failure (at least one wrong answer) is (1/20 + 1/40 + 1/80 + 1/160 ...) whose limiting value is 10%. The limit for the converse (no wrong answers) is therefore 90% or better, which satisfies the original solution criteria.
I may be overlooking something, but it looks like my proposal, which was (correctly) shown false by 24bingo: how do you guarantee that there will be an infinity of responses?Quote: dblanch256I'll present my own answer for peer review.
(I prsume spoiler caches are unneeded at this stage.)Quote: dblanch256(4) The start of the first group is the first spokes-wizard who sees the next (20-1) = 19 ahead of him wearing the same color hat.
The first to see the next 19 same hats is certain that his is a different color. Otherwise his predecessor would be the first.
Also, talking of "first" seems to me to imply that they speak successively, not simultaneously. Indeed, if the first run is more than 19, several wizards may think they are the first to see 19. If they speak simultaneously, several must be wrong.
Quote: kubikulann(I prsume spoiler caches are unneeded at this stage.)
The first to see the next 19 same hats is certain that his is a different color. Otherwise his predecessor would be the first.
Also, talking of "first" seems to me to imply that they speak successively, not simultaneously. Indeed, if the first (spatially) run is more than 19, several wizards may think they are the first to see 19. If they speak simultaneously, several must be wrong.
Actually your looking at it backwards. You are looking forward so say first 19 hats were all black then the 20th person would speak. If the first 20 hats were all black you would still see the 20th person speak since he is seeing the 19 people in front of him.
Still not sure if this process works though since its not identical to just break them all into groups and guessing like you originally suggested. I don't think the 19 people in front of him tells the information we need. Think its like the birth problem from before. You suggested the scenario 1 is a boy what is the chance the other is a boy and he wrote down the first is a boy what is the chance the other child is a boy. In the first we got 1/3 second 1/2. We want the 1/3 answer for this to work but his answer, which manages to get us an infinite number of guesses, is using the setup where we are getting 1/2. Obviously I used those numbers just for the sake of comparison and not what is actually happening. But yeah in your thing you were told that 19 children were sons what is the chance the other child is a boy and that is 1/20 in his we were told the first 19 were sons what is the chance that the 20 is a boy and that is clearly 1/2.
I don't think Pascals triangle will work here since we are either left with your scenario which doesn't necessarily give us an infinite number of guesses or Kubi's which gives us infinite guesses but each of those guesses are all cointosses.
Edit: Hey Bingo have you had any more luck with a power series approach to this problem?
Quote: dblanch
(4) The start of the first group is the first spokes-wizard who sees the next (20-1) = 19 ahead of him wearing the same color hat. He will always guess that his hat is different from the other hats in his group and will be wrong, on average, 5% of the time.
I disagree. The first wizard to see 19 wizards of the same color hat before him will have exactly 50% chance of matching those hats. Each guessing wizard will have a 50% chance of failure.
The binomial distribution doesn't mean anything in this case because it is not a randomly selected group of 20 wizards.
Quote: kubikulannI may be overlooking something, but it looks like my proposal, which was (correctly) shown false by 24bingo: how do you guarantee that there will be an infinity of responses?
Hold up - not me. CrystalMath. I still hadn't caught on to the idea of spokeswizards at that point.
It's not that similar to any of our solutions, because those all involved fixed groups. I'm not sure about the logic here, though. I'll try to work it out later, but for now, I was still trying to work out the problem in this box when he posted, and I want to get something down before too much more is posted. I'd be interested to know what publication this was, since I expect either the question/answer is misstated or the publication is some well-known bunch of quacks.
I will say that the obsession with Pascal's triangle for math that could have been done much more elegantly hurts the OP's credibility badly.
EDIT: Yeah, I agree with CrystalMath. This is just that "voodoo math" (i.e., a variant of the gambler's fallacy) I thought the solution was before I was made to think about manipulating the guesses. The reason the static groups might have worked is that there were N times more permutations where one succeeded than where one failed - but laid out in a row like this, they're equally likely.
(Not to bang on, but it's the difference between "there is one that is" and "this one is.")
Quote: CrystalMathI disagree. The first wizard to see 19 wizards of the same color hat before him will have exactly 50% chance of matching those hats. Each guessing wizard will have a 50% chance of failure.
The binomial distribution doesn't mean anything in this case because it is not a randomly selected group of 20 wizards.
Yep. Basically what I was trying to get at.
Quote: TwirdmanEdit: Hey Bingo have you had any more luck with a power series approach to this problem?
I'm basically stumped. Now that I've seen the "solution," I'm starting to veer back toward the impossible camp.
I realized what a fool's errand my "power tower" approach was - I can't make the function increase fast enough to catch up to its own exponent - so I thought rather it should increase very slowly. A logarithmic increase can make them both diverge, but even an L2 increase makes them both converge. I tried turning it around, to consider groups of groups of wizards at each level, and I'm not ruling it out yet, but I'm not hopeful.
Quote: 24BingoI'm basically stumped. Now that I've seen the "solution," I'm starting to veer back toward the impossible camp.
I realized what a fool's errand my "power tower" approach was - I can't make the function increase fast enough to catch up to its own exponent - so I thought rather it should increase very slowly. A logarithmic increase can make them both diverge, but even an L2 increase makes them both converge. I tried turning it around, to consider groups of groups of wizards at each level, and I'm not ruling it out yet, but I'm not hopeful.
I'm still having trouble with the various proscriptions that have cropped up. I think there have to be inferences made by the wizards in the room, and the only way any one wizard could answer is if 1) They saw all one color hats around them but still did not know what their own might be. 2) they placed themselves in the postulated line 3) another wizard came to stand behind that one wizard. Then, by inferring from the action of the trailing wizard, and that the one wizard was standing between 2 wizards with the same color hat, the one wizard could then state that his hat was that same color, whichever it is.
If there were 2 colors, and the wizards lined up behind the one they thought they were, I don't know how any other could correct any wizard who lined up incorrectly without communicating, so I'm back to all one color of hats.
Quote: kubikulannI may be overlooking something, but it looks like my proposal, which was (correctly) shown false by 24bingo: how do you guarantee that there will be an infinity of responses?
I contend that there will be an infinite number of responses because the probability of a "finite run of n identical hats" goes to one as N (the total number of hats/wizards) goes to infinity. In my solution, the set of values for n are [20*2^i] for all values of i from from 0 to infinity.
Let me suggest a "limit theory" based answer for any single sequence (say, the challenge of finding a sequence of 160 identical hats). If, for or any level desired level of certainty (1 - epsilon), I can compute a delta (some finite number of total hats) such that the probability of finding that sequence in the set of delta hats lies between (1 - epsilon) and 1, that is sufficient to prove that the limiting value of certainty is unity. I believe that to be the case here.
Note that the Wizard's groups give either a single right answer or a chorus of wrong ones - whatever solution you come up with, something similar will have to hold, since the expected number of right answers will always be half the wizards who answer. But you have individual wizards answering for their group, right or wrong, and they're equally likely; you're committing the gambler's fallacy.
Quote: kubikulann(I prsume spoiler caches are unneeded at this stage.)
The first to see the next 19 same hats is certain that his is a different color. Otherwise his predecessor would be the first.
Also, talking of "first" seems to me to imply that they speak successively, not simultaneously. Indeed, if the first run is more than 19, several wizards may think they are the first to see 19. If they speak simultaneously, several must be wrong.
I think we're tripping over the semantics of "first". In this problem, "first" does not, and cannot refer to any form of time ordering. I use it only in the ordinal sense (each wizard has an "index" starting with 1 (the "first" wizard) and continuing to an infinite line of wizards, each indexed by next higher natural number).
Yes, some wizard will be the first (lowest index) to qualify as the spokes-wizard (SW) for each group, but I contend that all wizards will know the identity of every SW at the outset (prior to the moment of simultaneous declaration). All they have to do is examine the lineup prior to their own index.
So I must disagree that the "first" (SW) will know his hat color because otherwise the previous wizard would have appointed himself the (SW). The problem does not permit any form of "waiting to see what the others do". That was the whole point of "on the count of three ..." simultaneity provision.
Unless, of course, I misunderstood your question ...
Quote: CrystalMathI disagree. The first wizard to see 19 wizards of the same color hat before him will have exactly 50% chance of matching those hats. Each guessing wizard will have a 50% chance of failure.
The binomial distribution doesn't mean anything in this case because it is not a randomly selected group of 20 wizards.
I don't have the heart to tell him where he went off the rails here. Does any one else care to?
Quote: dblanch256Quote: CrystalMathI disagree. The first wizard to see 19 wizards of the same color hat before him will have exactly 50% chance of matching those hats. Each guessing wizard will have a 50% chance of failure.
The binomial distribution doesn't mean anything in this case because it is not a randomly selected group of 20 wizards.
I don't have the heart to tell him where he went off the rails here. Does any one else care to?
This isn't about heart. Under the assumption that you are, in fact, making an infinite number of guesses, you still have a non-zero chance of each guess being wrong. No? If so, why is it true that an infinite number of trials, where each trial has a non-zero probability of losing, will nevertheless all win 90% or more of the time? In other words, why do you think that in an infinite number of trials where each trial can lose, that there won't *always* be at least one loser?
Quote: dblanch256I don't have the heart to tell him where he went off the rails here. Does any one else care to?
Go ahead and "tell" him. It'll be hilarious.
Meanwhile, in the real world...
Since each group has a 1-21-k chance of not giving a wrong answer and a 1-k*21-k chance of not giving a right one, each "step" has a (1-21-k)ak chance of not giving a wrong answer and a (1-k*21-k)ak chance of not giving a right one. The chance of getting no wrong answers, therefore, is Π(1-21-k)ak and of no right answers Π(1-k*21-k)ak, and as before, by converting them into sums of logarithms and using the limit convergence test, these are equiconvergent to Σ(ak*21-k) and Σ(ak*k*21-k). So setting ak to 2k/k2 we get that the former is Σ(2/k2) and the latter Σ(2/k). The former converges, and the latter diverges (the fact that it diverges to positive rather than negative infinity is due to a switched sign in the limit convergence trick above; note that all terms in the original series are negative). Adding the floor function doesn't make a difference because the terms differ by at most 2-k (since ak differs at most by 1), and thus the limit convergence test again holds.
In other words, the chance of getting a wrong answer stabilizes, whereas the chance of a right answer being the final one dwindles away as the logarithms blow up to -∞. QED.
Kudos!Quote: 24BingoMeanwhile, in the real world...
[spoiler=EYPHKA!][/spoiler]
I think you understood my objection, but you don't answer it.Quote: dblanch256Yes, some wizard will be the first (lowest index) to qualify as the spokes-wizard (SW) for each group, but I contend that all wizards will know the identity of every SW at the outset (prior to the moment of simultaneous declaration). All they have to do is examine the lineup prior to their own index.
So I must disagree that the "first" (SW) will know his hat color because otherwise the previous wizard would have appointed himself the (SW).
Unless, of course, I misunderstood your question ...
Take the first run of more than 18 same-color hats. Suppose there are 20 (or more). You are the first one. You see 19 after you, so you are supposing you are the first. OR you take into account that you might wear the same color, then your predecessor is the first. How do you decide, unless he spoke before you? With simultaneity, you have no clue.
You are back to your original sin of overestimating yourself and debasing the others. Actually, CrystalMath is right.Quote: dblanch256Quote: CrystalMathI disagree. The first wizard to see 19 wizards of the same color hat before him will have exactly 50% chance of matching those hats. Each guessing wizard will have a 50% chance of failure.
The binomial distribution doesn't mean anything in this case because it is not a randomly selected group of 20 wizards.
I don't have the heart to tell him where he went off the rails here. Does any one else care to?
(Modern science knows reasoning is not in the heart but in the brain -- Sorry, nothing personal, it was just too funny to miss.)
Quote: dblanch256Quote: CrystalMathI disagree. The first wizard to see 19 wizards of the same color hat before him will have exactly 50% chance of matching those hats. Each guessing wizard will have a 50% chance of failure.
The binomial distribution doesn't mean anything in this case because it is not a randomly selected group of 20 wizards.
I don't have the heart to tell him where he went off the rails here. Does any one else care to?
I've spent a few hours trying to convince myself that I'm wrong, but I just can't seem to do it.
Let's assume that the first wizard to see exactly 19 wizards in front of him makes a guess, and he guesses opposite of the 19 wizards ahead of him. He will have precisely 50% chance of getting the answer correct. I've decided it doesn't matter if they are before or after you, since all wizards have perfect vision and can survey the entire line before guessing.
I decided to limit it to seeing exactly 19 in order to eliminate the issue that kubikulann brought up: If you see 19 in front of you, you don't know if the wizard behind you also sees 19 (actually 20) or if the wizard before him sees 21, etc. If this is the case, there is a certainty that one of you guesses wrong, and your failure rate exceeds 50%.
So, please enlighten me; I can take it.
Quote: kubikulann(I prsume spoiler caches are unneeded at this stage.)
Indeed, if the first run is more than 19, several wizards may think they are the first to see 19. If they speak simultaneously, several must be wrong.
I think you are correct about that. Maybe the strategy needs to include "don't speak if you're immediate neighbors (at [n-1] and [n+1]) have the same color hat". Wouldn't that not plug the hole? See example below.
Consider a lower-order concrete example with only four hats sought, followed by 8, then 16 and so forth:
Wizard Index:
.........1.........2.........3.........4.........5
12345678901234567890123456789012345678901234567890
WBWBWBBWWWBWBWBWWBWBBBBBBWWBWBWBWBWWWWWWWWWBWBWBWB...
I claim that not only will wizard[20] know he is the first spokes-wizard for the group [20, 21, 22, 23] but that all of the other wizards (above and below, but not within his "interval") will know it also. Wizards located inside his "interval" (like 21 and 22) would abstain, because their neighbors hats are identical. By the same logic, the second SW would be wizard[35] representing the group [35, 36, 37, 38, 39, 40, 41, 42] and all wizards from 1-34 and from 43 and beyond would know. [Wizards 36-42 would say nothing, because their immediate neighbors both have white hats.]
Nice catch, by the way!
Wizard Index:
.........1.........2.........3.........4.........5
12345678901234567890123456789012345678901234567890
WBWBWBBWWWBWBWBWBWWBBBBBBWWBWBWBWBWWWWWWWWWBWBWBWB...
According to the new qualifications, wizard[19] will try to speak, and wizard[20] will try to speak. One will answer incorrectly.
Assuming we can always determine which wizard is the spokes-wizard, it won't help us, because they will still have a 50% chance at failure.
Anyway, 24Bingo's solution solved it, didn't it?
Quote: dblanch256
The few members either who insisted it "has no solution" or that the problem statement was "mal-formed" should know that I found it in respected Scientific Journal that is not known for making casual mistakes. Further, my solution (below) is my own, not the result of reading any published answer. Hence I'd appreciate a "peer review" for any of you willing to offer an opinion. I hope it was fun for at least some of you. If not, take heart. They're building taller and taller bridges every day ...
dblanch, can you please name your source (author, title, issue, year). Respected Scientific Journal doesn't tell us anything. After all this back and forth, I really need closure - your solution doesn't work as others have pointed out. You may have misinterpreted something in the original problem.
Quote: Canyonerodblanch, can you please name your source (author, title, issue, year). Respected Scientific Journal doesn't tell us anything. After all this back and forth, I really need closure - your solution doesn't work as others have pointed out. You may have misinterpreted something in the original problem.
I hope it's not the Rancocas Valley Journal of Applied Mathematics.
Quote: CrystalMathQuote: dblanch256Quote: CrystalMathI disagree. The first wizard to see 19 wizards of the same color hat before him will have exactly 50% chance of matching those hats. Each guessing wizard will have a 50% chance of failure.
The binomial distribution doesn't mean anything in this case because it is not a randomly selected group of 20 wizards.
I don't have the heart to tell him where he went off the rails here. Does any one else care to?
I've spent a few hours trying to convince myself that I'm wrong, but I just can't seem to do it.
Let's assume that the first wizard to see exactly 19 wizards in front of him makes a guess, and he guesses opposite of the 19 wizards ahead of him. He will have precisely 50% chance of getting the answer correct. I've decided it doesn't matter if they are before or after you, since all wizards have perfect vision and can survey the entire line before guessing.
I decided to limit it to seeing exactly 19 in order to eliminate the issue that kubulikann brought up: If you see 19 in front of you, you don't know if the wizard behind you also sees 19 (actually 20) or if the wizard before him sees 21, etc. If this is the case, there is a certainty that one of you guesses wrong, and your failure rate exceeds 50%.
So, please enlighten me; I can take it.
Kubikulann did indeed find a "crack" in my foundation, which I think I fixed with a slight strategy change. Sorry for the confusion.
Do you feel you understand the simpler example I posted earlier (with only four "un-ordered" wizards in a room)? The point I was trying to make there is that there are more ways for a random process to generate WBBB (or any permutation of that) than there are ways to produce WWWW. Therefore, all four wizards should use the strategy of (a) only speaking when the see all identical hats, and (b) when they do, they should declare the opposite color for themselves.
Just for a change of pace, let's say you have ten pennies, take the day off from work, and perform the following test one million times:
You throw all ten up in the air but only record the rounds which produce at least nine heads. The odds of that happening are 11/1024, or about 10,742 times that day. The odds of getting exactly nine heads are 10/1024 (about 9,766 times per day) whereas the odds of ten heads are 1/1024 (about 976 per day).
If each coin could "look" at the others and shout "I'm a tail!" when, and only when it saw nine other heads, it would be right 11 times for each time it was wrong. Further, on those very few rounds when it was wrong, all the other coins would be shouting the same wrong thing, and that round would be busted.
Good God, you've got me discussing "talking coins". What's next? A singing dancing mouse with its own amusement park???
No. 10.Quote: dblanch256The odds of getting exactly nine heads are 10/1024 (about 9,766 times per day) whereas the odds of ten heads are 1/1024 (about 976 per day).
If each coin could "look" at the others and shout "I'm a tail!" when, and only when it saw nine other heads, it would be right 11 times for each time it was wrong.
If you permit my telling, you are talking to yourself, since the 1 to N ratio was understood by everybody here, even before your "simpler example". It's the group sizing that is important.Quote: dblanch256Good God, you've got me discussing "talking coins". What's next? A singing dancing mouse with its own amusement park???
Quote: dblanch256
If each coin could "look" at the others and shout "I'm a tail!" when, and only when it saw nine other heads, it would be right 11 times for each time it was wrong. Further, on those very few rounds when it was wrong, all the other coins would be shouting the same wrong thing, and that round would be busted.
If this coin walks around all day until it finds a group of 9 heads, it will not change how the coin was flipped in the first place.
Quote: dblanch256Just for a change of pace, let's say you have ten pennies, take the day off from work, and perform the following test one million times:
You throw all ten up in the air but only record the rounds which produce at least nine heads. The odds of that happening are 11/1024, or about 10,742 times that day. The odds of getting exactly nine heads are 10/1024 (about 9,766 times per day) whereas the odds of ten heads are 1/1024 (about 976 per day).
If each coin could "look" at the others and shout "I'm a tail!" when, and only when it saw nine other heads, it would be right 11 times for each time it was wrong. Further, on those very few rounds when it was wrong, all the other coins would be shouting the same wrong thing, and that round would be busted.
Good God, you've got me discussing "talking coins". What's next? A singing dancing mouse with its own amusement park???
You can effectively discard all groups in which the wizards fail to answer, so you've boiled it down to a number of groups each guessing wrong with a 1/11 chance. That's fine for a finite number of guesses, but for an infinite number of guesses, any non-zero chance of being wrong means that the collective probability that at least one of them will be wrong (over all infinite guesses) will ultimately approach unity. It doesn't matter how clever the guesses are in the meanwhile.
Quote: kubikulannYou are back to your original sin of overestimating yourself and debasing the others. Actually, CrystalMath is right.Quote: dblanch256Quote: CrystalMathI disagree. The first wizard to see 19 wizards of the same color hat before him will have exactly 50% chance of matching those hats. Each guessing wizard will have a 50% chance of failure.
The binomial distribution doesn't mean anything in this case because it is not a randomly selected group of 20 wizards.
I don't have the heart to tell him where he went off the rails here. Does any one else care to?
(Modern science knows reasoning is not in the heart but in the brain -- Sorry, nothing personal, it was just too funny to miss.)
Weren't we all born with Original Sin, at least according to some?
OK, everybody, please listen up. I'd like to take a poll on this problem, but I don't know if it can be done "after the fact" in this thread. If not, perhaps management will permit me to start a companion thread ... if only for said purpose of poll. I'll wait for at least a few votes before I reveal all.
Quote: Canyonerodblanch, can you please name your source (author, title, issue, year). Respected Scientific Journal doesn't tell us anything. After all this back and forth, I really need closure - your solution doesn't work as others have pointed out. You may have misinterpreted something in the original problem.
That's an entirely reasonable request. I sense the cement hardening and fewer people changing their minds, so I agree. You are entitled to closure.
It would be a terrible mistake for me to have misquoted the problem, so just to put that possibility to bed, here is the direct "cut and paste" version:
I know an infinite number of wizards. I told them to prepare for the following contest and see if they can derive a method that guarantees a winning probability of at least 90 percent. Each wizard will be assigned a random hat, either black or white, with a probability of 1/2 for each choice. The wizards can see everyone's hat except for their own. At the count of three, each wizard must either guess the color of his or her hat or abstain from guessing. The wizards collectively win if, among them, there are an infinite number of correct guesses and zero wrong guesses.
Fair question, but I hope this puts an end to the speculation that at least the problem statement was correct. Like I said, I think a poll would be advisable.
I just don't know if its possible without starting a new topic.
Quote: dblanch256Do you feel you understand the simpler example I posted earlier (with only four "un-ordered" wizards in a room)? The point I was trying to make there is that there are more ways for a random process to generate WBBB (or any permutation of that) than there are ways to produce WWWW. Therefore, all four wizards should use the strategy of (a) only speaking when the see all identical hats, and (b) when they do, they should declare the opposite color for themselves.
The key words there are "or any permutation." WBBB is exactly as likely as WWWW when you discard all other permutations, as your solution does. The only way around that is that the groups be irrespective of the hats.
Quote: dblanch256That's an entirely reasonable request. I sense the cement hardening and fewer people changing their minds, so I agree. You are entitled to closure.
It would be a terrible mistake for me to have misquoted the problem, so just to put that possibility to bed, here is the direct "cut and paste" version:
I know an infinite number of wizards. I told them to prepare for the following contest and see if they can derive a method that guarantees a winning probability of at least 90 percent. Each wizard will be assigned a random hat, either black or white, with a probability of 1/2 for each choice. The wizards can see everyone's hat except for their own. At the count of three, each wizard must either guess the color of his or her hat or abstain from guessing. The wizards collectively win if, among them, there are an infinite number of correct guesses and zero wrong guesses.
Fair question, but I hope this puts an end to the speculation that at least the problem statement was correct. Like I said, I think a poll would be advisable.
I just don't know if its possible without starting a new topic.
OK, forget the poll. I'm losing faith in the "linear solution" I ventured, based on valid complaints from several key respondents
Let me suggest an alternative:
Before the hats are distributed, the wizards partition themselves into an infinite number of finite groups S_1, S_2, S_3, etc. Each of these groups, upon receiving their hats, will execute a strategy based only on the hats within their own group. Group S_i succeeds if it produces at least one correct guess and zero wrong guesses. If group S_i succeeds with probability p_i, then the collective probability of success is at least p_1 * p_2 * p_3 * ...
If we set each p_i to be greater than exp(-C*2^(-i)), then the infinite product is greater than exp(-C). By choosing C, this product can be made greater than 0.99. It suffices to show that for any p<1, some finite committee can succeed with probability > p.
Consider a size n=2^k-1 group, consisting of wizards numbered 1, 2, ..., n. Some subset of these wizards will receive black hats; let x be the "exclusive or" (XOR) of the wizards of this subset. Because n is of the form 2^k-1, x will be an integer between 0 and n.
The group does not know what x will be, but they can collectively guess. Rather than trying to guess the exact value, they just guess a value that x is not. Before the hats are even distributed, they randomly choose some y in the range {0, 1, ..., n} and simply guess that x != y. Obviously, their guess will be correct with probability n/(n+1). If they are correct, they can individually guess/abstain in a way as to ensure that they will succeed. The strategy is that each wizard assumes the collective guess is correct, looks at the other (n-1) hats, and determines whether he can rule out a given color for his own hat by computing the XOR value. If he can, naturally he guesses the other.
All that remains to be shown is that at least one wizard will make a guess when x != y. To see this, define x_i to be what the total XOR would be if wizard<i>'s hat color were flipped. Clearly, x_i != x_j whenever i != j, implying that {x_1, x_2, ..., x_n} is a permutation of {0, 1, ..., n} - {x}. So as long as x != y, there exists some i such that x_i = y, meaning that wizard<i> can rule out one of two colors, as required.
Where did you find this problem, and did they provide a solution? (Because clearly you didn't come here with theirs.) I still think I'm right as well, but I'm willing to be proven wrong. It certainly wouldn't be the first time.
(MathExtremist: The trick is that while the expected number of wrong guesses is going to be infinite, that doesn't mean there can't be a finite probability of no wrong guesses - think of it like the St. Petersburg game.)
Quote: 24BingoEDIT: No. Sorry. That solution is wrong because while they'll only guess wrong if they've happened upon the exact number, there will only be a right guess if the actual number happens to be exactly one bit away. This means there will be n times as many right guesses as wrong ones, which just makes it a needlessly complicated version of the strategy we've been looking at all along, of only the wizards who see all their groupmates have the same color hat guessing, and just like before, increasing by powers of two isn't going to produce infinite right guesses. (Also, it should be powers of two with indices starting at zero, not less one with indices starting at 1; you've biased it slightly toward odd numbers.)
Where did you find this problem, and did they provide a solution? (Because clearly you didn't come here with theirs.) I still think I'm right, but I'm willing to be proven wrong. It certainly wouldn't be the first time.
(MathExtremist: The trick is that while the expected number of wrong guesses is going to be infinite, that doesn't mean there can't be a finite probability of no wrong guesses - think of it like the St. Petersburg game.)
Listen to ME ... he speaks the truth (unless he's from that tribe that only tells lies, wait, which prison guard is he? I forgot.)
Quote: kubikulannKudos!Quote: 24BingoMeanwhile, in the real world...
[spoiler=EYPHKA!][/spoiler]
"Kudos!" strikes me as a bit verbose. Unless you're not into the whole "brevity thing" can I make a motion that we all agree on just "K!" in the future? Not only would it save considerable keyboard wear and tear, but also every time it is used, anyone who is anyone would think of you! ;)
[Sorry, just too funny. I couldn't resist.]
Start with a target group of wizards of size 40. The first group will be the first group that is bounded by BBBW on one end and WBBB on the other end and contains 40 wizards between the bounds. The 40 wizards must be all W, with the exception of up to 2 B. Not all wizards in the group will know they are part of the group, but all wizards coming after the group will know that that group has been spoken for.
Each wizard will assume that he is part of the group if he is surrounded by 39 W and up to 1 B and those wizards are bounded by BBBW and WBBB (so, all together, there will be 42 W wizards with the exception of 1 or 2 B wizards. Any wizard who sees exactly 1 B in the group will guess that he is B.
The options are:
case 1: BBBW WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW WBBB
case 2: BBBW WWWWWWWWWWWWBWWWWWWWWWWWWWWWWWWWWWWWWWWW WBBB
case 3: BBBW WWWWWBWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWWW WBBB
case 1: all wizards will abstain
case 2: all of the W wizards will guess incorrectly and the B wizard will abstain
case 3: the B wizards will guess correctly and the W wizards will abstain (the W wizards won't even know they are in the group, because they see 2 B to start with)
In cases 2 and 3, the B wizards can be located anywhere inside the 40 inner wizards, so we need to calculate the number of ways they can be ordered (or look at Pascals Triangle).
case 1: 1
case 2: 40
case 3: combin(40,2) = 780
p(correct guess) = 780/(780 + 40 + 1) = 95.0061%
Then, do this for group sizes 80, 160, 320...40*2^n. This will converge to 90.34% success rate.
