A short break

Dear Readers,

I will be out of town for a couple of weeks ( till 1st of July 2008 to be precise ). So the blog may not be updated during the period.

Regards,

Saurabh Joshi

Puzzle : A better solution to colour coding cables

Well,

It turns out that there exist a better solution for puzzle related to colour coding of cables.

Once again my brilliant friend Deepanjan came to the rescue and provided a better solution to the above mentioned puzzle.

In the earlier post along the same line, for even number of cables 3 trips were needed where as for odd number of cables 2 trips were needed.

In this solution, I will describe a method to always determine in only 2 trips that which ends belongs to which cable.

Solution : I suggest readers to have a pen and paper handy to comprehend the solution easily.

One assumption made for this solution is that more than two cable ends can be electrically shorted. In which case, if you put continuity meter between any two cable of the bunch, it will show them as connected.

Let us say we have N > 2 cables.

case 1 : N = k(k+1)/2

This case is easy to understand.
We can divide cables into groups of 1, 2, 3 …., k

In every group, all cables belonging to that group is shorted.

Now, we go down ( first trip ). Clearly, we will be able to identify different groups because for cables belonging to group i, continuity meter will show them connected with exactly i-1 other cables.

So we have determined following groups, 1, 2 , …. , k.

Now, we take one cable from each group( 1_1, 2_1, 3_1 …k_1) and short them. First group will be of size k, let us call the group as k’.

Similarly, second group will be of size k-1 ( because group 1 had only one cable, which was consumed in forming group k’)

The last group will have size 1.

Now we go up ( second trip ). Original group of size 1 was determined in the first trip itself. For group 2, if a cable is connected to k-1 other cables then it is 2_1, if it is connected to k-2 other cables then it is 2_2. Similarly we can identify every wire in every group.

case 2 : N = k(k+1)/2 + r where

In this case, we will form groups of size 1,2,…,k,r respectively.

Short all cables in their respective groups. For this example, let us say r = 5. So now, there will be two groups of size 5.

We go down ( first trip ) and identify . We will see two groups of size 5. Somehow, we need to be able to distinguish between them. Without, loss of generality we will put aside.

From rest of the groups, we will again form a group of size k ( call it ) by taking one cable from each group, as described in case 1.

So we will form groups and one remaining group . From , we will keep one cable loose . For the rest of the cable, we will start adding one cable () to , one cable() to and so on. If r=k then it can go only upto .

Now, we will go up ( second trip ). We will find two wires loose ( not connected to any other wire ). But one wire would be from original and one from . So we have identified . Now, from original group if a wire is connected to k different wires then it would be . Similalry we can identify each cable from group depending upon how many other wire it is connected to.

Once, each cable from group is identified, we can proceed to identify cables of other groups as already specified. So, for example, from if a wire is connected to 3 other wires in which one of the wires belong to . We know that, it belongs to . We had added only one wire from in so we will be able to identify the cables. Similarly, for other groups.

This solution is undoubtedly correct with the given assumption. If you do not follow the description easily, work out a small example on pen and paper using above method.

— Saurabh Joshi

Puzzle : A better solution to king’s wine cellar

Well,

Sometimes it happens that you are so much biased to think in one direction that you forget to think that a simpler and better solution might exist from a different direction. I am referring to my post on the king’s wine cellar.

One of my friend Sameer has suggested a very simple and a better solution based on hamming code.

For example, in our case we had 100 wine barrels. Let us number them from 0 to 99. Now, if we convert these numbers into binary, we need 7 bits to represent them. Thus, we need only 7 servants to be put on stake when we want to find out a poisonous wine barrel.

So if 58th wine barrel is poisonous, binary equivalent will be 0111010, so from the right, second, fourth, fifth and sixth servant would have drank from that barrel (because of ‘1’ in those positions) and would have died.

How silly of me not to think about this solution!!!

–Saurabh Joshi

Puzzle : Colour coding cables

Well, this page reminded of me a similar puzzle which I read long back. Copying the problem text below.

Problem :

This is ancient lore – from the time Empire State Building was being built. They had raised the structure successfully, had made all the floors, had built the elevator shaft. They had laid cable inside the elevator shaft. However, just before installing the elevator, they found out the blunder – the cables were not color coded.

They contracted this one electrician and asked him to color code all the wires.

There was a set of N=25 wires running from the top of Empire State Building to the bottom through a cable sheath. The electrician can assume that the wires are all insulated, and the cable sheath is conductive (although this is not necessary for a solution). The only equipment that the electrician has is a continuity meter. He knows how to connect and disconnect wires and how to use the continuity meter.

