[bonanova]

Ten prisoners are selected and told by the warden that next morning a hat with a single digit 0-9 will be placed on each of their heads.

The digits can be repeated; not all digits need be used.

Each prisoner can see the other nine numbered hats.

After the hats are placed, each prisoner will be brought to the warden, one by one and out of sight and hearing of the others, to guess his own number.

If at least one prisoner gets it right, all ten will be released.

Otherwise they all will be executed.

A strategy may be agreed upon tonight.

The prisoners then cannot communicate with anyone else until they have all spoken to the warden.

What strategy gives them the best chance of being released?

[superprismatic]

Well.....This is embarrassing! I spent a lot of time

deriving the probability and I made a logic mistake.

If I had programmed it, my mistake would have surfaced

quickly. I'm sorry for wasting everyone's time on my

mistake. I just programmed it and I get .44 now.

Either Drexlin or I have a bug for my strategy. Of

course, the way things are going on this problem, I'd

now bet that the bug is mine. In any event, please

accept my apology for this.

[Guest]

Nobody else, then? Well, you can't say I didn't give you all a chance.

Assign a different digit to each prisoner. Each prisoner computes the sum of the nine digits they can see, subtracts it from the next larger number ending with their assigned digit, which they then submit as their guess (or, mod10[digit-sum] if you prefer). Any prisoner whose assigned digit is also the last digit in the sum of all ten numbers will give their hat number. Because all digits can be assigned, they are guaranteed to win.

[Guest]

Nice puzzle... I'm still thinking.

Edited August 4, 2010 by Use the Force

[Guest]

Nobody else, then? Well, you can't say I didn't give you all a chance.

Assign a different digit to each prisoner. Each prisoner computes the sum of the nine digits they can see, subtracts it from the next larger number ending with their assigned digit, which they then submit as their guess (or, mod10[digit-sum] if you prefer). Any prisoner whose assigned digit is also the last digit in the sum of all ten numbers will give their hat number. Because all digits can be assigned, they are guaranteed to win.

That definitely looks right. Too bad I read your answer instead of figuring it out on my own. I would have rather been told that there was a way to guarantee success and then I would been able to have the fun figuring it out. Good job.

Edited August 4, 2010 by Use the Force

[bushindo]

Nobody else, then? Well, you can't say I didn't give you all a chance.

Assign a different digit to each prisoner. Each prisoner computes the sum of the nine digits they can see, subtracts it from the next larger number ending with their assigned digit, which they then submit as their guess (or, mod10[digit-sum] if you prefer). Any prisoner whose assigned digit is also the last digit in the sum of all ten numbers will give their hat number. Because all digits can be assigned, they are guaranteed to win.

I agree with this solution.

Let T be the sum of all the numbers on the hats. T modulo 10 can range from 0-9. Each of the 10 prisoners assume a different value for T from 0-9, and compute their hat number accordingly from what he sees. The prisoner with the correct guess for T will have the correct hat guess.

[Guest]

Wow, was I way off base.

I wrote my own simulation in JavaScript (attached for any interested) and d3k3's method always succeeded.

The script is attached for anyone interested, but it's a bit esoteric as I wrote it for myself.

Good puzzle Bonanova and well done d3k3. You definitely got the win.

prisonerTest.html

[Guest]

Nobody else, then? Well, you can't say I didn't give you all a chance.

Assign a different digit to each prisoner. Each prisoner computes the sum of the nine digits they can see, subtracts it from the next larger number ending with their assigned digit, which they then submit as their guess (or, mod10[digit-sum] if you prefer). Any prisoner whose assigned digit is also the last digit in the sum of all ten numbers will give their hat number. Because all digits can be assigned, they are guaranteed to win.

Wow!

Kudos, d3k3! Well done!