|
I have another puzzle to hopefully satisfy the intellectual appetite of the Team Liquid community. There are actually two versions of this puzzle, the easier one and the harder one. You could jump to the harder one if you don't want any hints, but for most people I think solving the easier one first is better.
+ Show Spoiler [Easier Version] +
There are 2 prisoners who have both been sentenced to life in prison. They are each going to be placed in solitary confinement(separate cells, they cannot communicate or see each other at all).
There are 100 guards working at this prison. Every day, each cell is guarded by one of the guards. If possible, both cells must be guarded. Also, a guard would prefer not to guard the same cell on consecutive days.
Lucky for the prisoners, there is a way for them to be released from prison.
Each prison cell's walls are painted either white or black. If either prisoner can successfully guess the color of the other prisoner's cell, then both will be freed. If either guesses wrong, they both die.
Every single day, the prisoners can do one of three things:
1) Talk to the guard. If the prisoner does this, the guard will be very offended and will never guard this prisoner's cell again.
2) Tell the guard what he thinks the color of the other prisoner's cell is. If the prisoner guesses correct, they both go free. Otherwise, they both die.
3) Do nothing.
As is usual with these kinds of problems, the prisoners have time beforehand to discuss their strategy. Can you think of a strategy that the prisoners can use to guarantee their freedom?
Clarifications
1) The priority of rules for the guards is as follows (first being highest priority):
----If a guard has been talked to, he will never guard that cell again
----If there is no other guard available to guard a cell, he will guard it.
----If the guard has guarded that cell the day before, he will not guard it today.
2) It is possible for a prisoner's cell to be completely unguarded on a day. For example, if the prisoner has talked to all 100 guards, then there will be no more guards left who are willing to guard him. This also means that the prisoner can no longer guess because there are no guards available to listen to him.
+ Show Spoiler [Harder Version] +
There are 2 prisoners who have both been sentenced to life in prison. They are each going to be placed in solitary confinement(separate cells, they cannot communicate or see each other at all).
There are 100 guards working at this prison. Every day, each cell is guarded by one of the guards. If possible, both cells must be guarded. Also, a guard would prefer not to guard the same cell on consecutive days.
Lucky for the prisoners, there is a way for them to be released from prison.
Each guard has an astrological sign (there are 12 astrological signs). If either prisoner can successfully guess the sign of the guard that is currently guarding them, then both will be freed. If either guesses wrong, they both die.
Every single day, the prisoners can do one of three things:
1) Ask the guard what his sign is. If the prisoner does this, the guard will tell you, but will also become very offended and will never guard this prisoner's cell again.
2) Guess the guard's astrological sign. If the prisoner guesses correct, they both go free. Otherwise, they both die.
3) Do nothing.
As is usual with these kinds of problems, the prisoners have time beforehand to discuss their strategy. Can you think of a strategy that the prisoners can use to guarantee their freedom?
Clarifications
1) The priority of rules for the guards is as follows (first being highest priority):
----If a guard has been asked his sign by a prisoner, he will never guard that prisoner's cell again.
----If there is no other guard available to guard a cell, he will guard it.
----If the guard has guarded that cell the day before, he will not guard it today.
2) It is possible for a prisoner's cell to be completely unguarded on a day. For example, if the prisoner has talked to all 100 guards, then there will be no more guards left who are willing to guard him. This also means that the prisoner can no longer guess because there are no guards available to listen to him.
3) A prisoner is only allowed to guess the sign of the guard that is currently guarding him.
|
<3 puzzles! Have to skip sc2 for a bit now tho ;(
|
I am assuming the prisoners can differentiate between the different guards?
+ Show Spoiler [Easier version] +Both prisoners talk to the guards for 49 days, thus chasing away 98 of the guards and leaving 2 of them.
On the 50th day, prisoner A will talk to the guard if his wall is white, but not talk if his wall is black. Prisoner B will do nothing.
On the 51st day, if prisoner B has no guard, he knows that A's wall is white, since A's guard on the 50th day will have ran off, and B's guard will go to A. If the guards changed, prisoner A's wall is black and B will know, thus freeing them.
If A's wall is white, B will tell the guard on the 52nd day.
|
Harder version is so difficult. I think I'm going to have to try working out the easier version first.
|
On October 08 2010 18:07 Vinnesta wrote:I am assuming the prisoners can differentiate between the different guards? + Show Spoiler [Easier version] +Both prisoners talk to the guards for 49 days, thus chasing away 98 of the guards and leaving 2 of them. On the 50th day, prisoner A will talk to the guard if his wall is white, but not talk if his wall is black. Prisoner B will do nothing. On the 51st day, if prisoner B has no guard, he knows that A's wall is white, since A's guard on the 50th day will have ran off, and B's guard will go to A. If the guards changed, prisoner A's wall is black, and B will know.
If A's wall is white, B will tell the guard on the 52nd day.
If a prisoner talks to a guard, that guard will only stop guarding that one prisoner, not both prisoners.
|
Vatican City State1176 Posts
in the hard version, under clarification 1), what do you mean with
"----If there is no other guard available to guard a cell, he will guard it."
most likely not important, but still
|
On October 08 2010 18:07 Vinnesta wrote:I am assuming the prisoners can differentiate between the different guards? + Show Spoiler [Easier version] +Both prisoners talk to the guards for 49 days, thus chasing away 98 of the guards and leaving 2 of them.
On the 50th day, prisoner A will talk to the guard if his wall is white, but not talk if his wall is black. Prisoner B will do nothing.
On the 51st day, if prisoner B has no guard, he knows that A's wall is white, since A's guard on the 50th day will have ran off, and B's guard will go to A. If the guards changed, prisoner A's wall is black and B will know, thus freeing them.
If A's wall is white, B will tell the guard on the 52nd day.
But I thought the prisoner's can't talk to each other?
+ Show Spoiler +If I was the prisoner, I'll just randomly guess the other guy's colour because I really can't find a solution.
50% chance of being freed! :D
Edit: Nevermind, didn't really read the questions carefully XD
I think the dude go it though
|
On October 08 2010 18:11 Sadir wrote:
in the hard version, under clarification 1), what do you mean with
"----If there is no other guard available to guard a cell, he will guard it."
most likely not important, but still
Suppose there's only 1 guard willing to guard prisoner A, while there are plenty of guards willing to guard prisoner B. In this scenario, the same guard will keep guarding prisoner A, even though he would prefer to switch.
|
+ Show Spoiler +so he could do nothing until he noticed a guard missing
one if by land (white!)
two if by sea (black!)
if he noticed two missing from his rotation, it's black
if he noticed one missing from his rotation, it's white
|
no idea on the harder version whatsoever
please dont keep me up for hours
|
On October 08 2010 18:07 Vinnesta wrote:I am assuming the prisoners can differentiate between the different guards? + Show Spoiler [Easier version] +Both prisoners talk to the guards for 49 days, thus chasing away 98 of the guards and leaving 2 of them.
On the 50th day, prisoner A will talk to the guard if his wall is white, but not talk if his wall is black. Prisoner B will do nothing.
On the 51st day, if prisoner B has no guard, he knows that A's wall is white, since A's guard on the 50th day will have ran off, and B's guard will go to A. If the guards changed, prisoner A's wall is black and B will know, thus freeing them.
If A's wall is white, B will tell the guard on the 52nd day.
this is assuming that they go in order
|
+ Show Spoiler + easy version: the cellmates before going in (assuming they know all the rules) decide that one of them is the 'talker' whilst the other is the 'thinker'.
The talkers job is simple, he talks to 99 of the guards if his cell is white, if it is black he doesnt talk at all, the thinkers job is pretty easy too, he waits 100 days, and then talks to 99 guards.
What this accomplishes is that the 'talker' prisoner always has that 1 guard left if he's in a white room, and due to the 'rules' that one guard must always guard him despite his preferences, so after 'thinker' gets rid of his 99 after 200 days or w/e, this one guard begins swapping back and forth if 'talker' is in a white room, at which point thinker knows the colour of both rooms and gets them free.
If however 'talker' is in a black room, and has never talked, the one guard 'thinker' didnt talk to is always stationed at his room, allowing 'thinker' to realize that 'talker' must be in a black room, at which point he knows the colour of both rooms.
|
i was just assuming that you could 98 or 99 it and then follow by the other guy talking to all 100
your method is pretty good, i didn't think about having to get two right
|
On October 08 2010 18:17 Bill Murray wrote:+ Show Spoiler +so he could do nothing until he noticed a guard missing
one if by land (white!)
two if by sea (black!)
if he noticed two missing from his rotation, it's black
if he noticed one missing from his rotation, it's white
Clarification: You cannot assume anything about the order of the guards. For example, if there are 3 guards available to guard prisoner A, he could very easily see the following:
1 2 1 2 1 2 ....
|
On October 08 2010 18:19 Ftrunkz wrote:+ Show Spoiler + easy version: the cellmates before going in (assuming they know all the rules) decide that one of them is the 'talker' whilst the other is the 'thinker'.
The talkers job is simple, he talks to 99 of the guards if his cell is white, if it is black he doesnt talk at all, the thinkers job is pretty easy too, he waits 100 days, and then talks to 99 guards.
What this accomplishes is that the 'talker' prisoner always has that 1 guard left if he's in a white room, and due to the 'rules' that one guard must always guard him despite his preferences, so after 'thinker' gets rid of his 99 after 200 days or w/e, this one guard begins swapping back and forth if 'talker' is in a white room, at which point thinker knows the colour of both rooms and gets them free.
If however 'talker' is in a black room, and has never talked, the one guard 'thinker' didnt talk to is always stationed at his room, allowing 'thinker' to realize that 'talker' must be in a black room, at which point he knows the colour of both rooms.
Congratulations. You have solved the easy version.
|
I'm going to sleep. Good luck with the hard version. I'll give clarifications when I wake up if necessary.
Edit: lol accidentally tripled posted.
|
|
|
omfg at hard version, braintstorming some ideas right now and not getting very far haha.
edit 1:OMG MY 2000TH POST NOOOOOOOO.
atleast im a sexy dt now.
edit 2: joke answer: if the a guard says leo he throws his show at their face hard enough to leave a bruise, allowing the other guy to say leo when he comes around.
|
argggggggggggggggggghhhhhh hard version.
nuts,
seems impossible cuz its 1 out of 12, and noway of knowing the guard's sign without asking.
going to think while sleep.
|
yeah, going completely round in circles and getting nowhere on hard, this is doing my head in, not enough IQ...
edit: I give up, im getting to that "its impossible fuck it" point in my head, haha. The thinking im up to is that one guy has to stop talking to guards at some point because a guard gives a certain answer, however I'm unsure as to how that helps the other guy, but its the only way of conveying any sort of information between the 2, which is what the problems all about... I just have no idea at what point logically makes sense for him to stop talking and to have the other guy figure it out based off that.
|
i was thinking you could do something if a person got the same sign twice in a row, but there would be a % against that even happening
|
Potential Hard Solution:
+ Show Spoiler +- P1 and P2 devise a numbering scheme for each astrological sign, assigning each a value between 1 and 12 (inclusive).
- P1 eliminates 99 guys, sums up the values of each astrological signs and divides it by 12, remembering the remainder M1. If M1 is 0 he will remember 12 instead.
- At this point P1 now sees the same guard G1 every day. P2 will never again see G1 until P1 chooses.
- P2 waits 99 days from the beginning and begins his own purging, eliminating 98 guards and while summing and dividing similarly for M2.
- P1 and P2 will now each see their own guards each day, G1 and G2 respectively.
- P1, having waited 98 days after his own purging, now waits M1 days and finally eliminates G1. P2 does nothing now except count days. Note that P2 will be guaranteed to see G2 at least once in this time.
- P2 will see G1 the day after, due to the priority rules. Having seen G2 and being able to tell G1 and G2 apart, he will have figured out M1, having counted the days since his purging ended.
- Since S1 is the modulo sum of every guard's sign except G1, and S2 is the modulo sum sign of every guard's sign except G1 and G2, their difference (using modular arithmetic) is the number corresponding to G2's sign.
- Using this information P2 can correctly guess G2's sign the following day.
+ Show Spoiler +
|
On October 08 2010 18:52 FatChicksUnited wrote:Potential Hard Solution: + Show Spoiler +- P1 and P2 devise a numbering scheme for each astrological sign, assigning each a value between 1 and 12 (inclusive).
- P1 eliminates 99 guys, sums up the values of each astrological signs and divides it by 12, remembering the remainder M1. If M1 is 0 he will remember 12 instead.
- At this point P1 now sees the same guard G1 every day. P2 will never again see G1 until P1 chooses.
- P2 waits 99 days from the beginning and begins his own purging, eliminating 98 guards and while summing and dividing similarly for M2.
- P1 and P2 will now each see their own guards each day, G1 and G2 respectively.
- P1, having waited 98 days after his own purging, now waits M1 days and finally eliminates G1. P2 does nothing now except count days. Note that P2 will be guaranteed to see G2 at least once in this time.
- P2 will see G1 the day after, due to the priority rules. Having seen G2 and being able to tell G1 and G2 apart, he will have figured out M1, having counted the days since his purging ended.
- Since S1 is the modulo sum of every guard's sign except G1, and S2 is the modulo sum sign of every guard's sign except G1 and G2, their difference (using modular arithmetic) is the number corresponding to G2's sign.
- Using this information P2 can correctly guess G2's sign the following day.
whoa, this is pretty mathematical but i understand the idea behind what you've done here, that's pretty cool and i would've never figured this out, gj (asuming you're correct :D)
|
Vatican City State1176 Posts
Potential Hard Solution: + Show Spoiler +- P1 and P2 devise a numbering scheme for each astrological sign, assigning each a value between 1 and 12 (inclusive).
- P1 eliminates 99 guys, sums up the values of each astrological signs and divides it by 12, remembering the remainder M1. If M1 is 0 he will remember 12 instead.
- At this point P1 now sees the same guard G1 every day. P2 will never again see G1 until P1 chooses.
- P2 waits 99 days from the beginning and begins his own purging, eliminating 98 guards and while summing and dividing similarly for M2.
- P1 and P2 will now each see their own guards each day, G1 and G2 respectively.
- P1, having waited 98 days after his own purging, now waits M1 days and finally eliminates G1. P2 does nothing now except count days. Note that P2 will be guaranteed to see G2 at least once in this time.
- P2 will see G1 the day after, due to the priority rules. Having seen G2 and being able to tell G1 and G2 apart, he will have figured out M1, having counted the days since his purging ended.
- Since S1 is the modulo sum of every guard's sign except G1, and S2 is the modulo sum sign of every guard's sign except G1 and G2, their difference (using modular arithmetic) is the number corresponding to G2's sign.
- Using this information P2 can correctly guess G2's sign the following day.
pretty damn impressive really, I got to the situation with the P1-G1 and P2-G2 (while G1 possible as well), but the information handling....puh...I couldnt think of how to solve this
pretty good 
chapeau
EDIT: I have to rethink that, I am not sure any more if I get it =)
EDIT2: ok I definitely got it now hehe
|
Can the prisoners differentiate between the guards without talking to them? I assumed they can't since they are in solitary confinement.
If they can differentiate are they able to agree upon a unique way to number them in the strategy phase? I mean in a way that once they are imprisoned then they will know when they are guarded by guard #1 or guard #38.
|
How I arrived at the solution:
+ Show Spoiler +I can't take credit actually. A few months ago Slithe or someone else put another puzzle of similar nature up, and the solution also was to encode information using modular arithmetic. Reading about it a few months ago totally blew my mind my as well  .
|
they could both eliminate all but 2 guards
prisoner A could dismiss one, and depending on the sign, wait 1-12 days to dismiss the last guard. They would know when this was occuring, because the guards would have a gap in between when they guarded the prisoners.
They eliminate down to 2 guards. At that point it would be 1, 2, 1, 2, 1, 2, 1, 2 for them both
when the prisoner dismisses the last guard, it would go from 1, 0 , 1, 0, to 1, 1, 1, 1, and he could correspond it with days of the gap relating to sign, because he would go back to 1, 2, 1, 2. The other prisoner wouldn't have a guard to guess, and would therefore "not get it wrong"
When he dismisses one, where the guards switch, the other guard will be stuck at his cell everyday, though he doesn't want to be stuck there whatsoever. when he waits the corresponding amount of days to dismiss him, the other prisoner will actually gain a guard.
He would know said guard's sign based upon silent communication of days, and the other dude wouldn't even have a guard to guess and get wrong.
So when he dismisses the guard, they will both be locked on the prisoner
he waits 1 day for ares, 12 days for pisces
on the 13th day, prisoner 2 would know said guard was pisces, for instance, because he would be back in rotation at his cell with the other guard whose sign he doesn't know
|
Hard solution perhaps (lacking mathematical explantion)
+ Show Spoiler +
If there are 100 guards and they must answer what their sign is the first time then that is a positive way of knowing one guards sign.
Also they are not to guard the same prisoners cell after that, unless no one else is available.
The prisoners would have to agree on a sign that when they heard it they would start the count.
This being said if on the first day one prisoners would ask the guards what their signs are and it was Leo.. Well heres and example on the first day to make things easier.
In the event that Leo is answered the day count starts at one. Now with 100 guards both guarding each cell when possible it will give you 54 days without a guard being repeated on that prisoner. On the 55th day the prisoner who did not ask the question on the first day would be guarded by the guard that guarded the other prisoner on the first day. Making the other prisoner positive that Leo is his sign.
Perhaps this only works if the sign is hit on the first day however.. but that would still give the prisoners a 1 and 6 shot I believe.
I'm not sure if the rotation I have in this solution is how it has to work, but i don't see it stated otherwise, so in this scenario it would
Either way I'm way too tired to try and work this out.. This was just what I initial thought I might read some of the other spoilers to see what other people have come up with
Bah nvm mine.. it relies on them speaking to each other
|
i hope my theory isn't swiss cheese
|
On October 08 2010 19:19 Bill Murray wrote:
They eliminate down to 2 guards. At that point it would be 1, 2, 1, 2, 1, 2, 1, 2 for them both
You can't guarantee that the same two guards are left for each prisoner. P1 could be left with G1 and G2 and P2 left with G3 and G4.
|
On October 08 2010 18:52 FatChicksUnited wrote:Potential Hard Solution: + Show Spoiler +- P1 and P2 devise a numbering scheme for each astrological sign, assigning each a value between 1 and 12 (inclusive).
- P1 eliminates 99 guys, sums up the values of each astrological signs and divides it by 12, remembering the remainder M1. If M1 is 0 he will remember 12 instead.
- At this point P1 now sees the same guard G1 every day. P2 will never again see G1 until P1 chooses.
- P2 waits 99 days from the beginning and begins his own purging, eliminating 98 guards and while summing and dividing similarly for M2.
- P1 and P2 will now each see their own guards each day, G1 and G2 respectively.
- P1, having waited 98 days after his own purging, now waits M1 days and finally eliminates G1. P2 does nothing now except count days. Note that P2 will be guaranteed to see G2 at least once in this time.
- P2 will see G1 the day after, due to the priority rules. Having seen G2 and being able to tell G1 and G2 apart, he will have figured out M1, having counted the days since his purging ended.
- Since S1 is the modulo sum of every guard's sign except G1, and S2 is the modulo sum sign of every guard's sign except G1 and G2, their difference (using modular arithmetic) is the number corresponding to G2's sign.
- Using this information P2 can correctly guess G2's sign the following day.
Congratulations, you have found the answer. It's also pretty much the fastest answer that you can have in terms of days.
I actually put a little bit of spread between this problem and the 7 hats problem because they use the similar trick of modular arithmetic, and I was trying to make sure people's brains would have to rediscover this neat idea.
|
That's what I got too, didn't thing of the summing/modulus though, so my solution would have taken up to 12^99 days :D.
|
On October 08 2010 23:21 FiBsTeR wrote:Show nested quote +On October 08 2010 19:19 Bill Murray wrote:
They eliminate down to 2 guards. At that point it would be 1, 2, 1, 2, 1, 2, 1, 2 for them both You can't guarantee that the same two guards are left for each prisoner. P1 could be left with G1 and G2 and P2 left with G3 and G4.
easy. short, bald, brown eyes, etc
distinguishable
you can pre-game strategy
|
On October 09 2010 15:08 Bill Murray wrote:Show nested quote +On October 08 2010 23:21 FiBsTeR wrote:On October 08 2010 19:19 Bill Murray wrote:
They eliminate down to 2 guards. At that point it would be 1, 2, 1, 2, 1, 2, 1, 2 for them both You can't guarantee that the same two guards are left for each prisoner. P1 could be left with G1 and G2 and P2 left with G3 and G4. easy. short, bald, brown eyes, etc distinguishable you can pre-game strategy
This is considered beyond the abilities of the prisoners. To make the problem more clear, I will say that all guards look the same, but they are arbitrarily numbered so that a prisoner can differentiate between them. However, they wear different numbers for each prisoner, so they cannot use number to jointly identify a guard.
|
|
|
|
|
|
EPT
