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

Puzzle : Balls and Binary

Well,

I know that the name does not give any clue what the puzzle is about, but I could not think of any better name than this. Anyways, without any beating around the bush, let me directly come to the point.

Oh, for the record, this nice puzzle was given to me by manoj.

Problem : There are boxes, numbered from 0 to . There is a ball placed in box 0. In addition to this, you are given k-balls. You can add or remove a ball from  box numbered j only if there is a ball in the box numbered j-1. Now, using only given k-balls and the valid moves ( add/remove ), how would you place a ball in the box numbered ?

Solution : I have to get back to a very powerful mathematical tool called principle of mathematical induction for this problem. Of course, the trick lies in coming up with correct induction hypothesis.

Claim : Using k-balls I can reach a configuration where balls are placed in box numbered

. Note that, according to this claim, i-th ball will be distance away from (i-1)-th ball.

Base case : k = 1, I have only one ball and I will place it in box numbered 1. Configuration will look like following :  ( a box containing a ball will be written as nB)

0B 1B

So, the claim is trivially true here. Note, that 0 contains a ball by default.

Induction Hypothesis : Assume that with k = p-1 balls, balls will be positioned in box numbered :

Induction Step : We have k-balls. Using k-1 balls we can reach a configuration ( due to induction hypothesis ) where these k-1 balls are placed in boxes numbered :

.

But, I still have one additional ball, I can put it in box as there is a ball in box . Now, I can remove a ball from because there is a ball in .

So now, I have one ball remaining, also there is a ball in . I can place a ball at and now remove a ball from and then from .

I have two balls now. There is a ball in box numbered . Using two balls, I can reach upto 3 from number 0. So, I can reach upto . Now I can recover . and so on. It is easy to see that in similar fashion I can recover k-1 balls keeping one ball in .

From 0 with k-1 balls in hand, I can reach upto . So from with k-1 balls in hand we can reach upto . Also, it is easy to see that now balls will be place in boxes :

. If you don’t understand why this will happen, just subtract from above terms and you will reach configuration mentioned in induction hypothesis.

Those who are a bit confused due to bad writing as well as mathematical notation here is an example.

Example : 4 balls.

0B  -> 0B 1B -> 0B 1B 2B -> 0B 2B -> 0B 2B 3B -> 0B 2B 3B 4B -> 0B 2B 4B -> 0B 1B 2B 4B -> 0B 1B 4B -> 0B 4B — using the steps show above, just asume that 4B acts like a 0B –> 0B 4B 6B 7B -> 0B 4B 6B 7B 8B -> 0B 4B 5B 6B 8B -> 0B 4B 5B 8B -> 0B 4B 8B -> 0B 1B 4B 8B -> 0B 1B 2B 4B 8B -> 0B 2B 3B 4B 8B -> 0B 1B 2B 3B 8B -> 0B 1B 2B 8B -> 0B 1B 8B -> 0B 8B ( Now you have 3 balls in your hand , assume 8B is 0B and you can reach upto 15B ).

Very nice puzzle indeed I must say One can see its connection with binary representation of a number.

–Saurabh Joshi

Largest sum sub-sequence and sub-matrix!

Well,

I happened to bump into two old problems which I had solved sometime back. However, I never bothered to write it down anywhere which I intend to do so now.

Problem 1 : Given a sequence of integers ( +ve and/or -ve ) find a contiguous subsequence with the largest sum. By contiguous subsequence I mean if the i-th element and j-th element of the original sequence are in the subsequence for ( ) then k-th element is in the subsequence.

Example :  sequence :  1 5 -9 2 4 3 8

desired subsequence : 2 4 3 8

Problem 2 : Given a m x n matrix A, find a submatrix of A such that sum of all the elements of the submatrix is the largest amongst all possible submatrices.

Example :

1 2 -1
-3 -1 4
1 -5 -2

Desired sub matrix :

2 -1
-1 4

