Posts Tagged ‘puzzle’

Puzzle : A heavy chessboard!

February 11, 2013


I have a thing for dramatic titles! The puzzle that I am about to post here is actually very simple. Without further ado, here it is.

Problem :  There is a standard 8×8 chessboard. Each of its 64 square is assigned a weight. These weights are assigned in such a manner that weight of a square is an average of the weight of the square that it is surrounded by. That is : w(i,j) = w(i-1,j-1) + w(i-1,j) + w(i-1,j+1) + w (i,j-1) + w(i,j+1) + w(i+1,j-1) + w(i+1,j) + w(i+1,j+1)/(num of squares surroinding (i,j)). Of course, the intelligent reader can deduce what would be the formula for the squares lying at the boundary. Now, prove that all the squares have equal weight!

Solution : The solution would require lesser space than the problem description :-). Assume that not all the squares have equal weight. Then there has to be a square whose weight is the least. Weight of this square can not be the average of the weight of the squares surrounding it! Please observe that if there are multiple squares with the least weight, the argument still holds as you will be able to find at least one square which has a neighbour with a higher weight. If not, then all of the squares have the least weight!!

Thanks to Deepanjan for this puzzle!

–Saurabh Joshi


Puzzle : A number game

February 24, 2011


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

Puzzle : Black and White hats!

January 3, 2011


This very nice puzzle was brought to me by Ramprasad.

Problem : Set of people ( infinite ) are standing on a line of natural numbers. That is they are standing at position 1, 2, 3 …. and so on. White or black hats are put randomly on all of them. What strategy can they decide on so that either all of them guess the color of their hat right, or none of them get it right?

Solution : I hope you guyz remember another puzzle on the similar lines. In fact, you better read that post and I am going to refer to the strategy employed there. Remember that in that earlier puzzle, they have to come up with a strategy so that only finitely many of them guesses it wrong. So we partitioned set of all strings into groups such that strings belonging to one group are only finite hamming distance away from each other. And then using axiom of choice we have a representative strings C1,C2…. in each group.

Now, the hint is, suppose you are one of the people standing. What additional information do you need to know whether you guessed it right or wrong? Think about it.

Well, if someone tells you the hamming distance of the string S ( in which you belong ) and the representative string Ci, then you know whether you guessed it right or wrong. Because, if you see that S’ ( all but you ) differs from the representative string by distance d, then you have guessed your color right. If you see the difference at d-1 position, then you know that you are in one of the position where two strings differ so you must have guessed it wrong.

There you go! That is the hint. All of them decide on to guess that the string S differs only at d locations where d is odd. Now, if S differs at locations d’ where d’ is even. All those people at position which does not differ from representative string Ci, they will see the difference of d’. But as decided, they will try to make the distance odd, so they will choose the opposite color as given by the representative string. Hence, all of them will guess it wrong. For a person who is in a position which differs from Ci, he will see the difference of d’-1 ( which is odd ) so he will go with the color mentioned in the representative string and thus guesses it wrong.

it is easy to see that if the distance of S is indeed odd, all of them will get it right.

Cool trick, isn’t it? Well, the solution I thought it by myself, with the hint given by Ramprasad.


Related posts : here, here, here and here

— Saurabh Joshi

Secret Sharing-3

November 26, 2010

As promised in the last post,  I am back with the solutions to the problem we left. There are  couple of solutions when collection of sets is given explicitly. If for example, sets S1 to Sn are given with the constraint that all and only members together from any set should be able to unlock the secret. Given n such sets, there are two solution which are similar in some sense.

First solution, can make the unlocking as hard as possible. That is, there is a brute force way to unlock, even if you are not authorized. In this, we share a secret as n tuple, each co-ordinate in the tuple is of length 1024 ( making it 2^{1024} possibilities ). That is for each set, you have 1024 bit. Choose a secret S and make n copies of it. Now, for each element of the tuple ( that is for each set Si) you can use the XOR method that we mentioned in the first post of the series.

