Sunday, November 11, 2007

The Random Jail


This problem is pretty interesting.

There are "n" people locked up in a room and they have to find a person that links them together. No, I didn't think of this after watching SAW2, but from a friend's post.
(See here: http://sdilips.blogspot.com/2007/11/random-jail.html )

Given the theory of 6 degrees of separation, the solution probably exists. Let us assume that it does and that there is one person "X" who links them all. What would be the best strategy for the "prisoners" ?

This is what I came up with:

Edit: To follow the remainder of the post, you need to know that "6 degrees of separation" is the hypothesis that any two people in the world are connected by just 6 other people (i.e., anyone in the world is my friend's friend's friend's friend's friend's friend's friend). See Wikipedia for a bit more info.

Now, "X" is at most 3 hops from everyone, or he is closer to some of them while farther away from the others. So, the worst case is probably either of the 2 scenarios:
1. "X" is 3 hops from each of the "n" prisoners
2. "X" is 1 hop from some "A" but 5 hops away from the remaining "n-1" prisoners

The obvious way to solve the problem would be going 1 hop at a time. At each round, everyone makes a list of places they have been associated with (like school, college, work place, vacations, etc) and then looks at everyone else's list to see if they can make a "connection" with one of places in the other's list. If they can make a "connection", then they write a list of possible people associated with that connection and again compare the lists for a match.

An important thing to be noted here is the way we define a "connection". Since we are assuming that the prisoners are capable of solving the problem, it means that they KNOW the intermediate hops - at least sub-consciously. Hence, when they establish a connection between two places, their mind might automatically skip a few hops in the chain.

The fact that there are 'n' prisoners, I think, simplifies the problem in a way. Because:
1. There are probably multiple paths between the prisoners and hence more than one way to reach the solution.
2. The "n" prisoners can work in a distributed manner (in groups) and perform inter-group comparisons if there is a match within their group, and constantly reshuffle the groups.

There is also the case of false positives to be discussed. There may be matches (apart from"X") among pairs of prisoners or even "n-1" out of "n" but not all of them. This could certainly complicate things. However, testing false +ves is probably simpler than expected. Let "Y" be the person common to the prisoners "A" and "B". Now, everyone else tries to establish a connection to "Y", which would be easier than establishing connections to either "A" or "B", since all the information about "Y" is limited to that obtained from "A" and "B" (which is expected to get lesser and lesser as the number of hops between "Y" and "A" or "B" increases), and this limited information about "Y" must be sufficient to form that chain for the remaining "n-2" people if "Y" is "X". (This is true because we are given that everyone in "n" will be able to make a connection to "X".) If none of the "n-2" people are able to make a connection to "Y" using the limited information about "Y" obtained from "A" and "B", clearly, "Y" != "X". A minor point to be noted is that if there is a match between "A" and "B", every person in that path must be tested for "X" - not just "Y".

Of course, if "X" is just one hop away (as in SAW2 or as in the post), the problem must be solvable in minutes. (Heck, they do it even without any strategy in SAW2 within few hours!!).

Unless of course, the connection between the prisoners is not a person but is actually a "thing". I bet it would be a lot harder for them to discover that they all secretly like "KANK", in which case, I would rather they go the SAW2 way than get out of the room ever :) .

3 comments:

Dilip said...

This makes a complete mockery of my post :P. But an excellent analysis of the problem. Why dont we make a pact to : me->create problems
you->solve them

and if you expected an intelligent comment from me, keep expecting :D

Aravind said...

@Dilip:
lol. Nee thirundave maatiyaa?? Btw I think it is a good proposition. As long as you come up with interesting problems, that is.

Anonymous said...

Nice post but you shouldn't be copying Dilip's ideas. Prathiba.

Post a Comment

Back to Top