• How will the electrician color code all the cables? Needless to say, the electrician has to do it in as few climbing-ups and climbing-downs as he can, and as few connections-disconnections (although, this does not carry as much weight) as possible.

  A continuity meter is a voltage source in series with a light bulb. If both ends of a continuous wire are connected to the two ends of the continuity meter, the bulb switches on. If the wire is not continuous, the bulb remains off.

• Once you have a solution, extend it to arbitrary N. (both, N odd, N even.)

Well, this puzzle also goes by other names like cable-car, ropeway cables etc. Here this guy has used cables inside elevator shaft.

Anyways, color coding is needed to identify two ends of a very long cable.

Solution : Well, I am trying to describe the solution with a very small example, but you might need a pen and paper to actually understand it.

I will first prove that we need total 3 trips ( or 1.5 trips if you consider a to and fro journey as a trip ) to determine which end belongs to which wire. You might need an additional trip to actually disconnect wires and color code them. We need 3 trips in case the number of cables are even and greater than 2. I will prove that 2 trips will suffice in case of odd number of cables ( greater than 1 of course, as we don’t need any colour code if there is only 1 cable ).

With given resources, I believe it is impossible to colour code if there are exactly 2 wires.

Anyways, me and my friend Deepanjan both came up with solution. However, his solution is a bit involved so I will describe only my solution here.

Let me give you example with 6 cables. Let A1 to A6 be ends of cables at the top of the building and B1 to B6 be ends of cables at the bottom. Let correspondence between them is A1-B1, A4-B2, A2-B3, A3-B4, A5-B5, A6-B6. The problem is to find this correspondence.

Assume that we start from the top of the building. We will short A1-A4, A2-A3, A5-A6. The labels here are just to verify the correctness. When we actually start we will make pairs by shorting any two wires at a time. So for N wires, we will have N/2 pairs.

Now, we come down ( 1st trip ) and using continuity meter can find three pairs. We will call them B1-B2, B3-B4 and B5-B6. At this point, we have no idea, which pair corresponds to which pair at the top. What we will do now is disconnect all the wires. Now we will short every B(2i) with B(2i+1), so in this case, we will short B2-B3 and B4-B5. B1 and B6 will remain disconnected.

Let us go back up ( 2nd trip ). Again disconnect all connections. We will find two wires ( A1 and A6 ) to be disconnected using continuity meter as they does not form a close loop when the meter is connected between them and any other cable. So A1 = ( B1 or B6 ) and A6 = ( B1 or B6 ). Because A1 = ( B1 or B6 ) we can deduce that A4 ( which was paired with A1 earlier ) must be either B2 or B5. We will find that A4 is connected with A2. So A2 can be either (B4 or B3). Similarly we can deduce following facts :

A1 = ( B1 or B6 )

A4 = ( B2 or B5 )

A2 = ( B3 or B4 )

A3  = ( B4 or B3)

A5 = ( B5 or B2)

A6 = ( B6 or B1 )

We need to only resolve now whether A1 is ( B6 or B1 ). If we can do that, rest all can be determined. So now, we will short A1 with any other wire except A6 ( as it is also having the same possibilities ). Let us say, we short A1-A2.

We will go back down ( 3rd trip ). After disconnecting all connections. We will find that B1 and B3 are connected and rest all are disconnected. That will ensure that A1 was indeed B1. Thus we have correctly determined which end belongs to which wire.

In case, of odd wires things become a bit simpler. Because of odd number, we can only form (N-1)/2 pairs by shorting and one wire will remain loose ( call it A1). When we come down ( first trip ), we will name the loose wire as B1 and rest of the pairs as B2-B3, B4-B5 and so on. Now, we will short B1-B2, B3-B4 and so on. Bn will remain loose.

In the second trip back up, we already know which wire corresponds to B1 ( A1 is the corresponding end in this case ). Now  a cable connected to B1 ( A1 ) will be B2 ( say Ai). Cable which was paired up earlier with Ai will be B3 and so on.

Thus, we need only two trips in case we have odd number of cables.

— Saurabh Joshi

Linked list and probability

Note : Those who saw a flawed solution to “Puzzle : Noodles“, the post has been updated and now contains the correct solution.

This post is about a problem I solved more than 2 year back. Actually, it is a simple problem which was asked to my friend vaibhav gutpa during a technical interview conducted by amazon.

Problem : You are given a singly linked list and the length of the list is not known to you. Write a function which returns an element from the linked list uniformly randomly. You are allowed to traverse the linked list only once.

Solution : Had we been allowed to traverse the list twice, the job would have been easier, as we could just calculate the length n and then select an element with probability 1/n.