Solution 1 : Well, actually, solution for this is very easy and many people know about it. Still, for those who don’t know, let me describe it over here.

Initialize max_sum = 0.

You start calculating cumulative sum from the first element,at each step you store it in max_sum if it is greater than its current value. If at any point of time the cumulative sum goes below zero, store it in max_sum if it is greater than its current value, and reset cumulatvie sum to zero. Subsequently, update max_sum only if the current running sum is greater than max_sum. At the end, max_sum will give the largest sum. What about the subsequence? Well, you can keep start_index and end_index to keep track of which contiguous subsequence contributed to max_sum.

Running time is and I guess this is the best possible.

Solution 2  : Second one is a bit tricky but not too tough. In fact, we will use Solution 1 to calculate this one.

First what we do is for each row calculate cumulative sum array. That is array[i][j]  will contain sum of all element from 1 to j in the i-th  row. Time required is For all i, array[i][0] = 0

Next let us pick any two column, say p and q (with latex {n \choose 2}$. Running time is

I don’t know whether this is the best possible solution, or does there exist any solution which can achieve this in complexity better than

Do let me know if someone have a better idea.

– Saurabh Joshi

Let there be light!!!

It has been a long time since I have posted anything on my blog. Well, I guess I am just out of focus now a days. Anyways, today’s post is not about a puzzle but it is rather about a couple of open problems. I apologize for not giving any reference for these problems.

Problem 1 :

There are finite number of  non-intersecting line segments in a 2D plane. Each of these line segments act as a mirror from both sides. That is, any ray incident at an angle is reflected back at an angle where . It is conjectured that for any point in the 2D plane. If a light source is put at then there will be at least one light ray which will escape to infinity ( or in other words, the path of the light ray can not be bounded by a closed curve on the 2D plane ). No other physical phenomena like refraction, deflection etc can be used for the argument.

This innocuous looking problem is notoriously hard to prove or disprove.

Problem 2 : Let there by any polygon in a 2D plane. It has been conjectured that if a light source is put at any point in the polygon, it will illuminate the entire polygon ( for each point in the polygon, there exist a ray from light source which reaches at point observing only the law of reflection as described in the Problem 1 ).

This is again an open problem and so far it is invincible. Any takers???

–Saurabh Joshi

Cake Cutting Algorithms – 7 : Divide and Conquer

Well,

It has been long since I have written anything about cake-cutting. Anyways, in this post I am going to describe the best known deterministic algorithm for cake-cutting.

Let’s say we want to divide the cake between 4 people. We can let p1,p2,p3 mark a line which will divide the cake in two equal halves according to their own perceptions (captured by evaluation function ).

Say for example, p1,p2 and p3 marks line as shown in the figure. Because odd number of persons have cut the cake we can have a middle line. We will cut the cake at this line. Ask p4, whether the piece on the left or right is at least half according to his perception. If p4 selects the left half, then play cut and choose between p4 and p1 for the left piece and for p3 and p2 for the right piece. It is easy to work out the solution in case p4 selects the right piece.

What if there are odd number of people? Say 5. In this case, we will ask p1 to p4 to mark the lines which will cut the cake in the ration 2:3 from the left. Ask, p5 if he thinks whether the left piece is worth at least 40% or the right piece is worth 60%. As argued above, we can divide group into bunch of 2 and 3 and recurse.

So in general, if n is even, ask first n-1 people to cut the cake in the ratio of 1:1. If n is odd, ask first n-1 people to cut the cake in the ratio (n-1)/2 : (n+1)/2. And then ask which piece the n-th person thinks is worth at least its declared value.

It is easy to see that this algorithm works in time . This is the best known deterministic algorithm for simple fair division.

It has been conjectured that the simple fair division can not be achieved in with a deterministic discrete ( unlike moving-knife algorithm ) algorithm.  Many believe that the lower bound for simple fair division, where queries to evaluation function is not free, is . However, it is an open question that remains to be answered.

– Saurabh Joshi