Puzzle : Secret Sharing

Comparatively, simple puzzle today. Again, thanks to ramprasad.

A king was dying. (There is something about puzzles woven into a story, it makes it more dramatic ) He alone new the key to the secret treasure. He had N sons ( anything can happen in a puzzle! ). He wanted to pass on this secret key to his sons. Passing the key in its entirety may become reason of a quarrel. Let us say that key is a very large number ( or a large binary string ).

1) He want to make sure that only when all of his sons combine their part of the key, can they open the treasure.

2) He want to make sure that any k out of N can combine their keys to open the treasure, but any set of k-1 keys can not open the treasure.

Solution :

1) First is extremely simple. Let us say string S is the secret. Generate N-1 random strings of the same length as S. Create Nth key such that XOR of all the keys gives S. Done. Without all N keys, treasure can not be opened as they have to find S from possible strings.

2) Second is also easy. It was an aha moment, when ramprasad told me the general strategy to design such a secret sharing mechanism. Let us say, you want to make sure that any k out of N son can open the treasure. Let us say the number S is the secret. Generate a random polynomial f(x) of k-1 degree such that f(0) = S. Or in other words, S is the constant in the polynomial. Now the part of the keys are nothing but evaluation of the polynomial at some random points ( of course, not at 0 ). Given any k-1 points, there can be infinitely many k-1 degree polynomial which can pass through these points. However, for any given k points, a unique k-1 degree polynomial can be determined.

Well, there you go, so easy eh?

Puzzle : Black and white hats revisited, .. yet again!

The credit for this puzzle again goes to ramprasad. And I think that for coming days he will add a lot to my knowledge and blog as he got hold of peter winkler’s book on puzzles.

As usual, there are n people ( finite this time ). Black and White hats are randomly placed on each of them. They have to give their answer simultaneously and they have no means of communicating with anybody else.

1) In this puzzle, every one must guess the color of their hat. Come up with a strategy so that every one guesses the color correctly with probability 1/2 ( and I think this is the best you can achieve ).

2) In this variation, people are allowed to guess or say “pass” ( basically saying they do not want to guess ). Group of people will succeed if there is at least one person who has guessed the color of his/her hat correctly, and none of the persons guesses it wrong. What is the strategy to follow so that you can maximize the probability of success??

Solution :

1) I could get the solution of this problem after a bit of pondering. Let ‘1′ stand for black and ‘0′ stand for white. Everybody will assume that the summation of the entire string is 0 mod 2. So a person sums up from all the hat he/she sees and then choose the color so as to make the grand total 0 mod 2. Given any random strings from , the probability that the total of the string is 0 mod 2 is 1/2.

2) Two is a bit tricky and I could not get it. Let us try for n=3. The strategy would be that if a person sees the same color on the other two, then he guesses the opposite color otherwise he will pass. It is easy to see that they will fail only when the string is 000 or 111. Probability of suceess is 3/4.

In general, for n people, they can come up with some “Perfect Code” ( Just google it, will ya? ). Code with hamming distance 3 and error correcting capability of 1 bit. Now, a person sees the remaining part of the string, if by guessing ‘0′ the string falls into the code, he/she will guess ‘1′ and vice versa. Otherwise, the person will pass. One can see that the experiment will fail when the assigned string is one of the string in the code. In all other cases, the person, flipping whose bit makes the string fall into the code, guesses it right and rest all will pass. But then there are n times more strings, which are hamming distance one away from code. So the probability of failure would be O(1/n).

Sorry for the shaddy explanation, but believe me, it works!

Puzzle : Black and White Hats Revisited

Well,
I have been very lazy and irregular these days so I am not even trying to commit that I will be so in future . Here are two very nice puzzles, thanks to Ramprasad.

Problem : A person is standing on each natural number belonging to N. Yes, that means that there are countably infinite people standing in a straight line 1,2 …..infinity. As always, black or white hats are placed on each of them. This gives rise to a random string of infinite length. A person can see everybody else’s hat but not his/her own. Everybody has to guess the color of their hat simultaneous. No communication between any two people is allowed.

1) Come up with a strategy so that infinitely many people guesses the color of their hat correctly.

2) Come up with a strategy so that only finitely many people guesses the color of their hat incorrectly.

Solution :

Well, 1st puzzle is comparatively easy to solve. I will give two solutions, here
1a ) This solution is by deepanjan. A person standing on position p, looks towards infinity and see if he/she sees any black hat. If he/she sees a black hat, the person will announce that his/her hat is black. Otherwise announce that his/her hat is white.

Why would it work?
Let us say, there are only finitely many black hats placed. In such a case, there must be a largest position bp such that for all position greater than bp, hats are white. In such a case, all people standing on position greater than bp will look towards infinity and will see no black hats so they will announce their hat as white. Hence, infinitely many people guessed the color of their hat correctly.

What if black hat appears infinitely often? In that case, any person with a black hat, would be able to see another black hat when he/she looks towards infinity. Hence, all persons wearing a black hat will guess it right. Again, they are infinitely many of them.

