dblanch256
Joined: Jan 9, 2014
• Posts: 92
January 18th, 2014 at 4:11:37 PM permalink
Quote: 24Bingo

I 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>
David C Blanchard
24Bingo
Joined: Jul 4, 2012
• Posts: 1348
January 19th, 2014 at 3:15:34 AM permalink
Looking at the Wikipedia page on convergence tests, in the hope of proving my previous solution, I realize, yes, I was overthinking it, but I don't think your "simplified problem" gave us anything that we hadn't gotten already.

For 0 < asuff. large k < 1, Π(1-ak) converges iff Σak converges, by the limit comparison test with the logarithm. Therefore, what we need is an f(x) such that Σ21-f(x) converges but Σf(x)*21-f(x) diverges. So it has to be that f(x+1)/f(x) must meet 2f(x+1)-f(x) at infinity, by the ratio test. I've got to say, I have difficulty seeing how this is possible, although after last time I'm hesitant to declare it "impossible." My mind again turns to tetration - I'm not quite sure of its behavior at infinity - although now I see that if the solution does involve tetration, my factor of x3 is unnecessary. Since your comparable problem seems to use the same strategy of the Wizard, though, and I'm about as sure as I can be that any progression that comes from Pascal's triangle isn't going to cut it with that strategy, I strongly suspect your proposed solution is wrong.
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.
dblanch256
Joined: Jan 9, 2014
• Posts: 92
January 19th, 2014 at 8:08:09 AM permalink
Quote: MathExtremist

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.

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!
David C Blanchard
dblanch256
Joined: Jan 9, 2014
• Posts: 92
January 19th, 2014 at 6:54:24 PM permalink
Quote: dblanch256

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?

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.
David C Blanchard
kubikulann
Joined: Jun 28, 2011
• Posts: 905
January 19th, 2014 at 7:01:42 PM permalink
Quote: dblanch256

I'll present my own answer for peer review.

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?
Reperiet qui quaesiverit
kubikulann
Joined: Jun 28, 2011
• Posts: 905
January 19th, 2014 at 7:13:49 PM permalink
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.

(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.
Reperiet qui quaesiverit
Twirdman
Joined: Jun 5, 2013
• Posts: 1004
January 19th, 2014 at 7:24:28 PM permalink
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?
CrystalMath
Joined: May 10, 2011
• Posts: 1907
January 19th, 2014 at 8:07:29 PM permalink
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.
I heart Crystal Math.
24Bingo
Joined: Jul 4, 2012
• Posts: 1348
January 19th, 2014 at 10:03:11 PM permalink
Quote: kubikulann

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?

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.")
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.
Twirdman
Joined: Jun 5, 2013