Re: an alternate prisoners dilema.

[Schrodinger's Dog]

https://www.physicsforums.com/showthread.php?t=30021

Here's the thread, look at the last two pages, can anyone come up with a formula that anyone could learn it is so simple, that will lead with the suggestions here to an outcome that will in theory and on average mean that each prisoner is there for the least number of days.

I'm nowhere near competent enough to prove any mathematical theory this complex, but maybe you number crunchers could do it?

Feel free to use any of the suggestions or your own.

Does anyone know the solution, if there is one off the top of their heads?

 

[verty]

That question has been posted before. I think it relies on far too many bogus assumptions, like that the switch won't be fiddled by anyone else.

 

[Schrodinger's Dog]

That question has been posted before. I think it relies on far too many bogus assumptions, like that the switch won't be fiddled by anyone else.

Indeed, but let's assume that either way the switch could be fiddled with or not. What is the best solution? So if the switch is often played around with how can you compensate, and if of course by the very nature of the puzzle people want to get out of there ASAP and don't screw with there lives what is the result?

We are assuming that it is in the best interest of all 100 prisoners to act honestly, if you do you get out of prison quicker, and if there is a moron/s who doesn't play the game how can you account for him/her or them.

 

[verty]

Each person makes a scratch in the wall, when there are 100 scratches, they know. I think this relies on less dubious assumptions.

 

[Hurkyl]

A naïve information theory argument suggests that you'll need 10,000 days. It follows from the following hypotheses:

(1) When selected, you expect to get at most one bit of information
(2) You need 100 bits of information to guarantee everyone has been selected



On the other hand, after a few thousand days, the odds that someone hasn't been picked is so staggeringly low that it's virtually certain everyone has been picked.

 

[Schrodinger's Dog]

Each person makes a scratch in the wall, when there are 100 scratches, they know. I think this relies on less dubious assumptions.

No you can't do that as soon as you do the prison guards will fill in the scratch.

The whole point is, there is only one variable other than the prisoners and the guards. Otherwise it would make no sense to ask the question in the first place.

A naïve information theory argument suggests that you'll need 10,000 days. It follows from the following hypotheses:

(1) When selected, you expect to get at most one bit of information
(2) You need 100 bits of information to guarantee everyone has been selected
I'm trying to work on a stronger argument, but I'm having trouble getting a good estimate on the number of possible ways one can write a sequence of n numbers in the range [1, 100] such that each number is picked at least once.

Yes you are right, but with my scenarios it should be less on average, and a bright mathemetician should be able to work out a system? worry not no one has yet. I trust you guys might?

But read the original thread it gives you a way of making 100 less. we're looking at patterns here, and probability.

 

[Hurkyl]

Like I said, it was just an approximation, and it was naïve. (and you missed a correction) It's not usually easy to find theoretical minimums for problems like this.

One omission is that the selection process gives you, on average, 0.08 bits of information per day, which is a heck of a lot more than the 0.01 bits per day you get from the lightbulb. (Of course, it might not be useful information)



And AKG's solution is valid. It just takes roughly 10,200 days, on average, before the counter is able to make his announcement. The exact formula for the expected amount of time is:

10,000 + 100 * (1 + 1/2 + 1/3 + 1/4 + ... + 1/99)

 

[Schrodinger's Dog]

Like I said, it was just an approximation, and it was naïve. (and you missed a correction) It's not usually easy to find theoretical minimums for problems like this.

One omission is that the selection process gives you, on average, 0.08 bits of information per day, which is a heck of a lot more than the 0.01 bits per day you get from the lightbulb. (Of course, it might not be useful information)
And AKG's solution is valid. It just takes roughly 10,200 days, on average, before the counter is able to make his announcement. The exact formula for the expected amount of time is:

10,000 + 100 * (1 + 1/2 + 1/3 + 1/4 + ... + 1/99)

According to the maths professor who set the problem it isn't read the link. Do you think I'd of set it otherwise, the only valid answer is?

No ones got an answer yet...

AKG is wrong because it's not 100%. and it's a slow answer, even mine was quicker.

No it doesn't you are assuming that the counter will be chosen x amount if times, Read the link.

Guys we've already done this, read the link.

You can do it in less...

 

[Hurkyl]

I don't see anywhere in the thread where the OP suggests AKG's solution doesn't work.

Any solution assumes each person is eventually picked at least once. If you're going to reject AKG's solution on the grounds that we can't guarantee the counter gets picked enough times, you're going to have to reject any proposed solution on the grounds that we can't guarantee any particular individual gets picked at least once.

 

[Schrodinger's Dog]

I don't see anywhere in the thread where the OP suggests AKG's solution doesn't work.
Any solution assumes each person is eventually picked at least once. If you're going to reject AKG's solution on the grounds that we can't guarantee the counter gets picked enough times, you're going to have to reject any proposed solution on the grounds that we can't guarantee any particular individual gets picked at least once.

You don't?

No on the grounds that in order to posit an answer you must be 100% sure, he is wrong it's as simple as that

It doesn't work because the solution has to be 100% infalible, since every pick is random, the special chosen person could never be chosen in their lifetimes, leaving all the prisoners dead anyway. If he is chosen only once and someone screws up or messes with the system, everyone dies.

The answer is optimal, and infalible, I just don't have the maths moxie to know how to optimise any of my solutions.

If you've solved the problem, why doesn't the author of the problem agree? As the man in the example below says the reason is significant and also leads to a solution.

However, if it is indeed true, all prisoners are set free. Thus, the assertion should only be made if the prisoner is 100% certain of its validity.

Some time ago, Ilia Denotkine has posted the following problem on the CTK Exchange
There are 100 prisoners in solitary cells. There's a central living room with one light bulb; this bulb is initially off. No prisoner can see the light bulb from his or her own cell. Everyday, the warden picks a prisoner equally at random, and that prisoner visits the living room. While there, the prisoner can toggle the bulb if he or she wishes. Also, the prisoner has the option of asserting that all 100 prisoners have been to the living room by now. If this assertion is false, all 100 prisoners are shot. However, if it is indeed true, all prisoners are set free and inducted into MENSA, since the world could always use more smart people. Thus, the assertion should only be made if the prisoner is 100% certain of its validity. The prisoners are allowed to get together one night in the courtyard, to discuss a plan. What plan should they agree on, so that eventually, someone will make a correct assertion?

He then added a background to his question:


I have seen this problem on the forums, and here are some of the best solutions (to my opinion):

1.

At the beginning, the prisoners select a leader. Whenever a person (with the exception of the leader) comes into a room, he turns the lights on. If the lights are already on, he does nothing. When the leader goes into the room, he turns off the lights. When he will have turned off the lights 99 times, he is 100% sure that everyone has been in the room.
2.

wait 3 years, and with a great probability say that everyone has been in the room.

Does anyone know The optimal solution?

I have taken this problem from the www.ocf.berkeley.edu site, but I believe that you can find it on many others.

As I had a recollection of seeing this problem in [Winkler], I replied


The problem is indeed popular. It's even included in P. Winkler's Mathematical Puzzles, which is a recommended book in any event. Winkler also lists a slew of sources where the problem appeared, including ibm.com and a newsletter of the MSRI.

The solution is this:

The prisons select a fellow, say Alice, who will have a special responsibility. All other prisoners behave according to the same protocol: each turns the light off twice, i.e. they turn it off the first two times they find it on. They leave it untouched thereafter. Alice turns the light on if it was off and, additionally, counts the number of times she entered the room with the light off. When her count reaches 2n - 3 she may claim with certainty that all n prisoners have been to the room.

As it happened, I was wrong. This may be immediately surmised from Stuart Andersen's response. In my wonderment I contacted Peter Winkler who kindly set things straight for me. The formulation in his book is somewhat different, but this difference proves to be of major significance:


Each of n prisoners will be sent alone into a certain room, infinitely often, but in some arbitrary order determined by their jailer. The prisoners have a chance to confer in advance, but once the visits begin, their only means of communication will be via a light in the room which they can turn on or off. Help them design a protocol which will ensure that some prisoner will eventually be able to deduce that everyone has visited the room.

 

[Hurkyl]

You don't?

Nope. I did a search for Tigers2B1's name in that thread, and I did not find any post where he rejected a solution.

No on the grounds that in order to posit an answer you must be 100% sure, he is wrong it's as simple as that

In AKG's solution, given the conditions of the problem, the counter is 100% sure when he makes the announcement.

... person could never be chosen in their lifetimes, leaving all the prisoners dead anyway.

As I said, if this is grounds for rejecting a solution, then this problem is provably unsolvable. If any individual is never chosen in their lifetimes, the prisoners will all die.

 

[Schrodinger's Dog]

Nope. I did a search for Tigers2B1's name in that thread, and I did not find any post where he rejected a solution.In AKG's solution, given the conditions of the problem, the counter is 100% sure when he makes the announcement.As I said, if this is grounds for rejecting a solution, then this problem is provably unsolvable. If any individual is never chosen in their lifetimes, the prisoners will all die.

Yes. That is precisely it, the system must be 100% airtight. That's the point of the problem, it would be too easy to solve otherwise, your proof must be airtight. You must divise a system that will in 100% of cases result in the prisoners release, not in 99% of cases but 100/100 and optimal.

Otherwise I could of thought up a solution in five minutes.

 

[3trQN]

seems like a long winded von Neuman architecture with prisoners.

 

[Schrodinger's Dog]

seems like a long winded von Neuman architecture with prisoners.

Thanks for that.

With the one-counter solution, I wrote a simulator and ran it 100,000 times. Of course, this assumes that the prisoner assignment is totally arbitrary and the random numbers are "truly" random (no clustering, but evenly distributed).

Results:

0-999 days: 0 times
1000-1999 days: 0 times
2000-2999 days: 0 times
3000-3999 days: 0 times
4000-4999 days: 0 times
5000-5999 days: 0 times
6000-6999 days: 10 times
7000-7999 days: 459 times
8000-8999 days: 6806 times
9000-9999 days: 27676 times
10000-10999 days: 37769 times
11000-11999 days: 21085 times
12000-12999 days: 5461 times
13000-13999 days: 681 times
14000-14999 days: 52 times
15000-15999 days: 1 time

On average, that means you're looking at about 24 to 33 years before you're POSITIVE that everyone's been in the room. Being overly optomistic, you might actually wait 16 years. And there's about a 0.001% chance that you'll be waiting 42 years or more.

Now, comparaitvely, here's how many days it ACTUALLY took to get all 100 people in the room:

0-99 days: 0 times
100-199 days: 0 times
200-299 days: 409 times
300-399 days: 14543 times
400-499 days: 35987 times
500-599 days: 27511 times
600-699 days: 13046 times
700-799 days: 5353 times
800-899 days: 1998 times
900-999 days: 755 times
1000-1099 days: 266 times
1100-1199 days: 89 times
1200-1299 days: 33 times
1300-1399 days: 5 times
1400-1499 days: 3 times
1500-1599 days: 1 time
1600-1699 days: 1 time

So, if you wait 4 years and then assert that everyone's been in the room, you have around a 99.997% chance of being correct. That means chances are, you're pretty safe NOT using the technique, and just waiting, say, 5 years for a 99.9999% chance of safety, rather than 16-42 years for a 100% chance of safety.

DaveE

The chance has to be 100%, that's the point otherwise it's easy to solve. Now the only method I know that does this in an optimised and 100% situation is to have no counter, but everyone as a counter, the first person to get enough results to call the warden calls the warden, in the unlikely event that the counter is never chosen, here at least you will be 100% corrrect in your assumption not 99.9999996 but 100% as the question asks. This is the point.

You have to bear in mind in the one counter situation if the counter is never chosen, all prisoners will be dead before the counter can make an assumption.

http://www.cut-the-knot.org/Probability/LightBulbs.shtml

This would work of course, but is it optimal? For instance, this would also work, I think:

Alice counts the times she finds the light on, and ensures that it is always off when she leaves the room. Everyone else turns on the light the first time they find it off, and then never touches it again. This way, between visits of Alice, at most one prisoner will turn on the light, and no prisoner turns it on more than once. Therefore the number of times Alice finds the light on is no more than the number of different prisoners that have entered the room. Each prisoner knows he has been counted once he has turned the light on, since he is the only one who touched the switch since Alice last visited. When Alice counts to n-1, she knows everyone has visited the room.

What does optimal mean here? It could only reasonably mean that the prisoners are freed in the shortest time. So what is the expected time they must wait until Alice has counted to n-1? This is a rather elaborate calculation in probability, so the prisoners turn to the actuary (who is in prison for embezzlement) for some answers.

He explains that using Bayes theorem,
P(X|Y)·P(Y) = P(X&Y) = P(Y|X)·P(X)

and the linearity of expected value,
E(X|Y)·P(Y) + E(X|~Y)·P(~Y) = E(X)

you can calculate the expected time in prison like this:

Suppose Alice has just visited the room, and let K be the number of days that pass before her next visit (so she visits again K+1 days from now), let n be the number of prisoners, let c be the number of times she has found the light on so far, and let P(ON) and P(OFF) be the probabilities that she finds the light on or off on her next visit. Then E(K) = n - 1, P(K=k) = 1/n·((n-1)/n)k, P(K = k & OFF) = 1/n·(c/n)k, which are fairly obvious.

Summing the last formula over all k gives P(OFF) = 1/(n-c). Bayes theorem then gives P(K = k|OFF) = (1-c/n)·(c/n)k, and from this you can calculate E(K|OFF) = c/(n-c) and linearity gives

E(K|ON) = ((n-1)(n-c)-c/(n-c))/(n-c-1).

Now let m be the number of times Alice visits and L be the number of days that pass before she next finds it on. Each time she finds it is off, c does not change, so all the calculations regarding the time until her next visit also do not change.

Therefore, the expected number of days until she next finds the light on is found by summing over all possible m to get the expected total time wasted on visits where the light is off, plus the expected time for the one visit where it was on. This gives

E(L) = (1+E(K|ON))P(ON) + sum(m(1+E(K|OFF))P(OFF)m
= n(1/(n-c-1) - 1/(n-c) + 1 - 1/(n-c)2).

Now we know how long we expect to wait from count = c to count = c+1. Therefore, we must sum this up from c=0 to c=n-2 to find the total expected time E(T). The result is E(T) = n2 - n/(n-1) - a, where a = S(1/c2) from 2 to n. Putting n=100 into this gives 9935.5 days, which is 26.2 years.

But (continues the actuary) this is absurdly long to wait. Simple probability shows that we can be almost certain much sooner than this. The probability that on day d the count is c is P(c, d), which is obviously equal to P(c-1,d-1)·(1-(c-1)/n) + P(c, d-1)·(c/n). Of course, P(0, 0) = P(1, 1) = 1 and P(1,0) = 0, so we can recursively calculate the probability P(n, d). It turns out that P(100,1146) = 0.999, and P(100,1375) = 0.9999, P(100,1604) = 0.99999, and P(1833) = 0.999999. That means that in 3.14 years, we have a less than 1/1000 chance of failing, and in exactly 5 years and a week, we have less than one in a million chances of failing. I say we should wait 5 years and then say "let us out, we've all seen the light."

As they are about to kill Alice (who was already a member of Mensa) for coming up with a crazy plan to keep them in prison for 26 years, the game theorist (who is in prison for insider trading on the stock market) steps into point out that this is a losing move. If they kill her now she will never go into the room, and the warden will keep them here forever.

In the happy ending, they let Alice live, and they all get out of prison in 5 years. Strangely, they all decline to join Mensa, preferring to enter actuarial training.

Q: How can the prisoners tell, with certainty, that all 100 of them have visited the central living room with the light bulb.

The riddle: 100 prisoners are in solitary cells, unable to see, speak or communicate in any way from those solitary cells with each other. There's a central living room with one light bulb; the bulb is initially off. No prisoner can see the light bulb from his own cell. Everyday, the warden picks a prisoner at random, and that prisoner goes to the central living room. While there, the prisoner can toggle the bulb if he or she wishes. Also, the prisoner has the option of asserting the claim that all 100 prisoners have been to the living room. If this assertion is false (that is, some prisoners still haven't been to the living room), all 100 prisoners will be shot for their stupidity. However, if it is indeed true, all prisoners are set free. Thus, the assertion should only be made if the prisoner is 100% certain of its validity.

Before the random picking begins, the prisoners are allowed to get together to discuss a plan. So ---- what plan should they agree on, so that eventually, someone will make a correct assertion?

This is why your idea and all the others are dismissed, not because it isn't likely, but because it does not meet the criteria of the experiment, read the quote again as for why and how this leads to the only conclusion that a single counter or 99 counters is not viable, only all counters will be 100%. Run your tests with that, is it more or less viable? I think you already know the answer, it not only more quickly leads to a result, but it is 100%. This is why he asid he was wrong because quite simply he was wrong, but this leads to the solution, since no one online appears to have got this technicality.

There answer is different and I can assure you I didn't read it before I came up with mine, so my answer could also be correct, and in fact, if your lucky it's even more optimised. But their answer is to just wait five years, now what if you have both as a precursor, aren't you optimising the situation still further?

It's OK by diligence and actually reading and following up my own links I have an answer, thanks for all the contributions.

I'd like to add 1 in a million is not 100% it's $$\frac{1}{1000000}1=0.000001%$$

 

[Hurkyl]

Yes. That is precisely it, the system must be 100% airtight. That's the point of the problem, it would be too easy to solve otherwise, your proof must be airtight. You must divise a system that will in 100% of cases result in the prisoners release, not in 99% of cases but 100/100 and optimal.

Otherwise I could of thought up a solution in five minutes.

I repeat:

If there is a time limit, the problem has no solution.
If there is no time limit, AKG's solution is guarnateed to get the prisoners released.


If you disagree with my first point, then please demonstrate how to release the prisoners within a time limit of L, if prisoner #13 is never chosen until time L+1.

If you disagree with my second point, then please demonstrate how the guards may choose prisoners, within the constraints of the problem, so that AKG's method either gets the prisoners killed or leaves them eternally imprisoned.

 

[Schrodinger's Dog]

I repeat:

If there is a time limit, the problem has no solution.
If there is no time limit, AKG's solution is guarnateed to get the prisoners released.If you disagree with my first point, then please demonstrate how to release the prisoners within a time limit of L, if prisoner #13 is never chosen until time L+1.

If you disagree with my second point, then please demonstrate how the guards may choose prisoners, within the constraints of the problem, so that AKG's method either gets the prisoners killed or leaves them eternally imprisoned.

No it isn't if the choser is never chosen then it is not guaranteed, because all the prisoners might be dead before he gets chosen, if you have an issue take it up with the professor who proposed the question and says you are wrong because it's not optimised. To be honest I'm not sure how more clear I can make this 1 in a million is not 100% anyway. My solution is to have 100 counters plus the original light switch solution plus the five years probability, and thus it is 100%. The first prisoner to be chosen 100 times and to see the switches all down is 100% assured of being right. Time limit is their lifetimes. Otherwise my original lateral solution is true. But what are the chances that no one gets chosen 100 times before they die? Say in 50 years average? Now add in the fact that you have a five year probability solution?

The riddle: 100 prisoners are in solitary cells, unable to see, speak or communicate in any way from those solitary cells with each other. There's a central living room with one light bulb; the bulb is initially off. No prisoner can see the light bulb from his own cell. Everyday, the warden picks a prisoner at random, and that prisoner goes to the central living room. While there, the prisoner can toggle the bulb if he or she wishes. Also, the prisoner has the option of asserting the claim that all 100 prisoners have been to the living room. If this assertion is false (that is, some prisoners still haven't been to the living room), all 100 prisoners will be shot for their stupidity. However, if it is indeed true, all prisoners are set free. Thus, the assertion should only be made if the prisoner is 100% certain of its validity.

Before the random picking begins, the prisoners are allowed to get together to discuss a plan. So ---- what plan should they agree on, so that eventually, someone will make a correct assertion?

 

[Hurkyl]

No it isn't if the choser is never chosen then it is not guaranteed, because all the prisoners might be dead before he gets chosen

Which is why I say, if there is a time limit, this problem is unsolvable.

if you have an issue take it up with the professor who proposed the question

You're the one who made the thread here. You are the one arguing the point. Thus, I'll take the issue up with you, thank you very much.

and says you are wrong because it's not optimised.

I never claimed AKG's was optimal.

To be honest I'm not sure how more clear I can make this 1 in a million is not 100% anyway.

Where are you getting "1 in a million" from?

My solution is to have 100 counters plus the original light switch solution plus the five years probability, and thus it is 100%.

What if one of the prisoners is never chosen in their lifetimes?
And if you have a "probability" solution, then it's not 100%.


I will repeat my point one last time.

If there is a time limit, this problem has no solution. You cannot guarantee that prisoner #26 will ever be picked before the time limit is up, and thus you cannot guarantee the prisoners' escape.

If there is not a time limit, AKG's solution guarantees their release: the counter cannot make his announcement before all 100 prisoners have entered the room.

 

[Hurkyl]

I see the original thread is still active: is there merit in having this topic in two threads? If not, I'm going to close this one.

 

[davee123]

According to the maths professor who set the problem it isn't read the link.

Ok. The math professor's solution WAS wrong. But his solution is NOT the same as AKG's solution. The solution he posted:

"The prisons select a fellow, say Alice, who will have a special responsibility. All other prisoners behave according to the same protocol: each turns the light off twice, i.e. they turn it off the first two times they find it on. They leave it untouched thereafter. Alice turns the light on if it was off and, additionally, counts the number of times she entered the room with the light off. When her count reaches 2n - 3 she may claim with certainty that all n prisoners have been to the room."

Which he agrees is wrong. Then, he receives the following, which he acknowledges is a correct, but possibly not optimal solution:

"Alice counts the times she finds the light on, and ensures that it is always off when she leaves the room. Everyone else turns on the light the first time they find it off, and then never touches it again. This way, between visits of Alice, at most one prisoner will turn on the light, and no prisoner turns it on more than once. Therefore the number of times Alice finds the light on is no more than the number of different prisoners that have entered the room. Each prisoner knows he has been counted once he has turned the light on, since he is the only one who touched the switch since Alice last visited. When Alice counts to n-1, she knows everyone has visited the room."

Notice that the latter solution (the correct one) matches AKG's solution.

DaveE

 

[cristo]

Thus, the assertion should only be made if the prisoner is 100% certain of its validity.

Schrodinger's Dog: In your post above you appear to be highlighting this point, and using it to justify why AKG's solution is incorrect. However, in AKG's solution, the prisoners will only declare that they have all been in when they are 100% sure! If the counter never enters, then they will not declare that they have all been in, hence this is a correct solution. It seems to me that in your solution you do not have 100% certainty, since you are talking about declaring when the prisoners are x% certain.

In all solutions to this problem, if a person does not enter the room, then the riddle can't be solved; this is clear, isn't it?

 

[Schrodinger's Dog]

Which is why I say, if there is a time limit, this problem is unsolvable. You're the one who made the thread here. You are the one arguing the point. Thus, I'll take the issue up with you, thank you very much. I never claimed AKG's was optimal.
Where are you getting "1 in a million" from?

But (continues the actuary) this is absurdly long to wait. Simple probability shows that we can be almost certain much sooner than this. The probability that on day d the count is c is P(c, d), which is obviously equal to P(c-1,d-1)·(1-(c-1)/n) + P(c, d-1)·(c/n). Of course, P(0, 0) = P(1, 1) = 1 and P(1,0) = 0, so we can recursively calculate the probability P(n, d). It turns out that P(100,1146) = 0.999, and P(100,1375) = 0.9999, P(100,1604) = 0.99999, and P(1833) = 0.999999. That means that in 3.14 years, we have a less than 1/1000 chance of failing, and in exactly 5 years and a week, we have less than one in a million chances of failing. I say we should wait 5 years and then say "let us out, we've all seen the light."

What if one of the prisoners is never chosen in their lifetimes?
And if you have a "probability" solution, then it's not 100%. I will repeat my point one last time.If there is a time limit, this problem has no solution. You cannot guarantee that prisoner #26 will ever be picked before the time limit is up, and thus you cannot guarantee the prisoners' escape.

Not true I explain this below.

If there is not a time limit, AKG's solution guarantees their release: the counter cannot make his announcement before all 100 prisoners have entered the room.

But this is unrealistic for the reasons given below.

And this is also wrong, since I didn't write the rules for the puzzle the professor did the answer is what he gave, all I'm saying is that this is not 100% either but 99.99999999% etc but obviously for the experiment this is close enough. However I merely suggested adding both systems in case the counter system got lucky.

Schrodinger's Dog: In your post above you appear to be highlighting this point, and using it to justify why AKG's solution is incorrect. However, in AKG's solution, the prisoners will only declare that they have all been in when they are 100% sure! If the counter never enters, then they will not declare that they have all been in, hence this is a correct solution. It seems to me that in your solution you do not have 100% certainty, since you are talking about declaring when the prisoners are x% certain.

In all solutions to this problem, if a person does not enter the room, then the riddle can't be solved; this is clear, isn't it?

Well there also wrong because it's not optimised, and it still doesn't make the solution 100% from the point of view of the prisoners, ie what is the best solution possible which will ensure there release in the minimum possible time. The answer is 3 years or if you want 100% then the alternate counter system, or both if you want the best possible solution, given that the counter system may get lucky and your out before 3 years.

Ok. The math professor's solution WAS wrong. But his solution is NOT the same as AKG's solution. The solution he posted:

"The prisons select a fellow, say Alice, who will have a special responsibility. All other prisoners behave according to the same protocol: each turns the light off twice, i.e. they turn it off the first two times they find it on. They leave it untouched thereafter. Alice turns the light on if it was off and, additionally, counts the number of times she entered the room with the light off. When her count reaches 2n - 3 she may claim with certainty that all n prisoners have been to the room."

Which he agrees is wrong. Then, he receives the following, which he acknowledges is a correct, but possibly not optimal solution:

"Alice counts the times she finds the light on, and ensures that it is always off when she leaves the room. Everyone else turns on the light the first time they find it off, and then never touches it again. This way, between visits of Alice, at most one prisoner will turn on the light, and no prisoner turns it on more than once. Therefore the number of times Alice finds the light on is no more than the number of different prisoners that have entered the room. Each prisoner knows he has been counted once he has turned the light on, since he is the only one who touched the switch since Alice last visited. When Alice counts to n-1, she knows everyone has visited the room."

Notice that the latter solution (the correct one) matches AKG's solution.

DaveE

And note it is also wrong and the explanation of why is given above.

I see the original thread is still active: is there merit in having this topic in two threads? If not, I'm going to close this one.

Fine by me.

 

[cristo]

and it still doesn't make the solution 100% from the point of view of the prisoners, ie what is the best solution possible which will ensure there release in the minimum possible time.

Where does the problem state that the solution must be proved to be optimal?

The only clause is that the prisoners must be 100% certain before they make a claim. In AKG's they are.

My counter-statement is always the same, and is never answered. Thus, I shall bow out of this discussion, since it is going nowhere!

 

[Schrodinger's Dog]

Where does the problem state that the solution must be proved to be optimal?

The only clause is that the prisoners must be 100% certain before they make a claim. In AKG's they are.

My counter-statement is always the same, and is never answered. Thus, I shall bow out of this discussion, since it is going nowhere!

I showed you this in the link? Did anyone read it? Using Bayes theorem the probability that all are picked is in three years at 1/1000 probability and 1/1000000 at 5 years. thus the light switch answer is wrong, all you need do to optimise your time of release is to wait 5 years. Why would a prisoner chose one system that means waiting an average of 26 years over one that means you're all out in 5? Obviously in maths world the answer is correct but in a real world situation, which is kind of the point of having real people it is not right. The most unarguably correct answer taking the lifespans of the prisoners into account is to wait until everyone has died but one prisoner, but this is hardly a valid solution although it is correct, there is both a solution with or without a time limit though if you get chosen 100 times after everyone has died then you can be sure that you're getting out by simply using the method of the light switch up, if no one changes it to down as in whatver solution then you know you are alone.

This is a logic problem or an applied maths problem, not a pure maths problem.

 

[cristo]

AKG's solution satisfies the conditions as stated in the problem statement in the original post. Therefore it is a solution to the riddle.

Does the fact that there happens to be another solution that takes less time for the prisoners to be free mean that AKG's solution is incorrect?

That is my point!

 

[Schrodinger's Dog]

AKG's solution satisfies the conditions as stated in the problem statement in the original post. Therefore it is a solution to the riddle.

Does the fact that there happens to be another solution that takes less time for the prisoners to be free mean that AKG's solution is incorrect?

That is my point!

I never said that I just said it's flawed and thus wrong from the point of view of the prisoners, reality is second place to mathematics though obviously. I don't see why it is correct if there's is a chance it is not 100% anyway, so I guess it's a technicality.

Look I'm honestly not trying to annoy anyone I just thought it would be fun to think about the limitations of the solutions and how logically they do not meet the criteria of the OP on that thread. Obviously it isn't fun, and obviously no ones interested so as suggested let's just agree to disagree and close the thread.

The prisoner must be 100% sure he is right.