Second solution, again uses tuples, but instead of using the XOR one can use the polynomials. Choose, different polynomial for each co-ordinate of the tuple such that the polynomial constant is secret S. This is again described in the first post.
However, when sets are not given explicitly, the size of the tuple becomes very large if one goes on to enumerate all possible sets which can unlock. The solution which ramprasad had in mind is using circuit with threshold gates. Th_k is a k-threshold gate which becomes one when k or more of the inputs are set to one.

Now, let us see how the circuit for the counter example mentioned in the last post would look like.

The example was as follows. group of 8 persons. 5 or more should be able to unlock the secret. If there are 4, then they would be able to unlock only if there are even of them from the first half ( in turn, there are even of them from each half 🙂 ).

The circuit would look like this

Th_5 \;OR\; (LTh_4)\; OR\; (LTh_2\; AND\; RTh_2)\; OR\; (RTh_4) where LTh and RTh denotes threshold gates for the left and the right half. Note that if we want to enumerate the sets there are {8 \choose 5} + {4 \choose 2}{4 \choose 2} + 2{4 \choose 1} sets. In comparision, having such a circuit is a very efficient solution 🙂

Secret Sharing – 2

November 25, 2010


We have already talked about secret sharing in one of the earlier post. Funny thing happened recently, Ramprasad came up with a question which is a little bit modified. He had a different answer in mind, but I came up with a very simple solution.

Problem : Given a secret S, you have to divide it amongst p1,\dots,p6 such that p1 and p2 together should unlock the secret. Alternatively, p1 or p2 along with three of the other four ( p2 to p6 ) should be able to unlock the secret. However, p2 to p6 together should not be able to unlock the secret.

Solution : I came up with a very simple solution. Take any random polynomial of degree 5 such that the constant term is our secret. Evaluate this polynomial at 10 nonzero random points. Now, give 3 points each to p1 and p2 along with their values. Similarly, distribute one point each to the remaining four persons. See that to construct the original polynomial and hence evaluate it at zero, you need at least 6 points.

For this concrete example this solution is perfectly valid. I was tempted to generalize it as follows.

Let us say that we are given collection of sets. In this case, sets are {1,2},{1,3,4,5},{1,3,4,6} ….. and so on. Meaning, you should be able to unlock the secret when all the members of any set are present. I was tempted to generalize the solution I gave earlier, as follows.

Write it in form of constraints such that we will give each person pi weight wi

So now the constraints will be

\forall i w_i > 0 ( we will give some positive number of points of polynomials to each of them )

\forall _{S_i \in C} \sum _{j \in S_i} w_j \geq 1 ( when all members of any set is present it should unlock the secret ( threshold is 1 )

\forall _{S_i \in C} \forall _{x \in S_i} \sum _{j \in S_i - x} w_j < 1 ( if not all members of the set are present, they should not be able to unlock the secret )

The reason why threshold is taken as 1 is because once we get any feasible solution to this system of inequalities, we can always scale it up, so that all w_i are positive integers and accordingly we will choose threshold T  ( degree T-1 polynomial ). So when collectively when they have T points, they can construct the polynomial and hence, can unlock the secret.

How do we know that the system of inequalities always have the solution? ( if it does, it has infinitely many of them ). Apparently, it is not always possible to have the solution for such a system. Here, any solution defines a hyperplane in n-dimension ( n being total number of people ) such that all the points above it are acceptable and all the points below it are not.

So for collection of sets which demands non-linear surface, this method will not work. Here is a counter-example that ramprasad came up with.

Let us say that there ar 8 persons. You are supposed to divide the secret in the following manner.

  1. If there are 5 or more together, they can unlock
  2. If there  are exactly 4 of them, then if there are even number of them from the first half ( p1 to p4 ) then they should be able to unlock the secret.
  3. Should not be able to unlock in all other cases.

Observe that this gives rise to non-linear partitioning surface.

There are many different generic solution  to this kind of problem. Will talk about it sometime later 🙂

Puzzle : Power game

October 13, 2010


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


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.

heir and tortoiseWhat 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


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

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

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