Archive for August, 2010

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.

I asked him :


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


>


He answered :

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