[Guest]

This is an extension on The Cap Puzzle and Hats on a death row!!

There are 101 logicians who are presented with a task. They are to be placed in a line on a downward sloping hill so that each logician can see everyone in front of him. From a box of caps with 10 different colors (of their choice) they will randomly have a cap chosen and placed on each their heads.

Each person, starting with the person at the back of the line is to quickly speak. If a person correctly calls out the color of his hat (which he cannot see) the group will get $100.

They will not be allowed to use any tricks, such as taking different times to call out the color or any other signals of that sort. They are allowed to meet beforehand to discuss a strategy.

What average amount of money they can make and what would their strategy be to obtain this maximum percentage or correct colors?

[Guest]

This is an extension on The Cap Puzzle and Hats on a death row!!

There are 101 logicians who are presented with a task. They are to be placed in a line on a downward sloping hill so that each logician can see everyone in front of him. From a box of caps with 10 different colors (of their choice) they will randomly have a cap chosen and placed on each their heads.

Each person, starting with the person at the back of the line is to quickly speak. If a person correctly calls out the color of his hat (which he cannot see) the group will get $100.

They will not be allowed to use any tricks, such as taking different times to call out the color or any other signals of that sort. They are allowed to meet beforehand to discuss a strategy.

What average amount of money they can make and what would their strategy be to obtain this maximum percentage or correct colors?

To clarify, how many caps are in the box? Are all 10 different colors represented equally?

so I'll say that every other logician tells what the color on the next head is, so one might say 'red' and two would also say 'red' because one just told him. Then 3 would tell and 4 would get it right.

In this way, 50 logicians would be correct. The remaining 51 would have a 1 in 10 chance, so an additional 5 would be expected.

The group will thus net $5500 without having to think too hard about it.

[Guest]

To clarify, how many caps are in the box? Are all 10 different colors represented equally?

Yes, assume that after they give the organizers the colors, the organizers put 101 of each color (1010 caps) in the box; so their individual hat color is truly random.

[Guest]

The first person in line calls out the most common hat color, and the other 100 call the same color.

[Guest]

The first person in line calls out the most common hat color, and the other 100 call the same color.

If each odd logician called out the hat of the next even logician, they should each have a 1 in 10 chance of matching their own hats, and all 50 of the evens can just repeat what the prior logician said and be right every time (the last odd logician just makes a wild guess). So, on average, $100 * (50+51*0.1) = $5510.

[Guest]

If each odd logician called out the hat of the next even logician, they should each have a 1 in 10 chance of matching their own hats, and all 50 of the evens can just repeat what the prior logician said and be right every time (the last odd logician just makes a wild guess). So, on average, $100 * (50+51*0.1) = $5510.

