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!

Logic and games -2

November 20, 2010

Well,

In the earlier post I mentioned about using games as a mean to prove/disprove expressibility of FO ( First Order Logic ).

Let us modify the game that we saw last time. Now each round consists of the following : The spoiler chooses one of the structure, chooses a subset of elements of that structure, duplicator has to do the same on the other structure. Now, the spoiler puts a pebble on one of the elements of the subset he/she has chosen and duplicator replies by playing it on the other structure. We have seen in the earlier post that it is impossible to distinguish between two graph A (two disconnected 5-cycle )and B ( one 10-cycle ) using only 3 pebbles. In fact, you will need log 2k pebbles to distinguish between two disconnected k-cycles and one 2k-cycle.

However, in this modified game, only 3 pebble suffices for the spoiler to win for any k. Here is the strategy for the spoiler to expose the difference between two structure.

Look at the figure. Spoiler first chooses one of the k-cycle in A and puts a pebble. Duplicator selects k-points in B ( 2k-cycle ) and puts a pebble. Now, the spoiler chooses the second k-cycle and puts a pebble and duplicator replies. For the third round, the spoiler chooses to play on B. It selects the shortest path between two fixed pebbles as subset, and puts a pebble right in the middle of it. Duplicator now has to play it in A ( two disconnected k-cycles ). Now, according to pigeonhole principle one of the k-cycle will have two pebbles. As shown in figure, (1,2) and (2,3) are in different cycles. Now on, spoiler will always play in graph B. it will choose a pair of pebbles belonging to different cycles in A, selects the pair having shortest path in graph B and puts the pebble right in the middle of it. The spoiler always maintain that it divides the path between pebbles images of which are in different cycles in the other graph. it is easy to see that, after some time, duplicator will have no answer to spoiler’s move ( isomorphism implied by pebbles can not be maintained in the other graph ).

This game gives rise to a logic which is strictly powerful than FO. However, Ramprasad mentions that due to a recent result one can always construct pairs of graphs that spoiler can not win for any k-pebble game. Also, this game has some connection to graph isomorphism but probably ramprasad will give details in the comment 😉

Similar games are designed to prove/disprove the expressibility of temporal logic, but may be some other time 🙂

— Saurabh Joshi

Logic and Games

November 18, 2010

Dear All,

This post is a side effect of a fruitful discussion with Ramprasad, which also refreshed my memories about a course “Logic in Computer science”.

An interesting way to capture the power of First Order logic is in terms of Ehrenfeucht–Fraïssé games. Essentially, it is a two player game. Given two different structures A and B and set of k pebbles the game is played as follows. Spoiler tries to show that A and B are indeed different where as Duplicator will try to hide this fact. Each of them take turn. In every round, spoiler will choose one of the two structure and put a pebble on one of the element of that structure. Duplicator puts a pebble on the other structure so that the two substructures induced by pebbles are isomorphic with respect to the relations specified.

For example, take two graphs A and B. A consists of two disconnected 5-cycles and B be a 10-cycle. One can see that it is impossible to distinguish these two graphs if only 3 pebbles are given. Try the exercise with 4 pebbles and the spoiler wins irrespective of the number of rounds played. Similarly, structures could be bit strings. Given P pebbles, one can always construct two bit strings of length greater than $2^b + 2$ such that one of then has odd parity and another one has even parity yet the spoiler has no way of winning. In general, parity checking or even st-connectivity ( whether there is a path from s to t in a graph ) can not be expressed in any first order logic. Here, pebbles corresponds to variables in the FO ( first order ) formula and a round corresponds to the quantifier depth of a formula. Hence, when we say duplicator wins in 5 pebble 10 round game,  is equivalent of saying that a formula which uses 5 variables and 10 quantifier depth can not express the property in question. When, the rounds are unbounded, it means that FO can not distinguish.

More interesting details/references can be found from wikipedia link given in this post. Thanks to Dr Anil Seth for introducing me to such a wonderful world of logic.

— Saurabh Joshi

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 : Power game

October 13, 2010

Well,

I like the dramatic titles :-). Anyways, here goes the problem.

Problem : Given an integer n, determine whether $n=a^b$ for some integers a and b in poly-logarithmic time.

Solution : It is obvious that for certain n, there could be multiple a’s and b’s such that $n=a^b$. We only need to find one such a and b or have to declare that there are no such integers. Needless to say, that we are ruling out b=1 :-).

Given any n, the number of bits required is log n. Now, let us fix b = 2. For this b,  a must be having $\lceil \frac{log n}{2} \rceil$ bits. So we know the range of possible a’s that might satisfy $a^2=n$. We do a binary search on this range in O(log n) time. If we do not find a suitable a, we fix b=3 and repeat. There can be only logarithmic many such b’s. Multiplication and calculating powers of a number, both can be done in polylog time. Hence, we can determine that the given number n is of the form $a^b$ for some n or not.

