Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Re: an alternate prisoners dilema.

  1. Feb 4, 2007 #1
    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?:smile:

    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?
     
    Last edited: Feb 4, 2007
  2. jcsd
  3. Feb 4, 2007 #2

    verty

    User Avatar
    Homework Helper

    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.
     
  4. Feb 4, 2007 #3
    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.
     
  5. Feb 4, 2007 #4

    verty

    User Avatar
    Homework Helper

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

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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. :frown:
     
    Last edited: Feb 4, 2007
  7. Feb 4, 2007 #6
    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.

    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.
     
    Last edited: Feb 4, 2007
  8. Feb 4, 2007 #7

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

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

    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. :grumpy: 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)
     
    Last edited: Feb 4, 2007
  9. Feb 4, 2007 #8

    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 doesnt 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.....
     
    Last edited: Feb 4, 2007
  10. Feb 4, 2007 #9

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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. :tongue: 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.
     
  11. Feb 5, 2007 #10
    You don't?:smile:

    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 :smile:

    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.

     
    Last edited: Feb 5, 2007
  12. Feb 5, 2007 #11

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
  13. Feb 5, 2007 #12
    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.:smile:
     
    Last edited: Feb 5, 2007
  14. Feb 5, 2007 #13
    Last edited: Feb 5, 2007
  15. Feb 5, 2007 #14
    Thanks for that.


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

    I'd like to add 1 in a million is not 100% it's [tex]\frac{1}{1000000}1=0.000001%[/tex]
     
    Last edited: Feb 5, 2007
  16. Feb 5, 2007 #15

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
    Last edited: Feb 5, 2007
  17. Feb 6, 2007 #16

    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?

     
    Last edited: Feb 6, 2007
  18. Feb 6, 2007 #17

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

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

    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. :grumpy:

    I never claimed AKG's was optimal.


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

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


    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.
     
    Last edited: Feb 6, 2007
  19. Feb 6, 2007 #18

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
  20. Feb 6, 2007 #19
    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
     
  21. Feb 6, 2007 #20

    cristo

    User Avatar
    Staff Emeritus
    Science Advisor

    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?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Re: an alternate prisoners dilema.
Loading...