dblanch256
dblanch256
Joined: Jan 9, 2014
  • Threads: 7
  • Posts: 92
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:

  1. 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.
  2. 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.
  3. 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.
  4. 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
MathExtremist
MathExtremist
Joined: Aug 31, 2010
  • Threads: 88
  • Posts: 6526
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.
"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
Wizard
Administrator
Wizard
Joined: Oct 14, 2009
  • Threads: 1423
  • Posts: 24357
January 13th, 2014 at 9:18:47 AM permalink
Quote: dblanch256

I'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.
It's not whether you win or lose; it's whether or not you had a good bet.
MathExtremist
MathExtremist
Joined: Aug 31, 2010
  • Threads: 88
  • Posts: 6526
January 13th, 2014 at 10:03:05 AM permalink
Quote: Wizard

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.


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
Wizard
Administrator
Wizard
Joined: Oct 14, 2009
  • Threads: 1423
  • Posts: 24357
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.
It's not whether you win or lose; it's whether or not you had a good bet.
CrystalMath
CrystalMath
Joined: May 10, 2011
  • Threads: 8
  • Posts: 1907
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.
dblanch256
dblanch256
Joined: Jan 9, 2014
  • Threads: 7
  • Posts: 92
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
Canyonero
Canyonero
Joined: Nov 19, 2012
  • Threads: 40
  • Posts: 509
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.
MathExtremist
MathExtremist
Joined: Aug 31, 2010
  • Threads: 88
  • Posts: 6526
January 13th, 2014 at 11:19:57 AM permalink
Quote: Canyonero

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.


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
Canyonero
Canyonero
Joined: Nov 19, 2012
  • Threads: 40
  • Posts: 509
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.

  • Jump to: