Hi All,
So I am here back again with a new interesting puzzle ( courtesy Vaibhav Gupta ). I am copying his mail verbatim below followed by the solution that I have in mind.
---------- Puzzle ------
NECKLACE PUZZLE #2
There are two circular necklaces with same number of three types of gemstones,
but the gemstones may be strung in different order along the necklace.
Now the two necklaces are placed on one top of the other so that the
gems are aligned
one above the other. Count the number of locations where the pair of
gems (one from
the lower necklace, one from the upper) is of the same type.
Since one necklace can be rotated relatively to the other, there are
many orientations
in which the count of matching gems can be taken.
Prove that there is at least one orientation where the number of
matches is at least
a certain number v.
For the special case of equal numbers of each kind of gem, v = N/3,
where N = total number of gems in one necklace (and 3 kinds of gems).
1. prove this for the special case.
2. find, with proof, value of v in the general case (with m kinds of
gems not necessarily equal in number).
some clarifications:
1. the necklace is circular i.e. its a simple closed loop. so given
two necklaces RGB and RBG,
the second can be rotated wrt first to give three orientations (but
this small example
is unusual because the number of matches is same in all 3 orientations):
RGB
RBG 1 matches
RGB
GRB 1 matches
RGB
BGR 1 matches
so v = 1
2. "there is at least one orientation where the number of matches is
at least v"
label the orientations from 1 to N. denote the number of matches for
orientation i as m[i].
then " there exists an i such that m[i] >= v" is the more formal way
of saying this.
-Vaibhav.
------------------
Well, indeed an interesting puzzle. Intially for a few minutes I thought whether it can be proved by contradiction or not. I tried to see whether I am able to hit a contradiction by imagining that "v is always less than N/3". Within a few minutes I realized that this is not going to work. As I remembered the lessons from Prof Sundar Vishvanathan , I thought of trying to prove it by induction. Prof Sundar always used to say that most of the proofs can be given by the principle of mathematical induction. This time I did not bank too much on this options as I learnt it from my earlier experience as I mentioned in my previous post. The solution of this proof also along the line which was taught to me by Prof Sundar.
The proof here makes use of the fact that if expected value of some random variable is a then there exist a possibility where the random variables has a values at least a.
Let us assume that first necklace is fixed and the second necklace is rotated with respect to the first one. Let us define a random variable X such that
X_i = 1 ( if ith gem of first necklace matches with the second one )
X_i = 0 Otherwise.
The ordering in the second necklace can be anything so assuming a uniform distribution there.
Calculating the expected value,
E(X_i) = Pr(X_i).X_i = (Number of gems having the same colour as ith gem/Total number of gems)
For 3 different kind of gems
E(X) = Sum(i=1 to N) ( E(X_i) ) = R^2/N + B^2 /N + G^2/N.
For the special case where R = B = G = N/3 we will have
E(X) = N/3. As the expected value is N/3 we can say that there is at least one configuration of second necklace which would make the number of matching gems at least N/3.
When there are m kinds of gems, not necessarily equal in number, let C[i] denote the number of gems of the same kind as i, where i varies from 1 to m.
Therefore, for general case the expected value is
E(X) = Sum (i = 1 to n ) ( C[i]^2/N )
Well, a nice puzzle indeed. As a closing remark, I have the solutions to the puzzle that I mentioned in my previous post. It will require some figures to be embedded to explain the solution in a lucid way. I will post it soon as I get the time.
Tuesday, May 29, 2007
Friday, May 11, 2007
Necklace Theorem
Hi all,
As mentioned in my last post, after lunch talks can be very fruitful at times. Describing a yet another fruitful chat with my friend Sambuddha Roy.
The other day he gave me an interesting problem to think about, which is formerly known as, as he told me, necklace theorem. Two thieves have stolen queen's very precious necklace. There are three kinds of gems in the necklace called R, G and B. All are even. The problem is to divide the necklace in such a way that both the thieves get equal amount of gems of each kind. The necklace can have any interleaving of the gems. ( e.g. RRGBGGRBBBG..... ) Prove that it is always sufficient to divide the necklace in equal share by at most 3 cuts.
The proof makes use of Ham Sandwich Theorem. For brevity, I will quote it as HST now on. HST for 2-dimension says that given any two point sets in a plane, there always exist a line which will cut both these point sets simultaneously into half. To say it more formally, call the point sets R and B. Then one side of line will contain at most |R|/2 points and at most |B|/2 points. The same constraints will be followed on the other side too.
If there is only 1 point set R. For a given direction we can always have a line which will divide R in two. The proof is based on intermediate value theorem. It says that for a continuous function if f(x1) = 0 and f(x2)=1 then there exist a z \in (x1,x2) such that f(z) = 1/2.
Now that we have two point sets. What we can do is we get a line for point set R. Now we evaluate how this line L behaves with respect to B. Let us define diff(L) = number of blue gems on the left of L - number of blue gems on the right of L. For initial line L, let the value of diff(L) be b. What we can do is rotate this line a bit. We know that for any given direction, we have a corresponding line L which will divide R equally. We will again evaluate wrt B. We keep on doing this until we have rotated the line for 180 degree. At this point value of diff(L) would be -b. From intermediate value theorem, we can state that there will be a line where diff(L) will be 0.
How about, Ham Sandwich theorem in 3-dimension?? Well, my friend has given me the proof as an exercise. The statement is that given 3 point sets R, G, B in R^3 ( or 3-dim space ) there always exist a plane which will divide all 3 point sets simultaneously into equal portion.
Now, we need to reduce Necklace Theorem to HST in 3D. Starting from left to right, assign every gem an index i. Plot a parametric curve ( t, t^2, t^3 ) using these indices. HST assures us that we will have a plane ax+by+cz+d=0 which will divide R, G, B equally. This plane will divide the parametric curve at , at most 3 points as at + bt^2 + ct^3 + d = 0 will have at most 3 roots. Now, it is easy to map these 3 intersection points on the curve to 3 cuts on the necklace.
Phew!!! It never occurred to me that this proof will use such weird things. Induction based method was too tempting for me to let me think in some different direction. But the story is not over yet. The proof given above is not constructive. So if we were to find an algorithm to find these 3 cuts we might have to explore all possibilities taking O(n^3) time. So another exercise would be to try to find more efficient algorithm to find these cuts.
The generalization of HST is that given k point sets in R^k there would be always be a hyperplane which would cut all these k point sets simultaneously into equal portion. Yet another generalization one can think of is that, what if there are more thieves??? Given q number of thieves and k kind of gems, what would be the upper bound on the number of cuts required?? The answer is due to dold's theorem ( Neither sambuddha nor I have read the proof ). It say that for such situation at most k(q-1) cuts would be necessary.
What if there are 3-point sets in two dimension?? Definitely a line would not suffice. An exercise would be to prove that two rays originating from an apex would be sufficient. Give an algorithm for finding them out.
Two more puzzles are :
1) Given a point set of size n in 2D, prove that there would exist a pair of orthogonal lines which would divide the point set in such a way that in each quadrant number of points are at most n/4.
2) Given a point set of size n in 2D, prove that there would exist 3 concurrent lines which would divide the point set in such a way that in each segment the number of points are at most n/6.
That's enough to tease our brain for a while :D.
As mentioned in my last post, after lunch talks can be very fruitful at times. Describing a yet another fruitful chat with my friend Sambuddha Roy.
The other day he gave me an interesting problem to think about, which is formerly known as, as he told me, necklace theorem. Two thieves have stolen queen's very precious necklace. There are three kinds of gems in the necklace called R, G and B. All are even. The problem is to divide the necklace in such a way that both the thieves get equal amount of gems of each kind. The necklace can have any interleaving of the gems. ( e.g. RRGBGGRBBBG..... ) Prove that it is always sufficient to divide the necklace in equal share by at most 3 cuts.
The proof makes use of Ham Sandwich Theorem. For brevity, I will quote it as HST now on. HST for 2-dimension says that given any two point sets in a plane, there always exist a line which will cut both these point sets simultaneously into half. To say it more formally, call the point sets R and B. Then one side of line will contain at most |R|/2 points and at most |B|/2 points. The same constraints will be followed on the other side too.
If there is only 1 point set R. For a given direction we can always have a line which will divide R in two. The proof is based on intermediate value theorem. It says that for a continuous function if f(x1) = 0 and f(x2)=1 then there exist a z \in (x1,x2) such that f(z) = 1/2.
Now that we have two point sets. What we can do is we get a line for point set R. Now we evaluate how this line L behaves with respect to B. Let us define diff(L) = number of blue gems on the left of L - number of blue gems on the right of L. For initial line L, let the value of diff(L) be b. What we can do is rotate this line a bit. We know that for any given direction, we have a corresponding line L which will divide R equally. We will again evaluate wrt B. We keep on doing this until we have rotated the line for 180 degree. At this point value of diff(L) would be -b. From intermediate value theorem, we can state that there will be a line where diff(L) will be 0.
How about, Ham Sandwich theorem in 3-dimension?? Well, my friend has given me the proof as an exercise. The statement is that given 3 point sets R, G, B in R^3 ( or 3-dim space ) there always exist a plane which will divide all 3 point sets simultaneously into equal portion.
Now, we need to reduce Necklace Theorem to HST in 3D. Starting from left to right, assign every gem an index i. Plot a parametric curve ( t, t^2, t^3 ) using these indices. HST assures us that we will have a plane ax+by+cz+d=0 which will divide R, G, B equally. This plane will divide the parametric curve at , at most 3 points as at + bt^2 + ct^3 + d = 0 will have at most 3 roots. Now, it is easy to map these 3 intersection points on the curve to 3 cuts on the necklace.
Phew!!! It never occurred to me that this proof will use such weird things. Induction based method was too tempting for me to let me think in some different direction. But the story is not over yet. The proof given above is not constructive. So if we were to find an algorithm to find these 3 cuts we might have to explore all possibilities taking O(n^3) time. So another exercise would be to try to find more efficient algorithm to find these cuts.
The generalization of HST is that given k point sets in R^k there would be always be a hyperplane which would cut all these k point sets simultaneously into equal portion. Yet another generalization one can think of is that, what if there are more thieves??? Given q number of thieves and k kind of gems, what would be the upper bound on the number of cuts required?? The answer is due to dold's theorem ( Neither sambuddha nor I have read the proof ). It say that for such situation at most k(q-1) cuts would be necessary.
What if there are 3-point sets in two dimension?? Definitely a line would not suffice. An exercise would be to prove that two rays originating from an apex would be sufficient. Give an algorithm for finding them out.
Two more puzzles are :
1) Given a point set of size n in 2D, prove that there would exist a pair of orthogonal lines which would divide the point set in such a way that in each quadrant number of points are at most n/4.
2) Given a point set of size n in 2D, prove that there would exist 3 concurrent lines which would divide the point set in such a way that in each segment the number of points are at most n/6.
That's enough to tease our brain for a while :D.
Wednesday, May 02, 2007
After lunch talks
Hi,
It's been a long pause on my blog. I would say nothing significant to write. Even in this post not much significant but few small interesting pieces of interesting discussion.
Sometimes we go to IRL foyer after lunch and have some discussion. At times, those discussions are fruitful too. By fruitful, I mean it adds something in your knowledge. For example, today I was chatting with my friend Sambuddha . He is a very good narrator, I must admit. He was talking about his BTech advisor Manindra Agrawal who has been awarded with a Godel Prize.
He narrated an incident when Prof Manindra was out to present his work on a conference. There were a few Fields medalist , who were unable to grasp the idea of a young talent like Prof Manindra taking away the Godel prize on the same problem that they once tried to tackle. As Prof Manindra was presenting his talks, these fellows tried to interrupt him in order to embarrass him every now and then. At one point, a question was posed on such a trivial thing that Prof Manindra could not resist but say "I don't know about the undergraduates in US, but I can assure you that any undergraduate student in India would be able to understand this". Needless to say, no further interruptions occurred during his presentation :-).
There were also a few things that I came to know like a complexity class ( NP^NP ) as well as
game of Hex, Secretary Problem and things like that.
Sometimes, chatting can be more brain stimulating than the work :-)
It's been a long pause on my blog. I would say nothing significant to write. Even in this post not much significant but few small interesting pieces of interesting discussion.
Sometimes we go to IRL foyer after lunch and have some discussion. At times, those discussions are fruitful too. By fruitful, I mean it adds something in your knowledge. For example, today I was chatting with my friend Sambuddha . He is a very good narrator, I must admit. He was talking about his BTech advisor Manindra Agrawal who has been awarded with a Godel Prize.
He narrated an incident when Prof Manindra was out to present his work on a conference. There were a few Fields medalist , who were unable to grasp the idea of a young talent like Prof Manindra taking away the Godel prize on the same problem that they once tried to tackle. As Prof Manindra was presenting his talks, these fellows tried to interrupt him in order to embarrass him every now and then. At one point, a question was posed on such a trivial thing that Prof Manindra could not resist but say "I don't know about the undergraduates in US, but I can assure you that any undergraduate student in India would be able to understand this". Needless to say, no further interruptions occurred during his presentation :-).
There were also a few things that I came to know like a complexity class ( NP^NP ) as well as
game of Hex, Secretary Problem and things like that.
Sometimes, chatting can be more brain stimulating than the work :-)
Subscribe to:
Posts (Atom)