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

Particle Collisions

Hi All,

It has been a long break on this blog. I was heavily busyb with some work. Anyways, lets get down to the business.

We are hearing buzz about CERN and the mightiest particle accelerator it created on which the “big bang” experiment has been started. And it so happened that I came across this nice puzzle, thanks to Sagarmoy.

Problem : 4 particles are travelling with mutually different uniform velocity ( uniform velocity implies that the speed is constant as well as the direction of motion does not change ).

We will say collision occurred between two particle when two particles are at the same place at the same time. Our particles being of a special kind, do not change their velocity even after the collision. You can imagine that particle can pass through the other.

The velocity vectors of these 4 particles are mutually non-parallel. Also, it is given that only 2 particles will participate in any collision ( no three line co-incide at the same point ).

Given these facts, we know that minimum 0 (no two lines are on the same plane) and maximum 6 collisions () can occur. If it is known that 5 collisions have occurred, can you prove that 6th collision will always occur?

Solution : Well, there are two solutions. One by Sagarmoy and one by Deepanjan. I will describe Deepanjan’s solution first.

1) As shown in the figure, lines 1,2,3,4 indicate the direction of particle motions. Let’s say we want to know that when 5 collisions have occurred ( all but (3,4) ) then collision between (3,4) will always occur.

Let’s have a line 4′ parallel to line 4. We know that collision (1,4) and (1,3) has occurred. As line 4′ is parallel to line 4, it is easy to see that collision (1,4′) would also occur because the ration of distance needed to be travelled within a given timeframe for both the particles does not change. We also know that (1,3) collision has occurred. So obviously (3,4′) collision would also occur. Again, as 4′ is parallel to 4, (3,4) collision would definitely occur.

Similar proof can be given for any different orientation of lines.

2) This solution is by Sagarmoy and it quite elegant, I must say. Consider the path of particle in space-time ( 4-dimensions , 3 physical + 1 time). As the particles travel with uniform velocity, their path corresponds to lines in space-time. Again, let us say, we want to prove that collision (3,4) will occur if all other 5 collisions has occurred.

We know that collisions (1,2)(1,3)(2,3) has occurred. So, line 3 must lie on the plane defined by line 1 and line 2. Similarly we know that (1,2)(1,4)(2,4) has occurred, so line 4 also must lie on the plane defined by line 1 and 2. So, line 3 and 4 are on the same plane and are not parallel. It must happen that lines intersect. But intersection of lines in space-time means that particles are at the same place at the same time, so collision (3,4) must occur.

– Saurabh Joshi

Rectangle Tiling Problem

Well,

It has been a long break on this blog, but I am back now and I hope to be regular posting here now on. Anyways, this problem has a long history but recently it was brought to me by sagarmoy .

Problem : Let there be a rectangle of type-A and type-B. type-A rectangle have at least one integral side ( that is length of the side is integer ) and type-B rectangle have no side of integral length.

1) Prove that from a given instance of a type-A rectangle, it is impossible to tile up these rectangle and make a big type-B rectangle

2) Prove that there is no way of tiling up (any) type-A rectangles to make a big type-B rectangle.

Solution :

It is easy to see tha version 1 of the question is a special case of version 2.

1) we have a specific type-A rectangle. so let it have two sides i ( integral ) and r (rational )

Suppose we have made a type-B rectangle using this type-A rectangle. Then the sides of type-B rectangle is

m1i + n1r, m2i + n2r , where m1,m2,n1 and n2 are positive integers. Area of the big rectangle should be equal to the area of the sum of the smaller rectangles.

where, is the total number of tiles used to form bigger rectangle.

r being a rational can be written in a form p/q where p and q are integers which are relatively prime. So

Multiplying by q

Right hand side of the equation is an integer. Also, first and second term of the left hand side is also clearly an integer.  To make the equation correct q has to divide n1 or n2 because it can not divide p ( remember that p and q are  relatively prime ). Without loss of generality, let us say q divides n1 then the side with length

m1i + n1(p/q ) becomes an integer ( as q divides n1 ).

2) Frankly speaking, none of us ( me, deepanjan and sagarmoy ) could come up with a proof for this second case. However, an interesting compilation of 14 different proof of this version is available at :

http://www.jstor.org/stable/2322213?seq=1

Those of you who are not subscribed to this journal, I am writing down one proof mentioned in that link which I found as most elegant.

Let our big rectangle R be aligned in a way such that bottom-left corner co-incide with (0,0), and the sides are aligned with x and y axis. Let T be the set of constituent tiles ( of type A ).

Let S = { (x,y) | x and y are integers, (x,y) is a corner of some tile in T }

We can draw a bipartite graph now with S and T forming two partitions of this graph. There is an edge from to if and only if tile t is having s as one of its corner. As all tiles in T are of type-A ( one integer side ), all tiles should have either 0,2 or 4 neighbours in S. Total number of edges between S and T has to be even. Each point in S which is not a corner of R will have 2 or 4 neighbours in T.

Note that (0,0) has only one neighbour in T, to make total number of edges even, there has to yet another point in s which lies on odd number of tiles.  Clearly, this point s has to be another corner of R ( so as to have only one neighbour in T ). If R has any other corner apart from (0,0) in S then R must have width or height of integer size.

There is one proof mentioned in the linked article which works like a magic, comes out of thin air. I won’t call that proof very elegant, but it really requires imagination to come up with such a proof. But I guess, I will mentioned that proof in some alter post.

Limitation of a data structure

Well,

I must give credit to my favourite professor sundar for this problem.