1b) A person on position 2p-1 will pair up with person standing at position 2p. Let us call them p1 and p2. p1 will guess the color of his/her hat to be the same as p2. p2 on the other hand will guess the color of his/her hat to be different than p1. Obviously, one of them has to be right. Meaning, half of the people will guess it right.

2) Solution for two is tricky. It is based on “Axiom of Choice”.

Let us say two infinite strings s1 and s2 are related, if they are finite hamming distance away from each other. Such a relation is equivalence relation, hence partitions the set of all strings into equivalence classes.

Let these classes be c1,c2,…ck. So basically, any two strings drawn from a class ci will be finite hamming distance away from each other. For each such class ci, people will fix some representative string si belonging to ci.

Now, a person p looks at given infinite string pi. The actual assignment might be given by string S. A person may put 0 or 1 as a guess for his own hat and still both the resulting strings will be in the same class as S and pi. So, having observed a string pi, a person identifies the class ci in which pi belongs, and picks up corresponding representative string si. He announce the color of his/her hat as given by si. Because, si is only finite hamming distance away from S, only finitely many people will guess it wrong.

Phew, did not know that innocuous looking “Axiom of Choice” could be so powerful mathematical tool.

Puzzle : 9 balls

Well,

Problem was given by manoj, which he in turn found from some website.

Problem : 9 balls, 8 identical and 1 is lighter. You need to find out in 4 weights, which one is lighter. Huh, sounds simpler?? well, hold on. You are given 3 balance weight machines, out of which one is defective. You do not know which one is defective. Also, defective machine can give any outcome ( >, =, < ) irrespective of what you put on the machine. Now, can you find out which ball is lighter weighing only 4 times in total???

Solution : None of us could figure out the solution. But, once we read the solution from the website, deepanjan gave a very nice explanation. I am lazy to draw the figure, so trying out a text based table.

Divide the balls in 3 sets of 3 balls, A, B & C.

On machine m1, measure A and B. Without loss of generality, say it tells that C is the lighter set.

Now, measure A1,B1,C1 vs A2, B2, C2 on machine m2. Again, without loss of generality say it tells us that one of the A3,B3,C3 is lighter.

So we have this

1   |    2   |  3

————————-

A |   A1 |  A2  |A3

————————-

B |   B1| B2 |B3

————————

C |  C1| C2 |C3

On machine m1 we measured columns and on m2 we measured row. Intersection in this case is C3 ( it could be any cell, but C3 is just a representative )

Now, we measure ( C1,C2) vs (A3,B3) on the third machine. Or in other words, measure two remaining balls of the columns vs 2 remaining  balls of the rows on machine 3.

Case 1 : (C1,C2) = (A3,B3)

In this case, C3, indeed is the lighter ball. Because, two out of three machines are correct. If m1, m2 are correct, they already told C3 is lighter. If, m1 and m3 are correct then m1 says C is a lighter set and m3 says that C1 and C2 are not lighter. so C3 must be the lighter ball. Similarly if m2 and m3 are correct, C3 will still come out as the lighter ball.

Case 2 : (C1,C2) < (A3,B3)

Machine 3, says one of the C1 or C2 is lighter, which is a contradiction to machine 2 which said that one of the A3,B3 or C3 is lighter. Hence, machine 1 must be correct which said C is a lighter set.

Now measure C1 and C2 on machine 1 and find out which one is the lighter ball.

Case 3 : (C1,C2) > ( A3,B3)

Here machine m3 contradictions with machine 1 which said that C is the lighter set. Hence, m2 must be the correct machine. Measure A3,B3 on m2 and find out which one of A3,B3 or C3 is lighter.

Phew!!!! No wonder, it is a math olympiad question.

— Saurabh Joshi

Puzzle : Semi-circle covering n points

Well,

This is not much of a puzzle. Actually, it is a problem in continuous probability, in which, I am really not good at. This question was posted by saket.  Sagarmoy and Ramprasad could devise a solution, however, I will only describe RP’s solution because of its simplicity.

Problem :

Given n points drawn randomly on the circumference of a circle, what is the probability they will all be within any common semicircle?

Solution :

One might think that there are infinitely many semi-circle on the circumference of a circle. However, the beauty is that we need to consider only n semi-circle here.

If a semi-circle covering all n points, indeed exists, then, a semi-circle covering all n points and starting from one of the points in a clock-wise direction also exists.

So, given a semi-circle which starts at one of the point in clock-wise direction. The probability that the rest of the n-1 points will be in that semi-circle is . So for n such semi-circle, the probability will be

Such a simple solution!! But we really had a hard time when we were trying to solve, because we were focusing too much on the fact that the probability is continuous here.

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 .

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)).

A problem in graph theory

Well,

It’s been a long time on this blog and I can feel it through reduced traffic. But anyways, let me not worry about it and lets get to the point.

The problem was brought to me by manoj for which saket gave a very elegant and simple solution. Me and satyam made some good observtions but not the one which matterred the most .

Problem : Let G be any undirected graph. Let I be the maximum independent set and C be the minimum vertex cover for this graph.  Prove that

