Posts Tagged ‘theorem’

Points on a grid

February 25, 2011

Hi,

This is again one of the question that tejas faced in the CMI entrance exam.

Problem : Given an nxn grid. You choose 2n-1 points randomly ( each with different co-ordinates on the grid ). Prove that there will be three points amongst these 2n-1 point forming a right-angle triangle.

Solution :

It is easy to see that if we prove that it always have to be the case that there will be a point sharing a column with one point and a row with another point we are done. Looks like good old pigeon hole principle (php) should come to the rescue. Unfortunately, I could not come up with a solution using php.

I used mathematical induction to come up with a proof. And I agree with many other people who say that it does not give much insight into the problem.  Anyways, here it goes.

I am going to prove a general claim.

Claim : If you choose m+n-1 points from an mxn grid, there will be three points forming a right angle triangle.

Base case : 2×2 grid ( does not make sense when m or n is 1 ). This is trivial because we have to choose 3 points.

Also, 2xn is also trivial. We have n+1 points. Using php it is easy to see that there will be two points on the same row and two points on the same column. Because there are only two rows, it has to form a triangle. Similar argument goes for mx2 grid.

Assume that the claim is true for any m-1xn-1 grid.

Now,

(1) choose a point p at (x,y) which does not share either a row or column with any other point.  Remove the column and row denoted by x and y. Now we have m-1Xn-1 grid with m+n-2 (= (m-1) + (n-1) – 1  + 1) points to choose from. Follows from induction hypothesis.

(2) choose a point p at (x,y) which shares the column x ( or row y) with only one another point p1. If p also share a row(or column) with some other point p2, we are done. If not, remove column x and row y. m-1xn-1 grid with m+n-3 = (m-1 +n-1 -1) points to choose from. Follows from induction hypothesis.

(3) There are points p1…pk in the same row ( or column ). One can see that there can not be a point p in any of the column of p1…pk. Hence, remove all columns of p1…pk and the row in question. Now, grid is m-1 X n-k with m+n-1-k ( = m-1 + n-k -1 + 1 ) points to choose from. Follows from the induction hypothesis.