Problem : Let there be an abstract data structure D. D is a k-Max data structure, in a sense that on performing delete() on this data structure, it returns the k-th largest(Maximum ) element of the elements stored in it. Only two operations are allowed on D, insert(number) and delete(). Obviously, insert(n) will insert the given number n to the data structure.

Prove that, it is impossible to implement D in a way such that both insert(n) and delete() takes O(1) time. Or in other words, any implementation of D will have at most one operation that can perform in O(1). The other operation can not be implemented in O(1).

On sujith’s request, I am giving a bit more space between the problem definition and solution so that one can avoid accidental peeking .

Solution : If someone want a bit of a hint, I would say, the proof goes by contradiction. If ,indeed, we have one such data structure we will defy rules of computational complexity.

Let us assume that we have such a data structure D. and let k=1, that is D is a 1-max data structure, which returns the largest element in D. Also, assume that insert(n) and delete() are both O(1) operations. Now, if I am given n integers. I would insert them one by one. After all insertions I will perform deletions. It is easy to see that this way, I can sort n integers in time O(n)!!!!

It should be fairly easy to see why this is true for any value of k>0. In linear time we can find the largest, say Max, of n integers. I can insert (k-1) dummy integers which are greater than Max in D. And again, I have a linear time sorting algorithm in the worst case!!!

It is a clear contrast to logarithmic lower bound for sorting.

Now we know why we don’t have any such data structure

– Saurabh Joshi

The ring of numbers

Well,

I am back from my short break, however, will go for another short break in a week’s time. But meanwhile lets get back to business.

Title of this post may be a bit misleading as I am not referring to ring as they appear in number theory. Deepanjan gave me this puzzle yesterday and I could come up with a very simple solution where as his solution was a bit involved.

Problem : Integers from 1 to n are arranged in a circle in some random permutation. Prove that there exist a set of k consecutive  integers on the circle sum of which would be at least k(n+1)/2.

Solution : Set of k consecutive integers can be uniquely specified by the start position and the direction ( clockwise, or counter clockwise ). We will call it a k-box. Because they are arranged in a circular fashion there are n positions. We will assume clockwise direction. For each of these n position compute sum of its corresponding k-boxes. Sum of all these k-boxes would be kn(n+1)/2. The reason is that . and each number will appear in k different k-boxes.

So on average, each k-box makes a contribution of k(n+1)/2. So there exist at least one k-box which makes contribution of at least k(n+1)/2.

Or, in other words. If none of the k-box can make contribution of at least k(n+1)/2 then the total of all k-boxes would be strictly less than kn(n+1)/2 which is a contradiction.

– Saurabh Joshi

A short break

Dear Readers,

I will be out of town for a couple of weeks ( till 1st of July 2008 to be precise ). So the blog may not be updated during the period.

Regards,

Saurabh Joshi

Puzzle : A better solution to colour coding cables

Well,

It turns out that there exist a better solution for puzzle related to colour coding of cables.

Once again my brilliant friend Deepanjan came to the rescue and provided a better solution to the above mentioned puzzle.

In the earlier post along the same line, for even number of cables 3 trips were needed where as for odd number of cables 2 trips were needed.

In this solution, I will describe a method to always determine in only 2 trips that which ends belongs to which cable.

Solution : I suggest readers to have a pen and paper handy to comprehend the solution easily.

One assumption made for this solution is that more than two cable ends can be electrically shorted. In which case, if you put continuity meter between any two cable of the bunch, it will show them as connected.

Let us say we have N > 2 cables.

case 1 : N = k(k+1)/2

This case is easy to understand.
We can divide cables into groups of 1, 2, 3 …., k

In every group, all cables belonging to that group is shorted.

Now, we go down ( first trip ). Clearly, we will be able to identify different groups because for cables belonging to group i, continuity meter will show them connected with exactly i-1 other cables.

So we have determined following groups, 1, 2 , …. , k.

Now, we take one cable from each group( 1_1, 2_1, 3_1 …k_1) and short them. First group will be of size k, let us call the group as k’.

Similarly, second group will be of size k-1 ( because group 1 had only one cable, which was consumed in forming group k’)

The last group will have size 1.

Now we go up ( second trip ). Original group of size 1 was determined in the first trip itself. For group 2, if a cable is connected to k-1 other cables then it is 2_1, if it is connected to k-2 other cables then it is 2_2. Similarly we can identify every wire in every group.

case 2 : N = k(k+1)/2 + r where

In this case, we will form groups of size 1,2,…,k,r respectively.

Short all cables in their respective groups. For this example, let us say r = 5. So now, there will be two groups of size 5.

We go down ( first trip ) and identify . We will see two groups of size 5. Somehow, we need to be able to distinguish between them. Without, loss of generality we will put aside.

From rest of the groups, we will again form a group of size k ( call it ) by taking one cable from each group, as described in case 1.

So we will form groups and one remaining group . From , we will keep one cable loose . For the rest of the cable, we will start adding one cable () to , one cable() to and so on. If r=k then it can go only upto .

Now, we will go up ( second trip ). We will find two wires loose ( not connected to any other wire ). But one wire would be from original and one from . So we have identified . Now, from original group if a wire is connected to k different wires then it would be . Similalry we can identify each cable from group depending upon how many other wire it is connected to.

Once, each cable from group is identified, we can proceed to identify cables of other groups as already specified. So, for example, from if a wire is connected to 3 other wires in which one of the wires belong to . We know that, it belongs to . We had added only one wire from in so we will be able to identify the cables. Similarly, for other groups.

This solution is undoubtedly correct with the given assumption. If you do not follow the description easily, work out a small example on pen and paper using above method.

– Saurabh Joshi