Cool, isn’t it?

–Saurabh Joshi

Puzzle : Find a duplicate

October 12, 2010

Well,

Needless to say that the puzzle was given by Ramprasad. After thinking for a while, I could figure out the solution using an old trick from one of the typical technical interview questions.

Problem : Given n element in an array ( say 0 to n-1 ). The elements comes from the set {1,..,n-1}. Clearly, due to pigeion hole principle, there will be a duplicate element. There can be more than one element which are occurring twice or more. In O(n) time, find out one duplicate element. The additional space you can use should not exceed O(log n).

Solution : At first, I thought that one can just have a bit array, storing whether we have seen an element or not. But for elements coming from 1,…,n-1 the number of bits required is O(n). Even if we consider a number representation to take O(log n), it will still require O(n/ log n) numbers to be stored. So clearly, that can not lead to a solution.

What works is as follows. Let us say you are given a singly linked list. You need to detect if the linked list has a cycle or not. You can only store constant many elements.

What you can do is have two poiters, p1 and p2. At each  step, you increment p1 by 1 ( by increment we mean that go to the next element in the linked list ), and you increment p2 by 2. If p1 and p2 ever becomes same, that means that the linked list has a cycle, otherwise, p2 will hit the end of the linked list.

It is worth noting that in this scenario, p1 and p2 will meet before p1 can finish traversing the entire cycle. Also, for any two relatively prime numbers ( n1, n2), if you increment p1 by n1 and p2 by n2, they will still meet irrespective of the length of the cycle.

This seemed like a little diversion from our original problem, but we are going to use this :-). What we will do is, we will look inside the element at index 0. Let us say this element is e1. Now we will look in the array A, A[e1] and then A[A[e1]] and so on. We can think of this mechanism forming a singly linked list. Because the element ranges from 1,….n-1, and the total elements in the array being n ( from index 0 to n-1 ) there has to be a cycle in this list. And as shown in the figure, the starting point of the cycle B, is the element which is repeated twice.  That is because, B will have two distinct predecessor e1 and e2 such that A[e1]=A[e2] = B.

So what you do is the following. As mentioned earlier, have two pointers p1 and p2. p1 will move by 1 and p2 will move by 2. Say they meet at point C. Let us say that distance AB=p, BC= q and CDB=r. How much p1 must have traversed? It will be p + q where as p2 has traversed p+q+r+q = 2(p+q) ( double than p1).
So, p = r.

So once we reach C. We will move p1 to A ( that is start from index 0 again ) and keep p2 at C. Remember that AB=p=r=CDB. Now, we will move p1 and p2 both by 1. They will meet at B and that is our duplicate element :-).

Instead of moving p1 by 1 and p2 by 2 to find out the point C, what if we move then by (n1,n2) where n1 and n2 are relatively prime? Would it work? 🙂

–Saurabh Joshi

Puzzle : Coloured Hats and Wizards!

August 24, 2010

Taking this puzzle from Pratik’s blog.

Problem : There are n wizards in a Kingdom. To test their intellect, the king summons them all. He tells them that on the next day, a hat of a random color from a set of k colors will be put on each of their head. A wizard can look at the colors of others hat but not at his own. He also tells them, that there are k rooms adjacent to the hall in which they will be gathered. Two wizard with the same colored hat must go to the same room, and any two with the different colored hat must go the the different room. One mistake and they all will be executed. What strategy should they come up with?

Solution : Well, the puzzle is not very different from usual black and white colored hats. And hence, the solution I posted as a comment on his blog, though correct, is not efficient. The solution proposed by me is as follows.

Give an ordering to each color $C_1 \dots C_k$. Now, assume two partitions, $C_1$ and the rest $C_2 \dots C_k$. Now, it reduces to the normal black and white colored hat puzzle. All wizards with hats colored $C_1$ will be able to figure out in time $O(C_1)$. Now, they will pick a room. Now, rest of the wizards can again use the partition $C_2$ v/s $C_3 \dots C_k$ as black and white puzzle, and all wizards with $C_2$ colored hats can figure out the color of their hat. And so on.

The solution is an overkill though. Nowhere, in the problem is it mentioned that wizards need to figure out the color of their hat. Merely, partitioning themselves, so that wizards with the same hats are in the same room and with different colored hats are in different room suffices.

So the efficient solution, as posted by a person named Sid, on his blog is as follows.

Give each color a number from $0 \dots k-1$. Now, each wizard will sum up the colors that he sees in modulo k.