I know that there must be extremely simple proof for this. Arrgh, unable to find it :(.

–Saurabh Joshi

Advertisements

Puzzle : A number game

February 24, 2011

Well,

This is comparatively a simple puzzle with a nice observation. Given to me by tejas, who in turn, faced it in an entrance exam of CMI.

Problem : You are given integers from 1…2n. You are supposed to divide it in two sub sequence A and B such that, A and B both are of the same size n. A is monotonically increasing and B is monotonically decreasing. Prove that,

for any two such sequences \sum _{i=1} ^n | A[i] - B[i] | = n^2.

Solution : A very simple observation and you have the solution. Let,  \sum _{i=n+1} ^{2n} i - \sum _{i=1} ^n i=n^2. So here is what you do. The moment you observe that A[i] > B[i] for some i, you swap the elements. So the element at A[i] is now in B[i] and vice versa. Thus, you can make sure that set A has all and only elements from 1…n and B has all and only elements from n+1….2n. Note, that the difference is taken over the absolute value, hence swapping does not change it. Now we know that difference between summation of elements of B and A is n^2.

Neat, isn’t it?

–Saurabh Joshi

Circles and Tangents

November 23, 2010

Recently I came across a very nice puzzle related to geometry.

Problem : Take any three non-intersecting circles of distinct radii. Common tangents of any two will intersect at a point. Prove that the three intersection points due to three pairs of tangents are co-linear.

Solution : Ramprasad and I came up with a proof but we believe that there should be much simple and elegant proof. If you can throw any light, please comment. Here is the proof.

Let the center of circles A, B and C be denoted by C_A, C_B,C_C. Also the intersection points be denoted by X_{AB}, X_{BC}, X_{AC} and radii are r_A,r_B,r_C.

Given any two circles, say A and B. Following relation holds due to congruence of the triangles formed.

\frac{X_{AB}C_{A}}{X_{AB}C_B} = \frac { r_A} { r_B}. Now, X_{AB}C_{A} = X_{AB}C_B + C_B C_A

Simplifying, we will get X_{AB}C_A = \frac{r_A}{r_A-r_B}C_AC_B. Thus, we have got how far a point will be given the radii of two circles and the distance between their centers. Let \alpha_{AB} = \frac{r_A}{r_A-r_B}C_AC_B.

Now, Let C_A be the origin and with respect to that the vectors of C_B,C_C be denoted as v_B,v_C.

So, vector v_{XAB} for X_{AB} will be \alpha_{AB}v_B.

Similarly, v_{XAC} = \alpha_{AC}v_C and v_{XBC} = \alpha_{BC}(v_C-v_B) + v_B = ( 1 - \alpha_{BC})v_B + \alpha_{BC}v_C

For three points to be collinear, following must hold for some \lambda.

v_{XBC} = \lambda v_{XAB} + ( 1 - \lambda ) v_{XAC}

Therefore, we must prove that for some \lambda

( 1 - \alpha_{BC})v_B + \alpha_{BC}v_C = \lambda \alpha_{AB}v_B + ( 1 - \lambda) \alpha_{AC}v_C
Simplifying,

\lambda=\frac{ 1- \alpha_{BC} }{ \alpha_{AB} } and \lambda = 1 - \frac{\alpha_{BC} }{\alpha_{AC} }

 

You can verify that it is indeed the case that

\frac{ 1- \alpha_{BC} }{ \alpha_{AB} } = 1 - \frac{\alpha_{BC} }{\alpha_{AC} }

 

Very ugly math, and with very high probability I must have made a typo in the calculation. Please try it yourself and convince that the property holds. I am looking for a better proof!

Impartial Games

November 15, 2010

Well,

Today’s post is outcome of a fruitful discussion and puzzle solving with Ramprasad.

Problem : Given two pile of coins (n,m) – denoting that there are n coins in 1st pile and m coin in the second. In this two player game, a player is allowed to take as many coins as he/she wishes from any one pile. He/she has to take at least one coin. If a player does not have a valid move, he loses. Which player has a winning strategy and what is the winning strategy?

 

Solution : It turns out that the first player has a winning strategy if n \neq m, otherwise the second player has a winning strategy. The strategy is that a player always make the configuration (i,i) and pass it on to the next player. Okay, for two pile this is simple enough. What about 3 piles? Who wins? What is the strategy?

In general, one can ask questions about such impartial games regarding the winning strategy. Grundy numbers and Sprague-Grundy theorem allows one to easily build strategy for wide class of such games.

As we are talking about finite impartial games, the leaves of game tree are assigned grundy number zero ( losing position ). Now for any node in the game tree, assign the smallest non-negative integer which is not equal to the grundy number of any of its child. Hence, in the two pile game, (n,0) configuration has a grundy number n.

So now, for a union game G1+G2 ( one can make a move in either game ), the grundy number of the node ( i , j)  is nothing but XOR of grundy number of i in G1 and the grundy number of j in G2.

 

For example, in the game of three coin piles with configuration ( 3, 4, 5 ) the XOR is 2 ( 011 XOR 100 XOR 101  = 010 ). Hence, any one getting a configuration with grundy number zero loses if the other player is smart enough :-). So, in a 3 pile game, a player’s job is to always make a move such that the grundy number of the resulting configuration is zero. Assume A XOR B XOR C = X. Now, we need to make a move such that A becomes A XOR X, or B becomes B XOR X or C becomes C XOR X so that the resulting configuration always yields a zero grundy number. Because X is non-zero look at the most significant 1-bit. You can choose A or B or C depending upon which of these have 1-bit in the corresponding position.

Not only this, one can have games like, a player is allowed to take at most 3 coins from 1st pile, upto 5 coins from 2nd pile or upto 8 coins from 3rd pile. It is easy to see that now grundy number of G1, G2, G3 is N mod 4, N mod 6, N mod 9 respectively. And resulting grundy number can be found by XORing these mod-ed numbers 🙂

 

Pardon for a not so clear and untidy article. I had to compromise a bit to keep the length tolerable :-). Please see corresponding wikipedia links and other relevant material for more details on games.

 

— Saurabh Joshi

Tournament graph and Hamiltonian Path

November 11, 2010

Well,

Those of you who are unaware of tournament graph and hamiltonian path, you can look here and here. Ramprasad gave me the following interesting problem to think about.

Problem : Given a tournament ( I will omit the suffix “graph” as it is obvious in the context of graph theory ), construct a hamiltonian path in polynomial time.

Solution : When I first heard the problem, I was even wondering how to prove first that all tournament indeed always have an hamiltonian path. And that too, we need to find it in polynomial time..Phew! But I believe that if you comeup with an algorithm, that itself gives you a proof!!

He gave me a hint : given that you already have explored some path v_1,\dots,v_k how can you extend it for a given vertex v? That is, of course, if the path has not covered every vertex :-).

If there is a directed edge from v_k to v there is a natural extension. You just append v to the path. If not, find out two consecutive vertices v_i, v_{i+1} in the path such that the tournament have edges (v_i,v) and (v,v_{i+1}) in which case the modified path will be v_1,\dots , v_i, v ,v_{i+1},\dots, v_k.

Suppose no such pair exists!!!! Let’s try to see why this can’t be true. Look at, v_1,v_2. It has to be the case that either tournament contains edges (v_1,v),(v_2,v) or (v,v_1),(v_2,v). If it is the second case, that v can be just added as a prefix to the path. If it is the first case, than note that tournament must contain (v_3,v) because other wise we can have \dots, v_2,v,v_3,\dots. Similarly, we can argue for v_4,\dots giving us the contradiction as we had assumed that edge (v_k,v) is absent from the tournament.

