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

Puzzle : Coin passing game

Hello all,
The problem I am about to post seems to be popular amongst puzzle lovers. Me
and Saket settled it when we came across it yesterday. Not a hard puzzle but needs just a
couple of observations to solve.

Problem : There are n persons sitting in a circular fashion. Each of them owns a coin.
First person passes 1 coin to the person sitting on his left side. The second person in
turn passes 2 coins to the person sitting on the left. Third person passes 1 coin to the
left, 4th passes 2 coin to his left and so on. So each person receiving 1 coin from the
right has to pass 2 coins to the left. Similarly, a person receiving 2 coins from the
right has to pass 1 coin to the left. If at any point of time, a person runs out of coin
he/she is thrown out of the game. Convince yourself that it can never happen that a person
having 1 coin has to pass 2 coin to his left.

A game is called terminating if at the end only 1 person is left with all the coins in
his/her possession. There might be values of n where the game may not terminate e.g. 3
persons left with 4 4 4 coins respectively.

Prove that there are infinitely many values of n for which the game terminates.

Solution : If you start observing behaviour of games starting from n=1, you can observe
patterns which you can generalize.

It is easy to see that in the first round each person sitting at an even numbered position
will be thrown out of the game as he/she has 1 coin initially, receives 1 coin from right
but has to now pass both the coins to the left.

Also observe that the 1st person will be always thrown out of the game ( poor guy !! )

If n = 2k, after the first round k-1 will remain. If n = 2k+1, then k will remain.

Case 1 : n is even
for n=2k , after the first round configuration would look like

3(4) 5(2) 7(2) … 2k-1(2)

where a(b) denotes position a with b coins.
at this point of time. Number of remaining people are k, if k is odd the game will not
terminate because a person who looses one coin in a round will gain one coin in the next
round.

Case 2 : n is odd
for n=2k+1, after the first round configuration would look like
3(3) 5(2) … 2k+1(2)

If k is odd, the game will not terminate.

If both the cases if k is even, at the end of two rounds exactly half will remain. Because
a person who looses a coin will keep loosing in subsequent round.

After this elimination you again have to deal with cases where remaining people are odd or
even.

Thus you can observe that if after the first round people remain then the game
will always terminate. This can happen if initially there are or $latex
2^k + 1$ person are there.

Not a very challenging puzzle, but interesting enough.

– Saurabh Joshi

A property of Fibonacci numbers

Well,

The problem itself is comparatively easy but I can not resist to write about such an interesting series.

Problem : Let, F(n) denote a function which returns n-th number in Fibonacci series. Prove that for all n,

F(k) | F(nk).

Solution : Again my beloved friend “principle of mathematical induction” comes to the rescue .

Base case : n=1, F(k) | F(k)  ( a | b denotes that “a divides b” or in other words “b is a multiple of a” ). Trivially true.

Induction Hypothesis : Assume that F(k) | F( nk-k)

F(nk-k) = F((n-1)k). So assume that the claim is correct for (n-1).

Induction Step :

F(nk) = F(nk-1) + F(nk -2 )

= 2F(nk-2 ) + F(nk-3)

= 3F(nk-3) + 2F(nk-4)

= 5(nk-4) + 3F(nk-5)

(A) = F(i)F(nk-i+1) + F(i-1)F(nk-i) (This generalization is also as easy to prove as this property)

I can take values from 1 to nk. For n=1 we have already proved. So n will be at least 2.

2k >= k+1

Therefore, Let i be k+1

(A) = F(k+1) F(nk – k -1 + 1) + F(k) F(nk-k-1)

= F(k+1) F(nk – k ) + F(k) F(nk – k – 1)

First term is a mutiple of F(k) due to induction hypothesis.

Hence, F(k) | F(nk).

If you are interested in knowing something more about Fibonacci numbers, visit this page and/or visit the wikipedia link given at the beginning of this post.

– Saurabh Joshi