The colors could be assigned numeric values 0-9, since they have a choice and a chance to discuss them. Then the first logician could add up all the associated numbers of the remaining 100 logicians and report the last digit (the one in the one's place). He would still have a 1 in 10 chance, good for $10 on average. Each subsequent logician could derive his own hat by subtracting the sum of the 99 logicians' hat values he can see who are not the first from the total reported by the first. On average, the team should net $10 + $100 * 100 = $10010.

Edited January 8, 2009 by Phatfingers

[Guest]

Well done, Phatfingers.

As this puzzle was an extension of the previous puzzle, it's no surprise that the solution be an an extension of the previous solution as well.

[Guest]

Well done, Phatfingers.

As this puzzle was an extension of the previous puzzle, it's no surprise that the solution be an an extension of the previous solution as well.

Thanks! I wasn't sure I was going to get away with it, in that the first logician kind of broke a rule... I also worked out a solution with the same score that doesn't break any rules.

last digit of (10 + (digit called out by #1) - (last digit of sum of 99 visible hats excluding first))

Edited January 8, 2009 by Phatfingers

[Guest]

Thanks! I wasn't sure I was going to get away with it, in that the first logician kind of broke a rule... I also worked out a solution with the same score that doesn't break any rules.

last digit of (10 + (digit called out by #1) - (last digit of sum of 99 visible hats excluding first))

Sorry, this violates the OP.

Each person, starting with the person at the back of the line is to quickly speak. If a person correctly calls out the color of his hat (which he cannot see) the group will get $100.

I don't care how brilliant your logicians are, they are not going to be able to sum a hundred (or even 20) hats and to the math in time to answer "quickly".

Besides, the first guy isn't allowed to call out a non-color, and there is no way to know simply by knowing the last digit - as you seemed to be suggesting encoding the last digit in the first magicians color choice).

Therefore the ~$5500 is still the best answer.

[Guest]

I don't care how brilliant your logicians are, they are not going to be able to sum a hundred (or even 20) hats and to the math in time to answer "quickly".

Sorry, but Phatfingers had the correct answer. You're being too technical with wordplay. I could say a lot of other many logic puzzles are impossible because they couldn't occur in real life.

The idea behind saying quickly was to disallow answers where one person could should out many colors (say all the colors in front of him).

Even so, the logicians don't need to sum a hundred in an instant, they can do it as the hats are being placed on the people in front of them.

Besides, the first guy isn't allowed to call out a non-color, and there is no way to know simply by knowing the last digit - as you seemed to be suggesting encoding the last digit in the first magicians color choice).

If you actually look at the wording [Each person] is to quickly speak. If a person correctly calls out the color of his hat... doesn't say you have to say a color, just that once you speak you'll get the money if you correctly call out the color.

Even so, in the correct answer, the first person takes the sum of all the folks in front of him, finds the unit digit and calls out the color of the hat associated with that digit, thus giving him the 1/10 of a chance to also be correct. Its essentially the same solution as the Black and White cap puzzle.

[Guest]

Sorry, but Phatfingers had the correct answer. You're being too technical with wordplay. I could say a lot of other many logic puzzles are impossible because they couldn't occur in real life.

The idea behind saying quickly was to disallow answers where one person could should out many colors (say all the colors in front of him).

Even so, the logicians don't need to sum a hundred in an instant, they can do it as the hats are being placed on the people in front of them.

If you actually look at the wording [Each person] is to quickly speak. If a person correctly calls out the color of his hat... doesn't say you have to say a color, just that once you speak you'll get the money if you correctly call out the color.

Even so, in the correct answer, the first person takes the sum of all the folks in front of him, finds the unit digit and calls out the color of the hat associated with that digit, thus giving him the 1/10 of a chance to also be correct. Its essentially the same solution as the Black and White cap puzzle.

Thanks for the backup, Vinays, but I'd also like to point out a couple of things that would reduce the math to something much simpler than adding 99 numbers in your head. Since they are only concerned with the last digit (technically, the sum modulo 10 which equates to the last digit), they can safely ignore any group of 10 hats of the same color, which is likely to be more than half of them, some possibly even being exactly 10. For the remaining hats, they can easily multiply counts of hats of like color by their respective values (a single-digit number times another single-digit number-- no sweat for a logician), use only the last digit of each result, and reduce the problem to performing maybe 7 multiplications and adding the last digits of each together. Maybe not instantaneous, but pretty fast, nonetheless.

Note also that I used the word "digit" in describing what the first logician spoke. What I meant was the hat color that would express the last digit.

[Guest]

I concede that you can almost encode the information in the unit digit, based on phat's explanation, but with one important caveat - there is no color encoded by 0, what happens if the initial sum has a 0 in the units place?

Also worth considering is failure rate. If even one logician makes an error in summing the hats in front of him, the whole lot is screwed and your expectation is much less that $5500. Ignoring risk has gotten us in to a financial pickle as of late, don't you think? If you assume a 1% error rate in logician summation, your average winnings are essentially cut in half. The 'every other' method would have a much lower error rate, and has the advantage that the errors don't propagate.

Finally, I think you are selectively interpreting the OP to fit your desired solution. I think there is a subtle but real difference between "quickly speak" and "speak quickly". You said the former but seem to have wanted the latter. If the constraints that you wanted to impart had been stated more precisely I would have no basis for objection. The problems this is based on had a nice penalty for cheaters, like getting killed. Since there is no prohibition against it, nor penalty for calling multiple colors there are any number of solutions that would improve the odds of correctly stating your hat's color.

All in all, I'll take the safe and easy $5500.

Sorry, but Phatfingers had the correct answer. You're being too technical with wordplay. I could say a lot of other many logic puzzles are impossible because they couldn't occur in real life.

The idea behind saying quickly was to disallow answers where one person could should out many colors (say all the colors in front of him).

Even so, the logicians don't need to sum a hundred in an instant, they can do it as the hats are being placed on the people in front of them.

If you actually look at the wording [Each person] is to quickly speak. If a person correctly calls out the color of his hat... doesn't say you have to say a color, just that once you speak you'll get the money if you correctly call out the color.

Even so, in the correct answer, the first person takes the sum of all the folks in front of him, finds the unit digit and calls out the color of the hat associated with that digit, thus giving him the 1/10 of a chance to also be correct. Its essentially the same solution as the Black and White cap puzzle.

[Guest]

Also worth considering is failure rate. If even one logician makes an error in summing the hats in front of him, the whole lot is screwed and your expectation is much less that $5500. Ignoring risk has gotten us in to a financial pickle as of late, don't you think? If you assume a 1% error rate in logician summation, your average winnings are essentially cut in half. The 'every other' method would have a much lower error rate, and has the advantage that the errors don't propagate.

A bird in the hand, eh? I believe the solution is more robust than you think, and does, in fact, maximize winnings.

red=0, orange=1, yellow=2, green=3, blue=4, indigo=5, violet=6, black=7, grey=8, white=9

If we cut the problem down to, say 21 hats, in the order: 1 1 2 3 5 8 3 1 4 5 9 4 3 7 0 7 7 4 1 5 6

The equation is "last digit of (10 + (digit called out by #1) - (last digit of sum of all visible hats excluding #1's))"

The first logician sums the last 20, gets 85 and guesses "5=indigo". He adds right, but his guess doesn't match his hat (he only had a 10% chance).

The second logician sums the last 20 (minus himself), gets 84. 10+5-4=11. He guesses "1=orange". Correct.

The third logician sums the last 20 (minus himself), gets 83. 10+5-3=12. He guesses "2=yellow". Correct.

The fourth logician is your 1% error rate. He miscounts and guesses "4=blue". Incorrect.

The fifth logician sums the last 20 (minus himself), gets 80. 10+5-0=15. He guesses "5=indigo". Correct.

The sixth logician sums the last 20 (minus himself), gets 77. 10+5-7=8. He guesses "8=grey". Correct.

And so on...

The mistake of a prior logician wouldn't affect the others. Only an error in the first logician's total would do that, and if he did fail, another logician could bring them back on track-- they would just need to start the group to sum from the first logician whose hat was correct and use the prior logicians guessed value in their equation.

[bonanova]

This puzzle was posted in 3-color form here.

In discussion it was generalized to n colors.

The best 3-color solutions were from octopuppy and Steve17.

In the spirit of fresh debate, this thread will persist.

[Guest]

Sorry to make you write it out, I realize now that I was erroneously thinking there were 9 colors, and that 0 was unused.

Of course, your solution does allow the maximum possible return.

I still assert that errors can propagate, although your example shows that only a subset will do so - unless you assume they are told after each turn whether or not they are correct, which is a lot to assume.

in your example #5 knew there was a problem because #4's color made the running sum too high, and caused him to ignore that input and go back to the previous sum. If #4 had instead guessed 'orange' (meaning 1), then #5 wouldn't have known anything was amiss and would have stated an off-by-one answer, and subsequent logicians would also be off.

In general, I think if a logician over-counts the hats in front of them they will provide a color represented by a lower number, and the error will propagate.

And this error correction function is added to their computational overhead (color to number mapping, summing of hats in front, keeping track of running sum). If they can do this and still speak quickly, I think we need them in Obama's cabinet!

A bird in the hand, eh? I believe the solution is more robust than you think, and does, in fact, maximize winnings.

red=0, orange=1, yellow=2, green=3, blue=4, indigo=5, violet=6, black=7, grey=8, white=9

If we cut the problem down to, say 21 hats, in the order: 1 1 2 3 5 8 3 1 4 5 9 4 3 7 0 7 7 4 1 5 6

The equation is "last digit of (10 + (digit called out by #1) - (last digit of sum of all visible hats excluding #1's))"

The first logician sums the last 20, gets 85 and guesses "5=indigo". He adds right, but his guess doesn't match his hat (he only had a 10% chance).

The second logician sums the last 20 (minus himself), gets 84. 10+5-4=11. He guesses "1=orange". Correct.

The third logician sums the last 20 (minus himself), gets 83. 10+5-3=12. He guesses "2=yellow". Correct.

The fourth logician is your 1% error rate. He miscounts and guesses "4=blue". Incorrect.

The fifth logician sums the last 20 (minus himself), gets 80. 10+5-0=15. He guesses "5=indigo". Correct.

The sixth logician sums the last 20 (minus himself), gets 77. 10+5-7=8. He guesses "8=grey". Correct.

And so on...

The mistake of a prior logician wouldn't affect the others. Only an error in the first logician's total would do that, and if he did fail, another logician could bring them back on track-- they would just need to start the group to sum from the first logician whose hat was correct and use the prior logicians guessed value in their equation.

Edited January 9, 2009 by xucam

[Guest]

Sorry to make you write it out, I realize now that I was erroneously thinking there were 9 colors, and that 0 was unused.

Of course, your solution does allow the maximum possible return.

I still assert that errors can propagate, although your example shows that only a subset will do so - unless you assume they are told after each turn whether or not they are correct, which is a lot to assume.

in your example #5 knew there was a problem because #4's color made the running sum too high, and caused him to ignore that input and go back to the previous sum. If #4 had instead guessed 'orange' (meaning 1), then #5 wouldn't have known anything was amiss and would have stated an off-by-one answer, and subsequent logicians would also be off.

In general, I think if a logician over-counts the hats in front of them they will provide a color represented by a lower number, and the error will propagate.

And this error correction function is added to their computational overhead (color to number mapping, summing of hats in front, keeping track of running sum). If they can do this and still speak quickly, I think we need them in Obama's cabinet!

Logician #5 had no reason to believe there was a problem and answered normally. Unless the very first logician miscounted, the other prior logicians' answers, whether right or wrong, don't factor into the equation. They can answer in any order they want and don't have to hear any other answers except for that given by the first logician. As soon as each of the logicians have tabulated the totals from the 100 logicians in the range 2-101 (omitting themselves), they can just plug the number of the color called out by the first logician, plus the last digit of their tabulated value into the same equation and all have their answers at the same time.

The worst case scenario would be if the first logician miscounted. In that case, the first several logicians would give wrong answers, and that would signal the remaining ones to use the same strategy with a smaller set. That is stretching the boundaries of the problem well past its puzzling solution, but the point is that is that human failures could be corrected with this strategy, even at it's weakest point.

[Guest]

Logician #5 had no reason to believe there was a problem and answered normally. Unless the very first logician miscounted, the other prior logicians' answers, whether right or wrong, don't factor into the equation. They can answer in any order they want and don't have to hear any other answers except for that given by the first logician. As soon as each of the logicians have tabulated the totals from the 100 logicians in the range 2-101 (omitting themselves), they can just plug the number of the color called out by the first logician, plus the last digit of their tabulated value into the same equation and all have their answers at the same time.

The worst case scenario would be if the first logician miscounted. In that case, the first several logicians would give wrong answers, and that would signal the remaining ones to use the same strategy with a smaller set. That is stretching the boundaries of the problem well past its puzzling solution, but the point is that is that human failures could be corrected with this strategy, even at it's weakest point.

I don't understand how the answers be independent of previous answers. Logician X can see 101 - X hats. The X = 1 logician can see 100 hats, L2 sees 99 hats (all except hers and L1's), L3 sees 98, all but La, L2, and self, etc. You seem to be saying that each logician can see all hats but their own, which is not true.

L1 and is the crux, in that if he screws up they are lost. L2 uses that value, let us call it L1_sum. L3 uses L1_sum, decrements L2 hat color, then compares it to the sum that he sees.

As an example, if I told you that the sum of all hats is 873, and in front of you the hats sum to 832, what color (number) is your hat? There is not enough info to figure it out.

Or am I missing something obvious?

Edited January 9, 2009 by xucam

[Guest]

Logician #5 had no reason to believe there was a problem and answered normally. Unless the very first logician miscounted, the other prior logicians' answers, whether right or wrong, don't factor into the equation. They can answer in any order they want and don't have to hear any other answers except for that given by the first logician. As soon as each of the logicians have tabulated the totals from the 100 logicians in the range 2-101 (omitting themselves), they can just plug the number of the color called out by the first logician, plus the last digit of their tabulated value into the same equation and all have their answers at the same time.

The worst case scenario would be if the first logician miscounted. In that case, the first several logicians would give wrong answers, and that would signal the remaining ones to use the same strategy with a smaller set. That is stretching the boundaries of the problem well past its puzzling solution, but the point is that is that human failures could be corrected with this strategy, even at it's weakest point.

Heh. I just noticed something. The instructions said that each logician could see all the others in front of him, and my solution assumed that the logicians could all see each other up and down the hill. That would make a difference. If that's the case, then it would, as xucam suggests, be much easier for an error to propagate, because instead of each logician seeing all the number equivalent hats, he would have to, on average, see half of the hats and hear the other half to get the values to plug into the equation. So if any one was wrong, he would get an incorrect total. Their game would have to be on that day to hear a bunch of color values and translate them into number values while tabulating them in real time. As much as I'd like to take a bow for figuring something out, what I figured out was not what this puzzle asked for.