where denote the set of vertices of G.

Solution : A very important observation to make is this.

Claim 1 : Let VC be any vertex cover ( not necessarily minimum ) then the set V-VC will form an independent set and vice versa.

Proof :   Let VC be a vertex cover. If V-VC does not form an independent set then there must be two vertices such that . But in that case VC can’t be a vertex cover as it did not cover (u,v).

For the other direction, let IS be an independent set. So V-IS must form a vertex cover. If not then there must be an edge,  for which none of the incident vertex belong to V-IS. Then they must be in IS.  It is a contradiction then that IS is an independent set.

Having established claim 1, it is easy to prove the original stated theorem. Let C be a minimum vertex cover ( for a graph, minimum vertex cover or maximum independent set need not be unique ). V-C must form an indepedent set. If V-C is not the maximum independent set then let I be the maximum independent set such that .  From claim one there exist a vertex cover V-IS such that . But C was a minimum vertex cover and we found a smaller vertex cover V-IS. A contradiction! So the theorem holds .

–Saurabh Joshi

Job scheduling problem

Well,

This problem was written on whiteboard by manoj for others to solve and finally arpita solved it for the most part with me chipping in at the end.

Problem : There are n jobs to be done and 2 processor available.  Each job take the same amount of time ( so for simplicity one can assume it takes unit time ). Both processor have the same capabilities.  A job may depend on other jobs, for example if job A is dependent on B and C then A can not be scheduled before B and C both  are finished.  Dependancies amogst jobs are given.  Give an algorithm to find the optimum schedule ( in terms of time to finish all jobs ).

Solution ; Because dependacies are given, one can generate a dependacy graph. This graph is a DAG ( Directed Acyclic Graph ). Because if there is a cycle then all jobs which participate in the cycle can never be scheduled. Now, compute the transitive closure, in a sense that if there are edges A -> B and B -> C, then add an edge A -> C.

This way we have obtained all dependencies, direct as well as indirect, in this graph G. Forget about the direction of the edges for a moment and compute a complement graph G’. It is easy to see two jobs can be scheduled in parallel if and only if there is an edge between them in G’. Find a maximum matching ( 1-factor ) of G’.  Minimum time taken would

# of edges in G’ + # of unmatched nodes in G’.

Of course, the ordering is still needs to be decided.

Let’s get back to G now.  We will merge nodes which were matched in G’, that will give us another DAG.  Topological sort on this DAG would give us the order in which we should schedule the jobs.

Though I am not fully confident, I believe that this method would give us the optimum schedule. One more point to ponder is that whether this can be generalized for k-processors.

– Saurabh Joshi

Puzzle : Death Defying Duck!!

So I am back after a long time with an interesting puzzle. The credit for giving this puzzle goes to Sameer and in turn to microsoft for askim him this puzzle in their placement interview. ( By the way, sameer got selected in microsoft ).

Problem : There is a circular lake of radius . A duck is there at the center of the lake and a dog at the perimeter. Dog is intelligent and so is duck ( Actually none of them are, but this is added to make sure that reder is intelligent enough not to give any stupid answer ). Dog desperately wants to eat the duck. Now that the duck has finished fishing, it wants to escape. The only way it can escape is to reach the perimeter of the lake and fly away.  ( For some unknown reason, this duck can fly very well, but can’t do so when in the water ). Swimming speed of the duck is while dog can run at a speed of . What stretagy/path the duck should follow to guarantee a safe escape??

Solution : When sameer asked me this question, my initial thought was to try if duck can escape swimming diagonally opposite to the dog. But alas!! so while duck has to swim , dog has to run which is easy for the dog to accomplish. So it does not work!!

Anyways, we will assume now on that without loss of generality. So the next thing I thought of what if the duck starts moving in the diagonally opposite direction only for some distance . After that, duck again changes the velocity so that the direction will be towards the digonally opposite point from the dog. I imagine that this will lead to some kind of a spiral like path. However, evaporation of integration and differentiation happened years ago from my brain, I could not prove or disprove whether this stretagy would work.

So finally, I came up with the solution from other direction. Look at the figure below.

Distances AB=1/4, AD=AC=1, BC=3/4. What if the duck can be at B while the dog is at D? Duck can now straight away go to C safely. Why? Well, think about it for a moment. BC=3/4, so dog can cover at most distance upto 3 unit of distance in that time. But to catch the duck, dog has to cover . Poor dog!!!

Next thing is to make this situation happen. Notice that when duck circles around the lake at radius 1/4, dog can run along the perimeter with the same angular velocity. For all circles with radius less than 1/4, angular speed of the duck is greater than the dog. So duck chooses to circle around at a radius where, is very very small. Duck now keeps circling around which gives him positive phase difference with respect to dog. When the phase difference becomes 180 degree, at that point duck can straight away go diagonally opposite to the dog and escape.  Here, is small enough to exploit the difference of .

It was an interesting exercise going through all that. Thanks to sameer for bringing this to me.

– Saurabh Joshi