[Trumpace]

A prison with 100 inmates has an eccentric warden (what's new?).

He decides that he will release them if they are smart/lucky enough to win the game he is going to play with them:

On a Sunday morning, every prisoner will be assigned a number (integer) from 1 to 100 (inclusive), which will be written on his forehead. Any number may be assigned to an arbitrary number of prisoners (repetitions allowed!)

Every prisoner will see the numbers of the other 99, but won't see his own number. The prisoners then guess their own numbers simultaneously. (There will be a guard assigned to each prisoner to note down the guess: yes, it is a high security prison)

If at least one prisoner guesses his number right, they are all released immediately. Otherwise, they will need to wait another year for another challenge.

On the evening before, they are allowed to gather together and devise a strategy.

What should the prisoners' strategy be?

[jonottawa]

Trumpace, on Nov 20 2007, 05:06 PM, said:

A prison with 100 inmates has an eccentric warden (what's new?).

He decides that he will release them if they are smart/lucky enough to win the game he is going to play with them:

On a Sunday morning, every prisoner will be assigned a number (integer) from 1 to 100 (inclusive), which will be written on his forehead. Any number may be assigned to an arbitrary number of prisoners (repetitions allowed!)

Every prisoner will see the numbers of the other 99, but won't see his own number. The prisoners then guess their own numbers simultaneously. (There will be a guard assigned to each prisoner to note down the guess: yes, it is a high security prison)

If at least one prisoner guesses his number right, they are all released immediately. Otherwise, they will need to wait another year for another challenge.

On the evening before, they are allowed to gather together and devise a strategy.

What should the prisoners' strategy be?

Find a wise old dwarf as quickly as possible.

I don't think it's clear from the parameters whether they are permitted to signal each other in ANY way, are they?

If they aren't (let's say they're locked up in solitary) then this is an impossible problem. It'd be like trying to pick a roulette number based on the last 20 rolls.

If they are, then this is a really simple problem.

[Trumpace]

jonottawa, on Nov 20 2007, 12:07 PM, said:

Find a wise old dwarf as quickly as possible.

I don't think it's clear from the parameters whether they are permitted to signal each other in ANY way, are they?

If they aren't (let's say they're locked up in solitary) then this is an impossible problem.  It'd be like trying to pick a roulette number based on the last 20 rolls.

If they are, then this is a really simple problem.

No. They are not allowed to signal each other in anyway.


Are you willing to bet that it is an impossible problem?

[gwnn]

nice one. estimated date of my solution: 19th september, 2015

[hrothgar]

I don't think that the problem is being described properly.

Lets assume that each prisoner is assigned a number at random from the uniform distribution [1-100]

Lets assume that each prisoner decided to randomly guess a number between [1-100] using a uniform PDF.

The chance that the first prisoner will correctly guess his own number is 1/100.

The chance that each and every one of the 100 prisoners will incorrectly guess their own number is (.99^100) = 0.366032341

There is a ~64% chance that everyone gets released in the first year.

If the prisoners are really bared from any kind of communication then I don't see any obvious way to improve on this without some kind of silly assumption about the function used to assigned numbers to prisoners. For example, if the numbers are being assigned using a pseudo-random process, you might be able to do something clever.

[han]

hrothgar, on Nov 20 2007, 02:26 PM, said:

I don't think that the problem is being described properly.

I think it is and you are missing the point.


Warning, hidding hint following:

Spoiler

Try to do it with 2 prisoners and the numbers 1 and 2 first.

[jonottawa]

I agree with hrothgar.

If it's some semantical game (does 'inclusive' imply that the numbers 1 and 100 must appear? if so, all prisoners can guess 1 or all prisoners can guess 100) then whatever.

It's implied that each number is random and that since repetitions are allowed, not all numbers must appear.

It doesn't work with 2 prisoners either. Each has a 50% chance of guessing wrong in that case.

[Echognome]

Perhaps I'm missing something. If only one needs to guess correctly, why don't they label themselves 1 to 100 and each guess their label? Then they've covered the entire range of numbers and someone will have guessed correctly. Obviously that is too easy, so you'll have to tell me in the setup why this isn't the case.

[inquiry]

Quote

If at least one prisoner guesses his number right, they are all released immediately. Otherwise, they will need to wait another year for another challenge.

with two prisoners the problem is trivial. One guesses 1, one guess 2, at least one of them has to be right, so they go free.

With the problem as stated, each prisoner guess a unique number from 1 to 100, at least one of them has to be right, so they all go free. Surely this is not so stupid to be that easy. The problem needs to be restated...

[jonottawa]

inquiry, on Nov 20 2007, 08:03 PM, said:

Quote

If at least one prisoner guesses his number right, they are all released immediately. Otherwise, they will need to wait another year for another challenge.

with two prisoners the problem is trivial. One guesses 1, one guess 2, at least one of them has to be right, so they go free.

With the problem as stated, each prisoner guess a unique number from 1 to 100, at least one of them has to be right, so they all go free. Surely this is not so stupid to be that easy. The problem needs to be restated...

?????

[han]

No, it is not that stupid.

Each prisoner gets a number but more than one can have the same number. So not every number has to be used.

I have never heard of the problem before but I am certain that this what Trumpace meant.

As a further hint, here is a possible solution for two prisoners using the numbers 1 and 2:

Spoiler

Prisoner A guesses the number Prisoner B has.

Prisoner B guesses the number prisoner A does not have.

If they have different numbers then prisoner B guesses right. If they have the same number than prisoner A guesses right. In either case they go free.

This is a big hint but the problem is still interesting afterwards.

[jonottawa]

Glad I didn't bet. Fooled again.

Great problem.

"One of these days in your travels, a guy is going to come up to you and show you a nice brand-new deck of cards on which the seal is not yet broken, and this guy is going to offer to bet you that he can make the Jack of Spades jump out of the deck and squirt cider in your ear. But, son, do not bet this man, for as sure as you are standing there, you are going to end up with an earful of cider."

[bid_em_up]

Trumpace, on Nov 20 2007, 12:06 PM, said:

On a Sunday morning, every prisoner will be assigned a number (integer) from 1 to 100 (inclusive), which will be written on his forehead. Any number may be assigned to an arbitrary number of prisoners (repetitions allowed!)

Every prisoner will see the numbers of the other 99, but won't see his own number. The prisoners then guess their own numbers simultaneously. (There will be a guard assigned to each prisoner to note down the guess: yes, it is a high security prison)

If at least one prisoner guesses his number right, they are all released immediately. Otherwise, they will need to wait another year for another challenge.

On the evening before, they are allowed to gather together and devise a strategy.

What should the prisoners' strategy be?

Certainly, the odds are better if they either:

All say the same number (100 chances of getting 1 number right) or,

Split up into groups of 2, 5, 10, 20, 25 (pick one) and each group guesses a different number that they can see.

Are they not?

[joshs]

inquiry, on Nov 20 2007, 03:03 PM, said:

Quote

If at least one prisoner guesses his number right, they are all released immediately. Otherwise, they will need to wait another year for another challenge.

with two prisoners the problem is trivial. One guesses 1, one guess 2, at least one of them has to be right, so they go free.

With the problem as stated, each prisoner guess a unique number from 1 to 100, at least one of them has to be right, so they all go free. Surely this is not so stupid to be that easy. The problem needs to be restated...

Ahh Ben, You are not even coming close to solving the problem even in the case of 2 prisoners.

You gave 2 people, and you had person A guess 1, and person B guess 2. If person A had 2 on his forehead, and person B has 1 on his forehead you lost.

Also, note the problem said that numbers can be assigned more then once (so not all numbers had to be used)...

[Echognome]

Oh ok. I get it now. It's not that we have to guess someone's number. We have to specifically guess our own number.

[han]

bid_em_up, on Nov 20 2007, 03:23 PM, said:

Trumpace, on Nov 20 2007, 12:06 PM, said:

On a Sunday morning, every prisoner will be assigned a number (integer) from 1 to 100 (inclusive), which will be written on his forehead. Any number may be assigned to an arbitrary number of prisoners (repetitions allowed!)

Every prisoner will see the numbers of the other 99, but won't see his own number. The prisoners then guess their own numbers simultaneously. (There will be a guard assigned to each prisoner to note down the guess: yes, it is a high security prison)

If at least one prisoner guesses his number right, they are all released immediately. Otherwise, they will need to wait another year for another challenge.

On the evening before, they are allowed to gather together and devise a strategy.

What should the prisoners' strategy be?

Certainly, the odds are better if they either:

All say the same number (100 chances of getting 1 number right) or,

Split up into groups of 2, 5, 10, 20, 25 (pick one) and each group guesses a different number that they can see.

Are they not?

No. It's not such an easy problem. If you have no idea how to attack the problem then I'd recommend looking at my hints and trying to solve it for 3 prisoners. Guessing the solution is unlikely to work.

[matmat]

my gut instinct is to pick a number i haven't seen on anyone else's forehead. I might change my mind if some significant fraction of my fellow inmates has the same number indicating that, possibly, the assignment procedure was non-random. (i've not done any math on any of this tho...)

[jonottawa]

Here's my solution. There may be other ways to solve it.

Spoiler

It's a similar but not identical problem to the dwarves.

If you add up the numbers of all the prisoners, the number you get must have 2 last digits, ranging from 01, 02, 03 up to 97, 98, 99, 00.

Assign numbers 1-100 to the prisoners in the private meeting beforehand. (These numbers are completely unrelated to the warden's numbers.)

Instruct prisoner#1 to guess that his number is the number that coincides with getting the grand total equal to ????01. So for example, if I was prisoner#1 and I added up everybody else's numbers from their forehead and got 1783, I would guess 18.

Instruct prisoner#2 to guess that his number is the number that coincides with getting the grand total equal to ????02

etc.

Whichever prisoner's prisoner-assigned # coincides with the last two digits of the grand total of all the warden-assigned #'s has successfully guessed his own warden-assigned number.

[bid_em_up]

The problem with this sort of solution is that "prisoners" are likely to be incapable of actually performing this kind of math.

(at least if they are criminal prisoners, anyway).

Which is why a complex solution like this, cannot be "right" or "practical", even if it works.

[joshs]

Hannie, on Nov 20 2007, 04:18 PM, said:

bid_em_up, on Nov 20 2007, 03:23 PM, said:

Trumpace, on Nov 20 2007, 12:06 PM, said:

On a Sunday morning, every prisoner will be assigned a number (integer) from 1 to 100 (inclusive), which will be written on his forehead. Any number may be assigned to an arbitrary number of prisoners (repetitions allowed!)

Every prisoner will see the numbers of the other 99, but won't see his own number. The prisoners then guess their own numbers simultaneously. (There will be a guard assigned to each prisoner to note down the guess: yes, it is a high security prison)

If at least one prisoner guesses his number right, they are all released immediately. Otherwise, they will need to wait another year for another challenge.

On the evening before, they are allowed to gather together and devise a strategy.

What should the prisoners' strategy be?

Certainly, the odds are better if they either:

All say the same number (100 chances of getting 1 number right) or,

Split up into groups of 2, 5, 10, 20, 25 (pick one) and each group guesses a different number that they can see.

Are they not?

No. It's not such an easy problem. If you have no idea how to attack the problem then I'd recommend looking at my hints and trying to solve it for 3 prisoners. Guessing the solution is unlikely to work.

But you wrote your hints in invisible ink....