Aleph-Naught Wizards
January 12th, 2014 at 3:30:08 PM
permalink
I 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?
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?
The key can be found along the edge and adjacent values of Pascal's triangle.
David C Blanchard
January 12th, 2014 at 4:37:10 PM
permalink
The wizards agree on some common pointing strategy, such as every wizard finds two nearby wizards with the same hat, and points at both of them. Any wizard being pointed out can then announce the colour of their hat by looking at where the pointer's other hand is pointing. With an infinite number of wizards, it is not hard to see there will be an infinite number of wizards being pointed at, guessing correctly. And 0 wrong guesses.
I like Pascal's triangle but don't see how my solution is related.
I like Pascal's triangle but don't see how my solution is related.
Wisdom is the quality that keeps you out of situations where you would otherwise need it
January 12th, 2014 at 5:33:21 PM
permalink
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?
Here are two trivial solutions given the literal statement of the problem:
At the count of 1, each wizard takes off their hat and looks at it.
At the count of 2, each wizard replaces their hat, just because they're wizards and like wearing hats.
At the count of 3, each wizard announces their own hat color.
At the count of 1, each wizard takes a selfie with their smartphone.
At the count of 2 they look at it.
At the count of 3 they announce their own hat color.
Here's one that's probably closer to what you intended, assuming the wizards are perfectly truthful (and perfect logicians, etc, etc.):
At the count of 1, the wizards pair up. For convenience they may move to stand adjacent to their partner wizard.
At the count of 2, each wizard in the pair holds up 1 finger if their partner's hat is white, and does not hold up anything if their partner's hat is black.
At the count of 3, every wizard correctly announces his or her own hat color.
This has 100% chance of success
At the count of 2, each wizard in the pair holds up 1 finger if their partner's hat is white, and does not hold up anything if their partner's hat is black.
At the count of 3, every wizard correctly announces his or her own hat color.
This has 100% chance of success
"In my own case, when it seemed to me after a long illness that death was close at hand, I found no little solace in playing constantly at dice."
-- Girolamo Cardano, 1563
January 13th, 2014 at 6:42:29 AM
permalink
Quote: dwheatleyThe wizards agree on some common pointing strategy, such as every wizard finds two nearby wizards with the same hat, and points at both of them. Any wizard being pointed out can then announce the colour of their hat by looking at where the pointer's other hand is pointing. With an infinite number of wizards, it is not hard to see there will be an infinite number of wizards being pointed at, guessing correctly. And 0 wrong guesses.
I like Pascal's triangle but don't see how my solution is related.
The wizards consider pointing (and for that matter) any other gestures to be rude. They must use only their perfect vision and enormous minds to decide their answers.
At the risk of being overly-enumerative, the wizards may not (collectively or individually):
(1) Remove their hats and look at them.
(2) Point at other wizards hats or body parts.
(3) Use any form of pantomime.
(4) Use their wPhones to collaborate.
(5) Melvin each other for giggles.
(6) Need I go on?
David C Blanchard
January 13th, 2014 at 6:44:42 AM
permalink
Quote: MathExtremistQuote: 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?
Here are two trivial solutions given the literal statement of the problem:
At the count of 1, each wizard takes off their hat and looks at it.
At the count of 2, each wizard replaces their hat, just because they're wizards and like wearing hats.
At the count of 3, each wizard announces their own hat color.
At the count of 1, each wizard takes a selfie with their smartphone.
At the count of 2 they look at it.
At the count of 3 they announce their own hat color.
Here's one that's probably closer to what you intended, assuming the wizards are perfectly truthful (and perfect logicians, etc, etc.):At the count of 1, the wizards pair up. For convenience they may move to stand adjacent to their partner wizard.
At the count of 2, each wizard in the pair holds up 1 finger if their partner's hat is white, and does not hold up anything if their partner's hat is black.
At the count of 3, every wizard correctly announces his or her own hat color.
This has 100% chance of success
Funny! But sorry, no fingers. Please see reply above to other "would be" finger pointer.
David C Blanchard
January 13th, 2014 at 7:08:59 AM
permalink
The Wizards define a certain order. It doesn't matter how, but every wizard must know his place. No matter what, only one wizard will hazard a guess. If one hazards a guess then all others will abstain. Here is the strategy:
- If the first Wizard sees every other wizard wearing the same color hat then he will guess that same color. He will have a 50% chance of being right.
- If the first Wizard abstains, then the second wizard must know the first one sees a mixture of colors. If the second wizard sees all the same colors (not counting the first wizard's hat) then he will know his hat will be the opposite color, and will guest that. Otherwise, the second wizard will abstain.
- If the first two wizards abstain, then the third wizard must know the second one sees a mixture of colors. If the third wizard sees all the same colors (not counting the first two hats) then he will know his hat will be the opposite color, and will guest that. Otherwise, the third wizard will abstain.
- Keep repeating this process until somebody hazards a guess, which must be right. It must eventually lead to a guess. If it gets down to the last two wizards then second to last one will guess the opposite color of the last one, and must be right.
The only chance of failure is if every hat is the same color and even then there is a 50% chance of being right.
This is similar to the "cheating husbands" riddle.
Hopefully that answer conforms to the rules. I'm worried it violates the "count of three" rule but maybe the wizards are fast.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
January 13th, 2014 at 7:22:47 AM
permalink
Am I missing something?
According to the rules, every wizard can abstain, thus using zero wrong answers.
I invented a few casino games. Info:
http://www.DaveMillerGaming.com/ —————————————————————————————————————
Superstitions are silly, childish, irrational rituals, born out of fear of the unknown. But how much does it cost to knock on wood? 😁
January 13th, 2014 at 8:00:26 AM
permalink
Quote: dblanch256Quote: dwheatleyThe wizards agree on some common pointing strategy, such as every wizard finds two nearby wizards with the same hat, and points at both of them. Any wizard being pointed out can then announce the colour of their hat by looking at where the pointer's other hand is pointing. With an infinite number of wizards, it is not hard to see there will be an infinite number of wizards being pointed at, guessing correctly. And 0 wrong guesses.
I like Pascal's triangle but don't see how my solution is related.
The wizards consider pointing (and for that matter) any other gestures to be rude. They must use only their perfect vision and enormous minds to decide their answers.
At the risk of being overly-enumerative, the wizards may not (collectively or individually):
(1) Remove their hats and look at them.
(2) Point at other wizards hats or body parts.
(3) Use any form of pantomime.
(4) Use their wPhones to collaborate.
(5) Melvin each other for giggles.
(6) Need I go on?
I interpret those rules (plus the original statement) to mean that the Wizard's can't communicate at all, even through other Wizards' guesses. That means whatever ordering or arrangement the wizards are in, they can't use it to sequentially perform their guesses. All guesses are simultaneous. Is that right?
Edit: can't communicate after the counting has started; the OP clearly says they need to derive a method/strategy to play the game so they're obviously talking beforehand.
"In my own case, when it seemed to me after a long illness that death was close at hand, I found no little solace in playing constantly at dice."
-- Girolamo Cardano, 1563
January 13th, 2014 at 8:04:35 AM
permalink
Quote: DJTeddyBearAm I missing something?
According to the rules, every wizard can abstain, thus using zero wrong answers.
For the part of the problem which mandates "there are an infinite number of correct guesses and zero incorrect guesses" I think you have covered the second part, but not the first. I don't see how you can have an infinite number of correct guesses if no one is guessing. Sorry.
David C Blanchard
January 13th, 2014 at 8:07:34 AM
permalink
Quote: MathExtremistQuote: dblanch256Quote: dwheatleyThe wizards agree on some common pointing strategy, such as every wizard finds two nearby wizards with the same hat, and points at both of them. Any wizard being pointed out can then announce the colour of their hat by looking at where the pointer's other hand is pointing. With an infinite number of wizards, it is not hard to see there will be an infinite number of wizards being pointed at, guessing correctly. And 0 wrong guesses.
I like Pascal's triangle but don't see how my solution is related.
The wizards consider pointing (and for that matter) any other gestures to be rude. They must use only their perfect vision and enormous minds to decide their answers.
At the risk of being overly-enumerative, the wizards may not (collectively or individually):
(1) Remove their hats and look at them.
(2) Point at other wizards hats or body parts.
(3) Use any form of pantomime.
(4) Use their wPhones to collaborate.
(5) Melvin each other for giggles.
(6) Need I go on?
I interpret those rules (plus the original statement) to mean that the Wizard's can't communicate at all, even through other Wizards' guesses. That means whatever ordering or arrangement the wizards are in, they can't use it to sequentially perform their guesses. All guesses are simultaneous. Is that right?
Yes that is right.
David C Blanchard
January 13th, 2014 at 8:25:56 AM
permalink
Quote: Wizard
The Wizards define a certain order. It doesn't matter how, but every wizard must know his place. No matter what, only one wizard will hazard a guess. If one hazards a guess then all others will abstain. Here is the strategy:
- If the first Wizard sees every other wizard wearing the same color hat then he will guess that same color. He will have a 50% chance of being right.
- If the first Wizard abstains, then the second wizard must know the first one sees a mixture of colors. If the second wizard sees all the same colors (not counting the first wizard's hat) then he will know his hat will be the opposite color, and will guest that. Otherwise, the second wizard will abstain.
- If the first two wizards abstain, then the third wizard must know the second one sees a mixture of colors. If the third wizard sees all the same colors (not counting the first two hats) then he will know his hat will be the opposite color, and will guest that. Otherwise, the third wizard will abstain.
- Keep repeating this process until somebody hazards a guess, which must be right. It must eventually lead to a guess. If it gets down to the last two wizards then second to last one will guess the opposite color of the last one, and must be right.
The only chance of failure is if every hat is the same color and even then there is a 50% chance of being right.
This is similar to the "cheating husbands" riddle.
Hopefully that answer conforms to the rules. I'm worried it violates the "count of three" rule but maybe the wizards are fast.
I believe that the wizards are, in fact, very fast (if only by Darwinian selection). Let's face it, the market for "slow wizards" has always been tight and most of them do their best to omit this feature in their resumes. But fast isn't instantaneous.
The above approach unfortunately does violate the "count of three" clause whose sole purpose is to enforce simultaneity of utterances (and non-utterances).
I'm not familiar with the "cheating husbands" riddle, but you've piqued my curiosity. Is it presented in one of these threads?
David C Blanchard
January 13th, 2014 at 8:28:16 AM
permalink
In 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.
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.
"In my own case, when it seemed to me after a long illness that death was close at hand, I found no little solace in playing constantly at dice."
-- Girolamo Cardano, 1563
January 13th, 2014 at 9:18:47 AM
permalink
Quote: dblanch256I'm not familiar with the "cheating husbands" riddle, but you've piqued my curiosity. Is it presented in one of these threads?
It is similar to your riddle, but only 40 wizards, and they must tender a guess or abstain one at a time. I'll try to remember to tell it after we work through this one.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
January 13th, 2014 at 10:03:05 AM
permalink
Quote: WizardIt is similar to your riddle, but only 40 wizards, and they must tender a guess or abstain one at a time. I'll try to remember to tell it after we work through this one.
Yes, doing a sequential guess process means subsequent wizards can gain information from the prior wizards' guesses (or lack thereof). The twist here is none of that typical induction logic works because there is no communication possible, even implicitly, when everyone needs to guess at precisely the same time. There's another puzzle that involves being the first to guess, and that has to do with the winner reasoning that the other participant's haven't guessed yet and therefore aren't sure. But I don't think I've seen an induction problem exactly with this statement before.
"In my own case, when it seemed to me after a long illness that death was close at hand, I found no little solace in playing constantly at dice."
-- Girolamo Cardano, 1563
January 13th, 2014 at 10:03:48 AM
permalink
I'm sure this isn't optimal, but will get the probability of success over 95%. It is based on ME's solution.
1. Create 5*(2^1000/2002) groups of 1000 wizards each. Everyone else is to abstain no matter what.
2. Instruct each member that if he sees all hats of the same color to guess the opposite way.
3. Here are the probabilities for any given group:
Correct guess = 2*1000/2^1000
Incorrect guess (everyone making it) = 2/2^1000
Probability group is correct given it guesses = 2000/2002 = 1000/1001.
Probability guess tendered = 2002/2^1000
4. The expected number of guesses tendered will be 5.
5. An approximation to the number of incorrect guesses is 5*(1/1001) = 5/1001 = 0.50%.
6. An approximation to the probability of no guesses is exp(-5) = 0.67%.
7. Total probability of failure = 0.50% + 0.67% = 1.17%.
p.s. ME, please put guesses in spoiler tags.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
January 13th, 2014 at 10:33:03 AM
permalink
It seems to me that if you don't tender any guesses, then you fail the challenge, because there are not an infinite number of correct guesses. So, if a strategy results in >10% chance of making no guesses, then this strategy fails.
I heart Crystal Math.
January 13th, 2014 at 10:48:26 AM
permalink
Quote: Wizard
I'm sure this isn't optimal, but will get the probability of success over 95%. It is based on ME's solution.
1. Create 5*(2^1000/2002) groups of 1000 wizards each. Everyone else is to abstain no matter what.
2. Instruct each member that if he sees all hats of the same color to guess the opposite way.
3. Here are the probabilities for any given group:
Correct guess = 2*1000/2^1000
Incorrect guess (everyone making it) = 2/2^1000
Probability group is correct given it guesses = 2000/2002 = 1000/1001.
Probability guess tendered = 2002/2^1000
4. The expected number of guesses tendered will be 5.
5. An approximation to the number of incorrect guesses is 5*(1/1001) = 5/1001 = 0.50%.
6. An approximation to the probability of no guesses is exp(-5) = 0.67%.
7. Total probability of failure = 0.50% + 0.67% = 1.17%.
p.s. ME, please put guesses in spoiler tags.
Wow. OK, hmmm. Intriguing, but doesn't Step 1 run afoul of the there are an infinite number of correct guesses dictum?
Even 'tho there's a "whole lotta wizard goin' on" here, your "<spoiler> groups of <spoiler> wizards each" is finite, from which I don't see how an infinite number of guesses (let alone correct guesses) could result.
[MS (if I may call you MS): Please remind me to ask my Bovada question later ... I love their service. I just need somebody to clarify why they do "a certain thing".]
David C Blanchard
January 13th, 2014 at 10:57:34 AM
permalink
Hey, is this still unsolved? Yay!
They form a line:
1. One wizard just stands there
2. The second wizard stands next to the first
3. If the third wizard sees only identical colors in the line, he stands on either side, if they see different colors they stand between the different color hats.
4. Repeat infinitely.
This way, a line forms that is perfectly separated by color. Now, if a wizard sees the same color on their left AND right, they name that color. The two wizards that see different colors on their left and right abstain.
And btw that works 100% of the time.
They form a line:
1. One wizard just stands there
2. The second wizard stands next to the first
3. If the third wizard sees only identical colors in the line, he stands on either side, if they see different colors they stand between the different color hats.
4. Repeat infinitely.
This way, a line forms that is perfectly separated by color. Now, if a wizard sees the same color on their left AND right, they name that color. The two wizards that see different colors on their left and right abstain.
And btw that works 100% of the time.
January 13th, 2014 at 11:19:57 AM
permalink
Quote: CanyoneroHey, is this still unsolved? Yay!
They form a line:
1. One wizard just stands there
2. The second wizard stands next to the first
3. If the third wizard sees only identical colors in the line, he stands on either side, if they see different colors they stand between the different color hats.
4. Repeat infinitely.
This way, a line forms that is perfectly separated by color. Now, if a wizard sees the same color on their left AND right, they name that color. The two wizards that see different colors on their left and right abstain.
And btw that works 100% of the time.
It does, but it's using body language to communicate, and I thought that wasn't allowed. If it is, you can also get there by using any of the pointing techniques described earlier. I think the intent of the problem is that the infinite wizards don't have enough time to do something clever like arrange themselves in an order (or point at each other) before they have to announce or abstain. They need to have the strategy figured out, but they only get their hats a few seconds before they have to announce what it is.
Is that right?
"In my own case, when it seemed to me after a long illness that death was close at hand, I found no little solace in playing constantly at dice."
-- Girolamo Cardano, 1563
January 13th, 2014 at 11:27:06 AM
permalink
Quote: MathExtremist
It does, but it's using body language to communicate, and I thought that wasn't allowed. If it is, you can also get there by using any of the pointing techniques described earlier. I think the intent of the problem is that the infinite wizards don't have enough time to do something clever like arrange themselves in an order (or point at each other) before they have to announce or abstain. They need to have the strategy figured out, but they only get their hats a few seconds before they have to announce what it is.
Is that right?
I maintain that there is no communication involved in my solution. The wizards just all think of the same strategy (being the clever wizards that they are; and this is neccessary in any solution), but at no point is any information shared, what they need they see with their own two eyes.
January 13th, 2014 at 11:27:31 AM
permalink
Dear ME:
You are getting dangerously close to a solution, although I think your first group (N=5) might sink you.
Please hide your work with something like:
<open bracket>spoiler=Uh huh. Uh huh. Who da man?<close bracket>Your work<open bracket<close bracket>/spoiler<close bracket>
to give others a chance to catch up.
-- Dave
You are getting dangerously close to a solution, although I think your first group (N=5) might sink you.
Please hide your work with something like:
<open bracket>spoiler=Uh huh. Uh huh. Who da man?<close bracket>Your work<open bracket<close bracket>/spoiler<close bracket>
to give others a chance to catch up.
-- Dave
David C Blanchard
January 13th, 2014 at 11:33:34 AM
permalink
<post deleted>
BTW, who's the "star thief"?
I had a nice 5-star rating on my Wizard Bait topic and some douche balanced it off with a zero.
Tournament director!!!
BTW, who's the "star thief"?
I had a nice 5-star rating on my Wizard Bait topic and some douche balanced it off with a zero.
Tournament director!!!
David C Blanchard
January 13th, 2014 at 11:35:58 AM
permalink
Quote: CanyoneroI maintain that there is no communication involved in my solution. The wizards just all think of the same strategy (being the clever wizards that they are; and this is neccessary in any solution), but at no point is any information shared, what they need they see with their own two eyes.
ME is correct when he said "it's using body language to communicate, and I thought that wasn't allowed". Sorry.
David C Blanchard
January 13th, 2014 at 12:02:24 PM
permalink
Absent some sort of communication, I don't see any way for any Wizard to deduce the color of his own hat, which would leave no solution.
Even if you did decide, before the contest, to arrange yourselves in groups of n (or n^m) wizards, simply observing the other hats in the group doesn't give you any information about your own hat. Each hat is an independent event, so if all n^m-1 other wizards have black hats, you still have a 50/50 chance of either color.
Further, if wizards who tender guesses have anything < 100% of picking correctly, and there are an infinite number of guesses, then you must tender at least 1 incorrect guess, seeing as how you have an infinite number of chances to fail.
Even if you did decide, before the contest, to arrange yourselves in groups of n (or n^m) wizards, simply observing the other hats in the group doesn't give you any information about your own hat. Each hat is an independent event, so if all n^m-1 other wizards have black hats, you still have a 50/50 chance of either color.
Further, if wizards who tender guesses have anything < 100% of picking correctly, and there are an infinite number of guesses, then you must tender at least 1 incorrect guess, seeing as how you have an infinite number of chances to fail.
I heart Crystal Math.
January 13th, 2014 at 12:35:27 PM
permalink
I changed my mind: CrystalMath put into words what was bugging me. There are ways to get a finite set of wizards to have a large percentage chance of winning over a finite number of guesses, but I don't think it's possible with an infinite number of guesses unless (as CM said) the probability of each guess being right is actually 1. Regardless of how many wizards don't guess at all, if any wizard's guess has a non-zero chance p of being wrong, and there are an infinite number of those guesses (per the problem statement), then it is guaranteed that at least one guess will be wrong: 1-(1-p)^infinity = 1 for all 1 >= p > 0.
"In my own case, when it seemed to me after a long illness that death was close at hand, I found no little solace in playing constantly at dice."
-- Girolamo Cardano, 1563
January 13th, 2014 at 3:25:21 PM
permalink
Quote: MathExtremistI changed my mind: CrystalMath put into words what was bugging me. There are ways to get a finite set of wizards to have a large percentage chance of winning over a finite number of guesses, but I don't think it's possible with an infinite number of guesses unless (as CM said) the probability of each guess being right is actually 1. Regardless of how many wizards don't guess at all, if any wizard's guess has a non-zero chance p of being wrong, and there are an infinite number of those guesses (per the problem statement), then it is guaranteed that at least one guess will be wrong: 1-(1-p)^infinity = 1 for all 1 >= p > 0.
No, no ... say it ain't so Joe! You were so close--and you have been consistently brilliant with so many other problems! Heck, it took me three days to crack this bastard the first time I saw it. It's only been on this site for a few hours, so please keep the baby, Faith. Wait, that should have read ... oh well.
You say "If any wizard's guess has a non-zero chance p of being wrong, and there are an infinite number of those guesses, then it is guaranteed that at least one guess will be wrong."
I'd agree with the above iff every guessing wizard had the same finite chance p of being wrong, but must that be so? Why can't the infinite guessing wizards
have respective probabilities of [p1, p2, p3 ...] for example?
Please understand that I hold you in the highest regard, (regardless). You are one of a very select group here who have already impressed the crap out of me. Not even an Aleph Naught of wizards can change that!
-- Dave
David C Blanchard
January 13th, 2014 at 3:32:52 PM
permalink
Can the wizards be organized, moved, or grouped before the guess?
Can I assume every wizard can see every other wizard?
Can I assume every wizard can see every other wizard?
I was wondering if this related to seeing an odd/even thing, but as an infinite number is neither odd nor even (or it's both) that wouldn't work.
Given the clues, it would strike me that an infinite set of groups are created, with some rule based on the grouping that a single wizard in each group makes a guess.
Certainly the infinite number (aleph-0) clue seems to both make and break this puzzle.
Given the clues, it would strike me that an infinite set of groups are created, with some rule based on the grouping that a single wizard in each group makes a guess.
Certainly the infinite number (aleph-0) clue seems to both make and break this puzzle.
"Then you can admire the real gambler, who has neither eaten, slept, thought nor lived, he has so smarted under the scourge of his martingale, so suffered on the rack of his desire for a coup at trente-et-quarante" - Honore de Balzac, 1829
January 13th, 2014 at 5:18:43 PM
permalink
Quote: dblanch256You say "If any wizard's guess has a non-zero chance p of being wrong, and there are an infinite number of those guesses, then it is guaranteed that at least one guess will be wrong."
I'd agree with the above iff every guessing wizard had the same finite chance p of being wrong, but must that be so? Why can't the infinite guessing wizards
have respective probabilities of [p1, p2, p3 ...] for example?
Because even if p1 != p2 != p3, and even if some of those guesses are never wrong, as long as some (smaller) infinite number of guesses are sometimes wrong the problem is still there. A finite number of wrong guesses would work, but I don't see how it's possible to guarantee only a finite possible of wrong guesses if the wizards need to hazard an infinite number of guesses overall.
"In my own case, when it seemed to me after a long illness that death was close at hand, I found no little solace in playing constantly at dice."
-- Girolamo Cardano, 1563
January 13th, 2014 at 5:34:38 PM
permalink
I'm still waiting to hear if my second solution violates the infinite right answers rule. I could always break down my method into infinitely many subsets, but some of them would be wrong. Just any one subset would have a probability of success over 95%.
I'm sure this isn't optimal, but will get the probability of success over 95%. It is based on ME's solution.
1. Create 5*(2^1000/2002) groups of 1000 wizards each. Everyone else is to abstain no matter what.
2. Instruct each member that if he sees all hats of the same color to guess the opposite way.
3. Here are the probabilities for any given group:
Correct guess = 2*1000/2^1000
Incorrect guess (everyone making it) = 2/2^1000
Probability group is correct given it guesses = 2000/2002 = 1000/1001.
Probability guess tendered = 2002/2^1000
4. The expected number of guesses tendered will be 5.
5. An approximation to the number of incorrect guesses is 5*(1/1001) = 5/1001 = 0.50%.
6. An approximation to the probability of no guesses is exp(-5) = 0.67%.
7. Total probability of failure = 0.50% + 0.67% = 1.17%.
I'm sure this isn't optimal, but will get the probability of success over 95%. It is based on ME's solution.
1. Create 5*(2^1000/2002) groups of 1000 wizards each. Everyone else is to abstain no matter what.
2. Instruct each member that if he sees all hats of the same color to guess the opposite way.
3. Here are the probabilities for any given group:
Correct guess = 2*1000/2^1000
Incorrect guess (everyone making it) = 2/2^1000
Probability group is correct given it guesses = 2000/2002 = 1000/1001.
Probability guess tendered = 2002/2^1000
4. The expected number of guesses tendered will be 5.
5. An approximation to the number of incorrect guesses is 5*(1/1001) = 5/1001 = 0.50%.
6. An approximation to the probability of no guesses is exp(-5) = 0.67%.
7. Total probability of failure = 0.50% + 0.67% = 1.17%.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
January 13th, 2014 at 7:08:59 PM
permalink
Since there have to be an infinite number of correct answers, presumably this means that everybody is divided into finite-sized groups.
If everybody is divided into groups of size N, then each group follows Wizard's "if I see everybody else in my group wearing the same color, then I guess the opposite color" strategy.
If all of the hats but one are the same color, there will be one guess within the group, and it is correct; if all of the hats are the same color, everybody will make an incorrect guess.
The probability of a correct guess is 2N / 2N, or N / 2N-1
The probability of an incorrect guess is 2 / 2N, or 1 / 2N-1
The problem is, since an infinite number of correct answers are needed, and the probability of a correct answer < 1, the product approaches zero.
If everybody is divided into groups of size N, then each group follows Wizard's "if I see everybody else in my group wearing the same color, then I guess the opposite color" strategy.
If all of the hats but one are the same color, there will be one guess within the group, and it is correct; if all of the hats are the same color, everybody will make an incorrect guess.
The probability of a correct guess is 2N / 2N, or N / 2N-1
The probability of an incorrect guess is 2 / 2N, or 1 / 2N-1
The problem is, since an infinite number of correct answers are needed, and the probability of a correct answer < 1, the product approaches zero.
January 13th, 2014 at 7:12:35 PM
permalink
Quote: WizardI'm still waiting to hear if my second solution violates the infinite right answers rule. I could always break down my method into infinitely many subsets, but some of them would be wrong. Just any one subset would have a probability of success over 95%.
I'm sure this isn't optimal, but will get the probability of success over 95%. It is based on ME's solution.
1. Create 5*(2^1000/2002) groups of 1000 wizards each. Everyone else is to abstain no matter what.
2. Instruct each member that if he sees all hats of the same color to guess the opposite way.
3. Here are the probabilities for any given group:
Correct guess = 2*1000/2^1000
Incorrect guess (everyone making it) = 2/2^1000
Probability group is correct given it guesses = 2000/2002 = 1000/1001.
Probability guess tendered = 2002/2^1000
4. The expected number of guesses tendered will be 5.
5. An approximation to the number of incorrect guesses is 5*(1/1001) = 5/1001 = 0.50%.
6. An approximation to the probability of no guesses is exp(-5) = 0.67%.
7. Total probability of failure = 0.50% + 0.67% = 1.17%.
You're not actually making an infinite number of guesses, so doesn't that automatically fail?
"In my own case, when it seemed to me after a long illness that death was close at hand, I found no little solace in playing constantly at dice."
-- Girolamo Cardano, 1563
January 13th, 2014 at 7:14:40 PM
permalink
Quote: MathExtremistYou're not actually making an infinite number of guesses, so doesn't that automatically fail?
Ungh! I guess so. I'm about ready to throw my hands in the air and give up -- speaking for myself only.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
January 13th, 2014 at 7:21:46 PM
permalink
Quote: WizardUngh! I guess so. I'm about ready to throw my hands in the air and give up -- speaking for myself only.
I have an inkling there was something slightly amiss with the problem statement; I don't see how you can have an infinite number of guesses and zero wrong ones unless the probability of being right is always 100%. But I admit to not having studied the various flavors of infinity too closely.
"In my own case, when it seemed to me after a long illness that death was close at hand, I found no little solace in playing constantly at dice."
-- Girolamo Cardano, 1563
January 13th, 2014 at 7:31:45 PM
permalink
Quote: MathExtremistI have an inkling there was something slightly amiss with the problem statement; I don't see how you can have an infinite number of guesses and zero wrong ones unless the probability of being right is always 100%. But I admit to not having studied the various flavors of infinity too closely.
Its possible as long as the limit of the probabilities of being wrong go to 0. Remember you only want a 90% chance of being right not 100%. So if you can get an infinite set of wizards first set at 9% chance of failure, next at .9%, and so on it would work. Since you'd have 9.999 repeating percent chance of missing at least one. Not sure how to construct these sets though just know that the question isn't necessarily wrong from the start.
Edit: Oh do feel the need to point out the 9% .9% and so on must be both percent chance to either miss or not answer otherwise you may run afoul of the infinite number of people answering criteria. Hope that helps someone but I am really failing right now at building appropriate sets and criteria for them to answer.
January 13th, 2014 at 7:35:17 PM
permalink
Well, they are Wizards, so why can't they cast a magical spell that, whatever they answer for themselves, it will be correct (and the hat will change to reflect their answer if necessary)?
Really, if none of them can tell individually, but all of them must somehow be able to tell simultaneously through reasoning, if the problem is to have a solution, then all of the hats must be of the same color, or it would be unsolvable.
Really, if none of them can tell individually, but all of them must somehow be able to tell simultaneously through reasoning, if the problem is to have a solution, then all of the hats must be of the same color, or it would be unsolvable.
If the House lost every hand, they wouldn't deal the game.
January 13th, 2014 at 9:08:30 PM
permalink
I would go so far as to say that Cayonero has proven that this problem, as presented, has no solution.
The trick to poker is learning not to beat yourself up for your mistakes too much, and certainly not too little, but just the right amount.
January 13th, 2014 at 9:42:47 PM
permalink
Quote: beachbumbabsWell, they are Wizards, so why can't they cast a magical spell that, whatever they answer for themselves, it will be correct (and the hat will change to reflect their answer if necessary)?
Really, if none of them can tell individually, but all of them must somehow be able to tell simultaneously through reasoning, if the problem is to have a solution, then all of the hats must be of the same color, or it would be unsolvable.
That was exactly my reasoning but I didn't want to fly in the face of conventional wisdom and posters MUCH smarter than me who are actually trying to figure this thing out :)
“There is something about the outside of a horse that is good for the inside of a man.” - Winston Churchill
January 13th, 2014 at 10:36:16 PM
permalink
I came up with DOOR #3. Am I close ?
Shed not for her
the bitter tear
Nor give the heart
to vain regret
Tis but the casket
that lies here,
The gem that filled it
Sparkles yet
January 13th, 2014 at 11:00:03 PM
permalink
Quote: TwirdmanSince you'd have 9.999 repeating...
Uh oh...
January 14th, 2014 at 7:57:21 PM
permalink
Quote: MathExtremist
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.
A group of size N has been shown by MathExtremist and the Wizard to have a probability of (1 - 1/2N-1) of not failing. The probability of global win is the product of all (infinite) group probabilities. (No communication means no correlations needed to be computed.)
This product must be higher than 90%, or its logarithm higher than ln 0.90 = -0.1053.
ln(1-x) can be approximated by -x; it is necessarily higher, anyway. So we are looking for NK's such that the SUM of ln(1-1/2NK-1) >
SUM(-1/2NK-1) > -0.1053.
It is known that the geometric series yields a + a² + a³ + ... = a/(1-a) if a²<1. With a<=0.0953178 you get a/(1-a) <= 0.1053, so you define 1/2N1-1 <= 0.0953178, or N1-1 >= 3.39111. The first group must be at least of size N1=4.39111 and MathExtremist was right to choose 5. The next groups need not be NK=N1K . It is sufficient to define NK=(N1-1) K + 1 . Or even NK>=3.39111 K + 1.
Note: not every francophone is French, exactly like Canadians are not United-Staters. Is Blanchard not a French name?
Reperiet qui quaesiverit
January 14th, 2014 at 8:34:31 PM
permalink
Quote: kubikulann
A group of size N has been shown by MathExtremist and the Wizard to have a probability of (1 - 1/2N-1) of not failing. The probability of global win is the product of all (infinite) group probabilities. (No communication means no correlations needed to be computed.)
This product must be higher than 90%, or its logarithm higher than ln 0.90 = -0.1053.
ln(1-x) can be approximated by -x; it is necessarily higher, anyway. So we are looking for NK's such that the SUM of ln(1-1/2NK-1) >
SUM(-1/2NK-1) > -0.1053.
It is known that the geometric series yields a + a² + a³ + ... = a/(1-a) if a²<1. With a<=0.0953178 you get a/(1-a) <= 0.1053, so you define 1/2N1-1 <= 0.0953178, or N1-1 >= 3.39111. The first group must be at least of size N1=4.39111 and MathExtremist was right to choose 5. The next groups need not be NK=N1K . It is sufficient to define NK=(N1-1) K + 1 . Or even NK>=3.39111 K + 1.
I was thinking along these lines, too, but doesn't this fail the requirements, because you will have too high a chance to not make any guesses. The problem stated that you must have a 90% chance of having an infinite number of correct guesses, but given a starting group of 5, the chance of not making a guess is near 62.5%. At best, this gives you a 37.5% chance of having an infinite number of correct guesses.
Quote: kubikulann
Note: not every francophone is French, exactly like Canadians are not United-Staters. Is Blanchard not a French name?
Sounds French, but if he had more French in him, he would have said "deja vu" instead of "vous" here.
I heart Crystal Math.
January 15th, 2014 at 6:41:19 PM
permalink
You're right, there is a problem.
Next step: find another group size progression?
The number of correct guesses is finite if there exists a M above which all groups abstain. The probability of this must be low.
Probability of abstention in a group of size N = p(N) = 1 - (1+N)/2N-1
Probability of abstention in ALL groups of size greater or equal to M = q(M) = PRODUCT{N=M to inf} p(N)
Consequence: as q(M+1) >= q(M) and it must be low, we will be interested in the largest M, i.e. M tending to infinity.
- ln q(M) = - SUM ln p(N) = (approximately) SUM ((1+N)/2N-1)
In our proposed succession of NK = Kn* :
=[1/2N-1]M { (1+Mn*)(1/2N-1) + (1+(M+1)n*)(1/2N-1)² + (1+(M+2)n*)(1/2N-1)³ + (1+(M+3)n*)(1/2N-1)4 + ...}
=[1/2N-1]M { (1+Mn*)(1/2N-1) - (1+Mn*-n*)(1/2N-1)² } / { (1 - 1/2N-1)² }
=[1/2N-1]M { 1+Mn* - (1+Mn*-n*) 1/2N-1 }(1/2N-1) / { (1 - 1/2N-1)² }
This tends to zero as M tends to infinity.
So, q(M) tends to 1. There is a quasi-certainty that the number of correct guesses will be finite.
Probability of abstention in a group of size N = p(N) = 1 - (1+N)/2N-1
Probability of abstention in ALL groups of size greater or equal to M = q(M) = PRODUCT{N=M to inf} p(N)
Consequence: as q(M+1) >= q(M) and it must be low, we will be interested in the largest M, i.e. M tending to infinity.
- ln q(M) = - SUM ln p(N) = (approximately) SUM ((1+N)/2N-1)
In our proposed succession of NK = Kn* :
=[1/2N-1]M { (1+Mn*)(1/2N-1) + (1+(M+1)n*)(1/2N-1)² + (1+(M+2)n*)(1/2N-1)³ + (1+(M+3)n*)(1/2N-1)4 + ...}
=[1/2N-1]M { (1+Mn*)(1/2N-1) - (1+Mn*-n*)(1/2N-1)² } / { (1 - 1/2N-1)² }
=[1/2N-1]M { 1+Mn* - (1+Mn*-n*) 1/2N-1 }(1/2N-1) / { (1 - 1/2N-1)² }
This tends to zero as M tends to infinity.
So, q(M) tends to 1. There is a quasi-certainty that the number of correct guesses will be finite.
Next step: find another group size progression?
Reperiet qui quaesiverit
January 16th, 2014 at 12:26:32 PM
permalink
Your more fundamental problem is you've got the probability of failing, not that of not failing. The probability of a group of wizards not failing is the probability that every single individual guesses right, i.e., 1/2^n. For any nontrivial group this will be less than 90%, so you're finished before you start.
No matter which wizards answer, an infinite number of wizards will have an infinitesimal probability of all being right, unless they have some information about their own hat. I'm not sure what information we're supposed to think they have, if not by communication. Even if they could see every single wizard, the landscape seen by a white-hat wizard and a black-hat wizard would be indistinguishable, since removing a finite number from an infinite population won't change the relative populations. I'm wondering if this is the same kind of voodoo pseudo-math by which allegedly a child becomes 16% less likely to be a boy based on not knowing whether they're older or younger than their brother (i.e., each wizard looks at the surrounding wizards, and gambler's-fallacies away).
(No spoiler markup because if I'm wrong, it doesn't matter, and if I'm right, this problem doesn't merit it.)
No matter which wizards answer, an infinite number of wizards will have an infinitesimal probability of all being right, unless they have some information about their own hat. I'm not sure what information we're supposed to think they have, if not by communication. Even if they could see every single wizard, the landscape seen by a white-hat wizard and a black-hat wizard would be indistinguishable, since removing a finite number from an infinite population won't change the relative populations. I'm wondering if this is the same kind of voodoo pseudo-math by which allegedly a child becomes 16% less likely to be a boy based on not knowing whether they're older or younger than their brother (i.e., each wizard looks at the surrounding wizards, and gambler's-fallacies away).
(No spoiler markup because if I'm wrong, it doesn't matter, and if I'm right, this problem doesn't merit it.)
The trick to poker is learning not to beat yourself up for your mistakes too much, and certainly not too little, but just the right amount.
January 16th, 2014 at 2:49:11 PM
permalink
Pfff! 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?Quote: 24Bingosame kind of voodoo pseudo-math by which allegedly a child becomes 16% less likely to be a boy based on not knowing whether they're older or younger than their brother
Reperiet qui quaesiverit
January 16th, 2014 at 2:55:51 PM
permalink
Next time they'll talk about "voodoo pseudo-physics" that says time is relative and "voodoo pseudo-biology" that says humans are evolved from primates.
Ignorance is bliss, they say. Well, for the ignorant maybe, but not for the informed to be endured from the ignorants.
Ignorance is bliss, they say. Well, for the ignorant maybe, but not for the informed to be endured from the ignorants.
Reperiet qui quaesiverit
January 16th, 2014 at 2:57:22 PM
permalink
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?
I have to agree with you there. It is one thing to be ignorant, which is already bad enough, it is quite another to be proud of your ignorance and say well I must be right because thats how I think it should work. Math can be incredibly difficult and even some really simple examples of elementary probability are incredibly counter intuitive that does not mean they are wrong. Intuition is nothing against the power of mathematical proof.
January 16th, 2014 at 2:58:38 PM
permalink
Nope.Quote: 24BingoYour more fundamental problem is you've got the probability of failing, not that of not failing. The probability of a group of wizards not failing is the probability that every single individual guesses right, i.e., 1/2^n.
What is required is just that one individual per group is right (and the others abstain), provided there are infinitely many such groups.
Reperiet qui quaesiverit
January 16th, 2014 at 3:04:16 PM
permalink
Quote: kubikulannNope.
What is required is just that one individual per group is right (and the others abstain), provided there are infinitely many such groups.
Technically don't even need to go that far. Don't you simply need each group to have a non zero probability of having one answer. Its perfectly acceptable in project to have an infinite number of the groups fail to answer as long as an infinite number of groups do answer.
January 16th, 2014 at 3:08:20 PM
permalink
I wonder how many are truly proud of their ignorance, and how many are just playing up a countenance because they hate to recognize their ignorance.Quote: TwirdmanI have to agree with you there. It is one thing to be ignorant, which is already bad enough, it is quite another to be proud of your ignorance .
I have colleagues (historians, language & literature, philosophy) who, sadly, boast about knowing nothing of math. I am terrified when this attitude is present in so-called educated people (University professors, please!).
Reperiet qui quaesiverit
January 16th, 2014 at 3:12:42 PM
permalink
You are right. That's what I meant when writing "infinitely many such groups". I didn't ask "all groups". But you are right in pointing that the groups where there is not one right-guessing member must be groups where everyone abstains.Quote: TwirdmanTechnically don't even need to go that far. Don't you simply need each group to have a non zero probability of having one answer. Its perfectly acceptable in project to have an infinite number of the groups fail to answer as long as an infinite number of groups do answer.
Of course, the requirements of the problem allow for more than one right-guesser per group, but I stick to the "Pascal triangle" idea of Wizard and MathEx.
Reperiet qui quaesiverit
