prisoners

Discussion in 'Off-Topic' started by recca02, Apr 22, 2007.

  1. recca02

    Thread Starter Senior Member

    Apr 2, 2007
    1,211
    0
    here is my version of a puzzle i cud not remember but i think i can reproduce it to some extent. in case some one knows the question as well as the answer feel free to post.

    in a prison 21 ppl are held captive.
    the jailer gives them a conundrum (he happens to be the administrator of some site i cant remember--:D ----*apologies* )
    the condition he lays is:
    the prisoners can meet and plan in advance but they may not meet or be able to communicate afterwards.
    the prisoners will be taken to a closed room with two switches.
    each prisoner will have to toggle any one switch.
    the prisoners can be taken any number of times in any order.
    after any prisoner is sure that all twenty one have been given a chance to toggle the switch at least once, he may declare so and all will be freed.
    but if his declaration is incorrect all prisoners will be executed (cruel jailer:mad: ).

    can any one come up with a sure fire idea abt this.
    there are 21 lives at stake:) .
     
  2. Dave

    Retired Moderator

    Nov 17, 2003
    6,960
    144
    The cheek! :D

    Ok, do the switches start in a known initial state?

    Dave
     
  3. recca02

    Thread Starter Senior Member

    Apr 2, 2007
    1,211
    0
    no, but if proper planning is done, i dont think that wud be necessary,
    u can have that condition as granted though.
    actually speaking even i dont know the actual answer but i have figured a sure fire way.
     
  4. Dave

    Retired Moderator

    Nov 17, 2003
    6,960
    144
    I'm thinking if the switches are in an initial state the switches can represent a binary value - its now a case of creating a toggling sequence that can be decoded each time someone enters to ascertain if all 21 have been in the room and toggled the switch at least once. The problem is knowing what sequence would be suitable.

    Am I getting close?

    Dave
     
  5. recca02

    Thread Starter Senior Member

    Apr 2, 2007
    1,211
    0
    the only hint i can give u is the process can take a real long time.
    it depends on how the jailer decides to continue he may even cal them serially if he so desires and yet it may take a long time. in the meeting a leader has to be decided first and foremost.

    i didnt think of binary encoding or decoding , it may or may not be helpful depending on the approach.


    i can pm a better hint if you can tell me why wud some one write elf when he is abt to die :p
     
  6. Dave

    Retired Moderator

    Nov 17, 2003
    6,960
    144
    Ok, so encoding/decoding is not going to work - that is my normal approach to these kinds of problems (typical engineer!). I'll have a little think about this tomorrow, it is getting late here.

    If you want to provide hints, do it in the wider forum so others can see. I'll do the same with the "elf" hint in the other thread.

    Dave
     
  7. recca02

    Thread Starter Senior Member

    Apr 2, 2007
    1,211
    0
    sure thing, it was meant as a joke neways .
    btw, the 'leader' clue though seems obvious must not be overlooked.the whole game depends on him.

    one more thing, if i can come up with an answer it shud be child's play for everyone else,give it a try because it can be solved by trial and error method (hope the prisoners were given a fair trial after their error :) ) and of course by that it doesnt mean that u have to go to prison ;)
     
  8. Dave

    Retired Moderator

    Nov 17, 2003
    6,960
    144
    I am curious if this is one where there is a trick in the initial question.

    Dave
     
  9. recca02

    Thread Starter Senior Member

    Apr 2, 2007
    1,211
    0
    no,
    u dont need to read between the lines.
    if there was some sort of trickery i wud have stated so myself.
    no use giving ppl mental torture. :D
     
  10. Dave

    Retired Moderator

    Nov 17, 2003
    6,960
    144
    I am getting mental torture here! The two approaches I would normally take (analytical, or looking for the 'trick') are not applicable (or so it seems). Is this one of those that is so simple when you hear it, it is hard to believe others would not be able to get it?

    Dave
     
  11. recca02

    Thread Starter Senior Member

    Apr 2, 2007
    1,211
    0
    its not simple.
    let me give u my own example.
    i happen to have read this puzzle 3 years back. cudnt find an answer then.
    it featured in a newspaper column which gives ppl mental torture.
    just yesterday i came up with a solution since i had nothing else to do.
    to solve this one try simulating the condition in the mind.
    hope the answer i have found doesnt have a loophole else there will be a pretty hefty reward on my head :D .
     
  12. Dave

    Retired Moderator

    Nov 17, 2003
    6,960
    144
    Ok, so this begs the questions: Do the prisoners see each other after the initial discussion (I know they can't communicate)? And is the taking the prisoners into the room with the switches 'blind' from the other prisoners?

    Dave
     
  13. recca02

    Thread Starter Senior Member

    Apr 2, 2007
    1,211
    0
    no prisoner is able to see each other nor the switches except until he is taken to the room to toggle it.
    the whole discussion wud have else fallen apart.
    the first time i saw this question it seemed to be the hardest out there.
    but after u know the answer every question seems easier.
    trust me it isnt that easy.
     
  14. Dave

    Retired Moderator

    Nov 17, 2003
    6,960
    144
    This requires a board meeting at work!

    Dave
     
  15. recca02

    Thread Starter Senior Member

    Apr 2, 2007
    1,211
    0
    try thinking that the prisoners have all the time in the world.
    after all they need to ensure that everybody has toggled atleast once.
    one big hint
    the leader might have to visit the cell at least 21 times.
     
  16. Dave

    Retired Moderator

    Nov 17, 2003
    6,960
    144
    I hooked on there being an analyitical solution this (i.e. analytical way of getting a solution to prove how many times they have been through the room) - but I'm wrong aren't I?

    Dave
     
  17. recca02

    Thread Starter Senior Member

    Apr 2, 2007
    1,211
    0
    the solution is indeed analytical but doesnt require any binary algebra knowledge.
    after all which prisoner knows abt boolean equations and all that.
    its 4 am think i better hit the sack now.
     
  18. Dave

    Retired Moderator

    Nov 17, 2003
    6,960
    144
    Ok, thanks for the information. I did think that in the interests of technical accuracy that having some prisoners performing some encoding/decoding procedure is a little unrealistic!

    I will have a ponder tomorrow and have a concrete (read as pathetic) guess at an answer.

    Dave
     
  19. n9352527

    AAC Fanatic!

    Oct 14, 2005
    1,198
    4
    Here's a stab at the answer. The only way the prisoners would know that all of them had visited the room was to nominate someone to count. There's no way to encode 21 visits with two switches. I guess this is why they have to nominate a leader/counter.

    Now, the leader has to count that each prisoner had visited the room. There are two switches, so we will use one switch as an indicator of prisoner visit, and the other one as a dummy, because each prisoner has to toggle a switch during a visit.

    If initial positions of the switches were known, this would be easier. It'd go something like this for switch A initially off:

    During visit by the prisoner, except the leader:
    If A was off and you'd never toggled A on before, toggle A on. Otherwise toggle B.

    Then for each visit by the leader:
    If A was on, increment prisoner count and then toggle A off. Otherwise toggle B.

    Then just wait for the count to reach 20.

    The real problem is because the initial positions are not known. I haven't cracked it yet, still thinking :D

    Edit:

    Right, there has to be a way to let all prisoners know that switch A had been initialised first by the leader. i.e. the real counting process has to be done after the prisoner know that the leader had visited the room before.

    So, we add a condition that no prisoner was allowed to toggle switch A on unless he had seen switch A on once on a previous visit. The leader, then, had to let the prisoner know that he had visited the room before by toggling switch A on if it was off, or toggle switch A off if it was on and only increment the count if he didn't toggle switch A on on his previous visit.

    During visit by the prisoner, except the leader:
    If A was off and you'd never toggled A on before and you'd seen switch A on once before, toggle A on. Otherwise toggle B.

    Then for each visit by the leader:
    If A was off, toggle it on.
    If A was on, toggle A off. If he didn't toggle A on on his previous visit, increment prisoner count. Otherwise toggle B.

    Boy, this whole process would take a really really long time :D
     
  20. recca02

    Thread Starter Senior Member

    Apr 2, 2007
    1,211
    0
    damn u r good!
    now keep pondering abt the last condition but its rather easier.


    hope u wont mind if your answer was exsponged by a kind moderator.
    mr dave really wanted to solve this one.