As we do not know the length of the list, we can maintain an invariant that the probability of selection of any element seen so far should be inversely proportional to the list traversed so far.

For example, we can initially compare the first two elements and select one element as a winner with probability 1/2. Now we make this winner contend with the third element. Of course, the winner should be given a bit more weightage as it has strugged to come so far. So the winner will be selected with probability 2/3 and the 3rd element with probability 1/3. Had the length of the list been only 3, you can see that winner is selected with probability (1/2)(2/3) = 1/3 or the third element is selected with probability 1/3. Similarly if there is a fourth element, we can choose the winner so far with probability 3/4 and the fourth element with 1/4.

This way we can traverse the entire list once. At the end, winner is guaranteed to have probability of selection as (1/n) if n is the length of the list.

–Saurabh Joshi

Puzzle : Noodles

PS : This post contains a flawed solution followed by a correct solution. Solution posted earlier was flawed as pointed out by vikas in a comment following this post. Fixed solution is written in green.

I stumbled upon this page and saw interesting collection of puzzle. Most of them I had already solved. Found this one particularly interesting.

Problem : There is this weird man who goes to a noodle shop and orders noodle soup. He asks for exactly 100 noodles in his soup.

Once his noodle-soup arrives, he gets to work. He extracts two noodle ends from under the soup, ties a knot, and lets it slip into the soup again. He does the above 100 times – so that now all the noodle ends are tied.

Now he reaches his hand into the soup. What is the probability that he would extract a garland containing all the 100 noodles?

Flawed Solution : Interesting thing to note is that everytime the man chooses those noodle ends which are not tied already. This way in 100 steps the man can tie all the noodle ends. If there is no loose noodle ends then it must be the case that noodles might form a circle. If he can extract a garland containing all the 100 noodles means that he had actually constructed a circle containing 100 noodles.

Initially, me and Deepanjan both went on a slightly wrong direction by actually trying to calculate the probabilities of failure after first step, second step and so on.

After a few minutes I realized that this problem is nothing but to find the number of partitions of a given integer, 100, in this case. So the answer is 1/p(n) = 1/190,569,292

Those of you, who are not able to see the connection between two problems , let me give you an example. Say there are only four noodles. What are the possible configurations of noodles at the end of 4 steps? Following number indicates the size of the circles in each configuration.

4

3 1

2 1 1

2 2

1 1 1 1

This is nothing but to find the number of ways to split a given integer. Once I realized this reduction, wikipedia was handy enough to provide me with the exact figures.

Fixed Solution : The reason why the solution mentioned above was flawed is that it assumed that each end configuration is equally likely, which is not the case.

The correct solution goes like this. At each step we want to calculate the probability that the noodle ends being tied should belong to different noodles. Also, I am giving a generalized solution for any n.

If we are given n noodles. Initially, we have 2n noodle ends. Number of ways to choose one end from these is . Now, the other end should come from a different noodle. Number of ways to choose the second end is . We need to divide this figure by 2 because of symmetry, because for a noodle ends named A and B, B-A or A-B should not be considered as different possibility.

So for the first step we have

For the second step we will have, n-1 different noodles and 2n-2 different noodle ends. We can repeat the same procedure again.

Probability that we can form a garland of all n noodle can be given by

For n=100, Probability of success is :

–Saurabh Joshi

Puzzle : Burning ropes

Many of you must have heard this puzzle.

Problem : There is this special kind of ropes made from some non-homogeneous material. Because of this special material, the rope takes exactly one hour to burn if lighted from one end. However, as the material is not uniform across the rope, different parts of rope may take different amount of time. So for example, one half may take 1 minute where as other half may take 59 minutes to burn.

1) You are given two such ropes and you need to measure 45 minutes.

2) You are given only one such rope and you need to measure 15 minutes.

Solution : Solution to the first one is very simple, the second one is however, not as easy as the first one.

1) We have two ropes A and B. Light A from both the ends and B from one end. When A is finished burning we know that 30 minutes have elapsed and B has 30 minutes remaining. Now, light the other end of B also so that remaining part of B will burn at double speed taking 15 minutes to burn. Thus, we have got 30+15 = 45 minutes.

2) We are given a rope of 1-hour burn time and we need to measure 15 minutes. Doubling the speed is easy by burning  the rope from both the ends but the same is not true when you need to increase the speed four fold.

For example, if you cut a rope into two halves H1 and H2 with burning time 10 and 50 respectively. Now, burning both of them from both the ends does not help as H1 will burn in 5 minutes where as H2 will take 25 minutes.