It is trivial to see that two wizard having the same color, will calculate the same number s modulo k. And those with different color will calculate different numbers. That’s it!! Very elegant solution 🙂

— Saurabh Joshi

Related post : here, here and here

Puzzle : Nice puzzle on sorting!

August 11, 2010

Well,

The title is directly taken from a mail by Ramprasad, so is the puzzle :-). He in turn gives credit to Prof Meena for this nice puzzle.

Problem : Pasting the problem verbatim here from Ramprasad’s email.

Meena had given us this puzzle during this workshop and I found it
incredibly interesting.

Suppose we have 13 cards arranged in descending order: K Q J 10 9 8 7
6 5 4 3 2 1
At any move, you can take a substring of cards and move it elsewhere.
For example, 10 9 8 could be move to the right by 2 steps to get K Q
J 7 6 10 9 8 5 4 3 2 1. The goal is to minimize the number of such
moves.

It must be absolutely obvious that you can do it with 12 moves but the
very fact that I’m asking you this question means that you can do
better. How many moves do you need? 🙂

Now the obvious extension to this problem is to generalize this technique for any n.

Solution : Well, I got the solution myself, but not without the hint. And the hint is as follows.

See the snipped mailing conversation between me and Ramprasad.

> Is it the case that number of inversions should strictly decrease?

>

Actually inversions was my first guess towards proving the lower

bound. It is a very good guess but I do not know if it absolutely

necessary that inversions must go down at each step. But perhaps your

guess is right… maybe it must go down monotonically at each step.

[For those who do not know what an inversion is, a pair of indices

(i,j) is called an inversion if i < j and a_i > a_j ]

My first attempt towards the lower bound was that initially there are

n-choose-2 inversions and finally there are none. If we can show that

each move can remove only n inversions then we’d sort of have a good

lower bound. But unfortunately this is not true: take n n-1 n-2 … 1

and shift the first half and put it after the 2nd half to get n/2

n/2-1 … 1 n n-1 n-2… n/2+1. This process actually gets rid of

O(n^2) inversions and my proof attempt broke.

However there is a very similar parameter that can be used to argue

about the lower bound. And this parameter is called ‘descents’. These

are indices i such that a_i > a_{i+1}. Now clearly to begin with there

are (n-1) descents.

Claim: At every step, you can reduce the number of descents by at most

2. [prove it]

This immediately gives a (n-1)/2 lower bound. But do all steps

actually reduce the number of descents by 2? No! Take for example, the

first move. It can reduce the descents only by 1! And similarly the

last step. Thus you get the required lower bound of (n+1)/2.

And, this lower bound can be achieved!

---


Well, there you go! It was sufficient for me to get the trick after this hint. The claim is easy to prove

hence I am leaving it for interested readers ( if any 🙂 ).

The sequence for 13 cards is as follows :

K Q J 10 9 8 7 6 5 4 3 2 1
K 6 5 4 3 2 1 Q J 10 9 8 7
1 Q K 6 5 4 3 2 J 10 9 8 7
1 2 J Q K 6 5 4 3 10 9 8 7
1 2 3 10 J Q K 6 5 4 9 8 7
1 2 3 4 9 10 J Q K 6 5 8 7
1 2 3 4 5 8 9 10 J Q K 6 7
1 2 3 4 5 6 7 8 9 10 J Q K

In seven steps!! Only, seven steps are required, as mentioned earlier by Ramprasad.

In general, for any decreasing sequence

n n-1 n-2 …. 2 1
First move would be to move the second half of the array just after n.

n n/2-1 n/2 -2 …. 1 n-1 n-2 …n/2

Now, we maintain the invariant that the subarray before and including n, does not have a descent.

On the right of n, find an element a_i such that a_i < a_(i+1) ( does not have a descent ).

Move these two elements to the left of n to maintain the invariant. In fact, one can put a_i at the a_i th

place from the left. Again, it is easy to prove the correctness of this strategy.
Copying verbatim interesting notes from Ramprasad :
Some general notes on this problem. The question of finding the
shortest set of moves to sort any given permutation is not known to be
in P, and not known to be NP-hard or anything either. There are
approximation algorithms for this known and that is how Meena asked me
this question. One of the participants of the workshop had worked on
this problem and we started discussing this when we spoke about his
problem.

One question I asked Meena was, is the decreasing sequence the worst
sequence? And turns out, surprisingly, the answer is no! People ran
some computer analysis and they figured a permutation on 15 and
another on 17 which took more than 8 and 9 respectively! But people
are making the conjecture that for sufficiently large n, the worst
sequence is the decreasing sequence [and some others also believe that
‘large n’ is any n > 17 🙂 ].

— 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