Puzzle : Balls Reloaded!!!

Well,

I know that even this time the title does not give any clue what the post is about, but well, at least it looks cool, eh? Just like ‘Matrix Reloaded’. Anyways, let’s get to the point.

Problem : I would like to give credit for this puzzle to Manoj and Sameer. Okay, so the problem goes as follows. There are two boxes A and B with m balls in one box and n balls in another. What you can do is take out any number of balls from any one of the box or you can take out equal number of balls from both the boxes. For example, you can take out 4 balls from A or 7 balls from B or 3 balls from both A and B. Of course you have an opponent in this game. At the end both A and B will be empty. The last person to make the move wins.

If you have the first move to make, what will be your stretagy? One thing is for sure that you can not always win. For example in a configuration (1,2) it is impossible for you to win no matter what move you make. In a sense (1,2) is a loosing state. Your job is to find out whether given configuration is a winning state or not and if it is a winning state, what will be the sequence of moves that will lead you to victory.

Yeah, I know it is one of those bunch of puzzles where you have to play a game with opponent and the last person to make the move wins or looses. Long back I posted a very interesting puzzle on a different blog.

Solution : Normally, the way to tackle this kind of puzzle is to build a state transition graph where sequence of transition alterntes between a winning state and loosing state. So idea thing would be to make a move so that the opponent always end up in loosing state.

I tried this approach first but unfortunately could not exhaust all the cases. For simplicity, I will only describe bases where in any state m < n because of symmetry of the problem. L denotes a loosing state and W denotes a winning state. Here, the state is independent of the player. Whosoever ends up in a winning state can win and similarly he/she can loose if loosing state is encountered.

(0,0)L <– (0,i)W <– (i,i)W

<– (i,i)W <– (j,j)W

(i,i+1)W ( except (1,2) )

(i,i+2)W ( except (2,4) (3,5) )

You can see that you can build a list of winning states with a list of exceptions where you can loose. Basically, I could not find any close form function in terms of (m,n) from which I can determine in constant time whether I can win or not.

The trick Sameer mentioned takes O(m) time.

We know that for |m-n| = 1, (1,2) is a loosing state. That also  makes (1,>2) and (2,>1) winning states. For |m-n| = 2, there is (3,5) making (3,>5) and (5,>3) winning states. Next possible number which is unused is 4 so (4,7) is the loosing state for |m-n| = 3. (6,10) will be loosing state for |m-n|=4.

One can construct such loosing state for any given |m-n| in O(m) time and O(m) space in this way. Now the stretagy is the following.

m=n  –> take out (m,m) and you win

m<n –> check whether (m,n) is a loosing state. If it is, you are doomed. If it is not, then there must be a loosing state (m,n’) corresponding to m.

if n’ > n then you will be able to find a loosing state (m”,n”) such that |m” – n” | = | m-n| and m” < m. Take out (m-m”,m-m”) to reduce (m,n) to (m”,n”) and your opponent is doomed.

if n’ < n, then take your move would be (0,n-n’) which will take (m,n) to (m,n’) and the soul of your opponent wll rest in peace.

Let’s take a look what makes a loosing state (m,m+i) a loosing state. We know that all numbers from 0 to m-1 are used to form a winning state. If you take out anything from m you end up in a state (j,m+i). There exist a loosing state (k,j) or (j,k) where |k-j| < i. So in the next move your opponent will take you from (j,m+i) to one of these states and you will be fragged.

If you make a move (l,l) you will end up in (j,j+i) and again your partner will lead you to hell through (j,k) or (k,j) as described above. So the lesser number m must not reduce. The only option remains for you is to move (0,l) where l<i). But that reduces the difference |m-n| < i. Now as described in the winning stretagy your opponent will take out (m-m”,m-m”) which will put an end to your game.

Again, I apologize if these i,j,k,l,m,n bothered you too much. One can take some concrete example and see that it works.

–Saurabh Joshi