Prisoners problem....

[psuresh1982]

Hi James,

We are all waiting for the solution for this problem....Almost 10 days over...

--------------------
suresh

[jamesravid]

Sorry for the delay to post my solution.

Let us assume that the sum of all number assigned to 100 prisoners is S(P) and the number assigned to the first prisoner is n1, the number to the second prisoner is n2 and so on.

That is, S(P) = n1 +n2+n3 +...+n100.

And it is obvious that Mod(S(P),100) ranges between 0-99.

Here is my strategy that must work in all cases,

The first prisoner always assumes that "Mod(S(P),100)" is going to be 0
The second prisoner assumes that "Mod(S(P),100)" is going to be 1
so on...

It is certain that exactly one of the 100 prisoners is right with his guess.

Now, The first prisoner in his turn
1. Add all numbers assigned to rest of the people (n2+n3+...+n100). Let us say the value is S(p1).
2. Find "Mod(s(p1),100)". Let us say he has got the number np1.
3. Find 100 -np1, which is going to be his guess. Since he guess that "Mod(S(P),100)" is going to be 0

Let be brief this with an example.

Let use assume that he has got 5078 at the end of first step

Step2 mod(5078,100) = 78
Step3 100 -78 = 22
Hence the guess will be made by the first prisoner is 22.

Now, The second prisoner
1. Add all numbers assigned to rest of the people (n1+n3+...+n100). Let us say the value is S(p2).
2. Find "Mod(s(p2),100)". Let us say he has got the number np2.
3. Find 100+1 -np2, which is going to be his guess.

Example if the second person got 5078 at the end of first step then his guess would be 100 + 1 -78 = 23.


All other 99 prisoners also will make their guess as described above. It is obvious that one their guess on value of "Mod(S(P),100)" must be right. Hence that prisoner's guessing on the number assigned him will also be right.