Puzzle : 6 Prisoner and The matter of Life and Death

Again,

Manoj and Saket brought this interesting puzzle but with their role reversed this time. Saket posed the puzzle and Manoj solved it. I was very close to the solution but Manoj did it before me.

Problem :

A prison has six prisoners. One day, the jailer tells them that, he will write a (integer) number from [0,5] on each of the prisoners forehead, a number may be repeated any times and the assignment is completely arbitrary. After that everyone will be able to see all the numbers written except the one on his own forehead. Immediately after that, he will ask each of them to guess his own number, and write it on a piece of paper which the jailer will collect. The prisoners are not allowed to communicate in any manner after the numbering has been done, they obviously cannot see their fellow prisoner’s answers. But they are allowed to communicate with each other before the numbering. If ANY ONE out of the six prisoners makes a correct guess, then all of them will be set free, but if all of them make an incorrect guess then all of them will be executed.

Suggest a strategy for the prisoners that will ensure their freedom.

Solution :

Let the prisoners number themselves from [0,5] so that each prisoner
has a distinct number assigned to himself.

Now let the the jailer number them in any arbitrary way.
Let S be the sum of the number written by the jailer.

Claim: S mod 6 = x such that 0 <= x <= 5
That is to say (S mod 6) lies between 0 to 5. Nothing too much. This
is trivial. Any “number mod n” lies between “0 to n-1”.

Now let the guy labelled 0 assume that
S mod 6 = 0
So what he does is that he add up the number he see on other prisoners
forehead, let this number be S_0. Then he add an appropriate number
x_0 such that (S_0 + x_0) mod 6  = 0. And he claims that x_0 is
written on his forehead.

Claim: Atleast one prisoner will correctly identify the number on his forehead.
Proof: Let S mod 6 = k. We claim that the kth prisoner will correctly
answer the number on his forehead.
This is because first he will add up the number he sees on other
prisoners forehead, say S_k. Then he will add an appropriate number
x_k such that (S_k + x_k) mod 6 = k. Clearly x_k is written by the
jailer on the forehead of kth prisoner. Thats why S mod n = k.

PS : Manoj states that solution is not his, so I acknowledge whosoever unnamed, intelligent soul out there who came up with this 🙂

Puzzle : Goof ups by GOD

Well,

Coming directly to the point. Today’s puzzle was posted by manoj and answer was given by Saket. I am just copying it verbatim assuming that things are under creative commons license :D.

Problem :

You are given n balls. There are two type of information God has given to you.
Same(i,j) if ball “i” and “j” are same.
Different(i,j) if ball “i” and “j” are different.

Since the world is imperfect, obviously God has goofed up somewhere.
example
Same(1,2), Same(2,3), Different(1,3)
Obviously this is not consistent
But,
Same(1,2), Different(2,3)
is consistent as you “believe” that God will never assert “Same(1,3)”

But as I said God has goofed up somewhere and you have to pay the
price. And that too a computing price.
Given “m” such assertions can you find if the assertions are consistent.

Can you do it in O() time?

Can you do it in O() time?
Can you do it in O(m) time?

Solution :

I think O() solution is quite easy to achieve for this problem.

Every ball is represented by a vertex, when we process the statement same(i,j) we add an edge between the two corresponding vertex. We process all same(x,y) statements like this. Now for the set to be consistent, there should not be a statement different(x’,y’) such that x’ and y’ are connected. There can be O(m) such statements, we can check each statement by a simple DFS, which will again take O(m) time. Thus giving us an O() solution.

For the O(m log n) solution we can use the same edge structure, but additionally make use of the well-known Union-find data structure. Which gives O(log n) time for union / find. So we can insert O(m) edges for all same(x,y) calls in O(m log n) into the structure + for each different(x’,y’) use find, to check if both x’ and y’ belong to the same component (there can be O(m) such statements making the total time taken O(m log n)). The total time for the whole operation is thus O(m log n).

For the O(m) solution,

I think this problem in fact is same as the one addressed by union – find. Because if we have a O(m) solution to this problem, then we will also have an O(1) time union-find solution. But since the union find has a proven lower bound of inverse ackerman function (which although not constant, is extremely slow growing), this problem will also have a lower bound of O(m  α(n)).