Hence, we can always extend the path as long as there is some vertex we have not yet covered.
Ramprasad gave a simple proof of why a pair v_i,v_{i+1} must exist such that we can extend the path to contain v_i,v,v_{i+1}. If we can not add v as a prefix or a suffix to the path. Then look at the vertex with the least index j such that (v,v_j) is an edge. By the definition of the tournament, one of the two edge (v_{j-1},v) , (v,v_{j-1}) must be there. But, because j is the least index having an incoming edge in the path, the second edge can not be there. hence we can extend the path to contain v_{j-1},v,v_j.

Easy to see that algorithm runs in O(n^2) time as we need to search O(n) vertex to extend the path and repeat it till we  have covered all vertices.

–Saurabh Joshi

Puzzle : Hercules and Hydra

August 9, 2010

Well, without any ado, let me directly dive into the problem at hand. This interesting problem was given to me by Ramprasad. As usual, he is the guy who brings in interesting problem with interesting solutions.

Problem : Most of you know the legendary battle between Hercules and Hydra. Please search on Wikipedia or Google to get the details of this mythological story. Anyways, let’s come back to mathematics. Let Hydra be a rooted tree.  As Hydra is a demon tree, instead of leaves, it has heads. And the internal nodes to which the heads are attached to are called throats.

Now, in the battle between Hercules and Hydra, Hercules can make a following move. At every move, Hercules can cut one of the head of Hydra.  At any i-th move, Hydra grows i copies of the throat from which the head was chopped off in i-th move. For example, if in 7-th move, a head is chopped off from throat T ( having 6 heads prior to chopping, and 5 after a head is chopped off ). There will be 7 copies of T ( with 5 heads ) as siblings to original T. Once all the heads from a throat is removed, the throat becomes a head.

1)      Argue that Hercules has a winning strategy for any finite Hydra. That is he can wipe out Hydra completely.

2)      Argue that any strategy employed by Hercules is a winning strategy for any finite Hydra.

Solution: Frankly speaking, I did not have any formal argument for the problems above. But I have an intuition that at every move, only the width of the hydra is increased and not the height.  Besides the copies of T generated, have one head less.

So, for any throat T with k heads at n-th move, let f(n,k) denotes the number of moves it takes to wipe out throat T along with all its copies. As long as f(n,k) is finite, we know that hydra can be wiped out. At any n-th move, we get copies of T with k-1 heads. However, now the n increases hence a simple induction does not go through.

Deepanjan came up with a proof for a special case of Hydra. Let Hydra have only one root node, only one throat attached to it, and m heads attached to this throat. Now, let us have an m-tuple (Hm,H(m-1), H(m-2),…H1) denoting the number of throats having m heads, m-1 heads and so on.

So initially, this tuple is (1,0,0,…0).  Before any move, if tuple is (a1,a2,…am) and after the move if it is (b1,b2,…bm) then we can state that (a1,a2,…am) > (b1,b2,…,bm). Where the order is defined as follows.

(a1,a2,…am) > (b1,b2,…,bm) if either a1 > b1 or a1 == b1 and a2 > b2 or a1 == b1 and a2==b2 and a3>b3 and so on. Hence, at every move, the value of the tuple is strictly decreasing. Therefore, after finitely many steps the configuration would be (0,0,…0) and the hydra is completely wiped out.

This can not be generalized to general hydra because number of heads can surpass m for some throat T. ( remember that when throat is reduced to a head, the inter node attached to it becomes a throat ).

From what I gather from Deepanjan, Ramprasad told that it uses trans-finite induction and Goodstein’s theorem. I am yet to meet Ramprasad in understanding the proof of these statements.

–Saurabh Joshi

A problem in graph theory

January 19, 2009

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

|I| + |C| = |V| where V 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 u,v \in V-VC such that (u,v) \in E. 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 |IS| > |V-C|.  From claim one there exist a vertex cover V-IS such that |V-IS| < |C| . But C was a minimum vertex cover and we found a smaller vertex cover V-IS. A contradiction! So the theorem holds :-).

–Saurabh Joshi

Puzzle : Coin passing game

November 20, 2008

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 2^k people remain then the game
will always terminate. This can happen if initially there are 2^k + 2 or 2^k + 1 person are there.

Not a very challenging puzzle, but interesting enough.

— Saurabh Joshi

A property of Fibonacci numbers

November 19, 2008

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

Let there be light!!!

October 16, 2008

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 i is reflected back at an angle r where i=r. It is conjectured that for any point p in the 2D plane. If a light source is put at p 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 p in the polygon, there exist a ray from light source which reaches at point p 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