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