Anyways, the solution is , you cut the rope into two pieces ( need not be half, because of non-uniformity it does not matter whether you cut at the middle point or not ) P1 and P2. Note that we need to measure 15 minute with 60-minutes burn time rope. Or in short, given a rope of length L( in time when burned from one end ) we need to measure L/4.

Burn, P1 and P2 from both the ends. P1 = 30-x and P2 = 30+x where . Because we are burning from both the ends, P1 will get burnt in 15-(x/2) minutes. For P2 , 30+x – 2*(15-(x/2)) = 2x, because P2 is also burning from both the ends. At the end of 15-(x/2) minutes P2 will have length 2x remaining. To measure exactly 15 minutes we need to measure time x/2 after 15-(x/2) has elapsed.

We are again back to the same problem. We have a rope of length 2x and we need to measure x/2 which is increasing the speed four fold. So, we can keep on repeating this experiment. How long do we need to repeat this? Well, until both the pieces finish burning exactly at the same time. Why?

Say we have a rope of length y and we need to measure y/4. Two pieces P1 and P2 measures y-z and z. When both are lighted from both the ends time taken will be (y-z)/2 and z/2 respectively.

If they finish burning at the same time then

(y-z)/2 = z/2

=> y = 2z

Burning time was z/2 = y/4 which is what we wanted.

–Saurabh Joshi

Handshakes in a party

This is yet another easy problem.
Problem : Prove that in any party there will be at least two persons who have shaken hands with equal number of people.

Solution : Let us say there are n persons attending the party. Obviously, this problem makes sense only when . If no two person have shaken hands with equal number of people then there handshake count must differ at least by 1. So the possible choices for hand shake count would be 0,1,…,n-1. There are exactly n choices and n people. But the catch is that if there exist a person with n-1 handshake count, there can’t be a person with 0 handshake count. Thus reducing the possible choices to n-1. Now, due to pigeon hole principle, we have that at least two person will have the same number of handshake count.

–Saurabh Joshi

Puzzle : King’s poisonous wine cellar

Well,

It has been a couple of days since I have posted anything here. Posting a very simple puzzle over here.

Problem : A king has a wine cellar with 100 drums of wine. A traitor sneaked into his wine cellar to poison the drums. He could mix poison in only one of the drums when guards caught him. However, guards could not see which one drum was poisoned. Our king being a drunkard wishes to be able to drink wine as soon as possible but safely. The poison guarantees that the person drinking the wine would die in 10 days.

Being a king, he can order his servants to drink wine from the drums to find out poisonous drum. However, he wishes does not want to risk lives of too many servants.

1) King wishes to be able to drink some wine on 11th day. How many servant would be needed to take the risk of drinking wine before figuring out a harmless wine drum?

2) King wishes to throw a grand party on 11th day. How many servant would be needed for figuring out the poisonous wine drum?

Solution :

The solution to the first problem is extremely simple and obvious. Only one servant need to drink any one of the wine drum. If the servant dies, all the other drums are harmless. If he does not die, we can guarantee that at least that one wine-drum is harmless.

Well, second problem has actually two sides to it. Say for example, king wishes that number of servant to be put on stake can be arbitrarily large, but the number of servant died during the process should be less. Then, we need 99 servant for each wine drum. At most one servant would die in this case.

However, what if we want to minimize the number of servants to be put on stake? Initially I went on a very wrong direction. That was to use prime factorization of every number from 1 to 100. For example, there will be a servant drinking from wine-drums which are numbered in multiple of 2, and similarly another servant for multiple of 5. So, we would be able to detect number 10 as the poisonous drum if both of them dies. Using this multiple scheme, number of servant needed would be

2,4,8,16,32,64

3,9,27,81

5,25

7,49

all primes number between 1 to 100 which has not appeared in the above list.
Basically, the number comes out to be huge. Certainly a very very bad solution.

A good solution would be to arrange wine-drums in 10×10 maze. We would need only 20 servant. 10 servant for the row and 10 for the column. So when in 10 days i-th servant for row and j-th servant for column dies, we would know that the drum located at (i,j) is the culprit. But still we are far from the best solution.

We can visualize the maze in three dimension. 5x5x5 would need only 15 servants. Of course, there would be some spots empty in the maze, but that does not matter.6x6x3 = 15. Going ahead we can have 5x5x4=14.

It seems we can still push it further. We can visualize the maze in four dimension. 4x3x3x3 = 13. This is the least possible number I could find. I don’t know whether we can push it still further down. If you can figure out a still smaller number, please comment on this post.

–Saurabh Joshi