Archive for October, 2009

Puzzle : 9 balls

October 9, 2009


Problem was given by manoj, which he in turn found from some website.

Problem : 9 balls, 8 identical and 1 is lighter. You need to find out in 4 weights, which one is lighter. Huh, sounds simpler?? well, hold on. You are given 3 balance weight machines, out of which one is defective. You do not know which one is defective. Also, defective machine can give any outcome ( >, =, < ) irrespective of what you put on the machine. Now, can you find out which ball is lighter weighing only 4 times in total???

Solution : None of us could figure out the solution. But, once we read the solution from the website, deepanjan gave a very nice explanation. I am lazy to draw the figure, so trying out a text based table.

Divide the balls in 3 sets of 3 balls, A, B & C.

On machine m1, measure A and B. Without loss of generality, say it tells that C is the lighter set.

Now, measure A1,B1,C1 vs A2, B2, C2 on machine m2. Again, without loss of generality say it tells us that one of the A3,B3,C3 is lighter.

So we have this

1   |    2   |  3


A |   A1 |  A2  |A3


B |   B1| B2 |B3


C |  C1| C2 |C3

On machine m1 we measured columns and on m2 we measured row. Intersection in this case is C3 ( it could be any cell, but C3 is just a representative )

Now, we measure ( C1,C2) vs (A3,B3) on the third machine. Or in other words, measure two remaining balls of the columns vs 2 remaining  balls of the rows on machine 3.

Case 1 : (C1,C2) = (A3,B3)

In this case, C3, indeed is the lighter ball. Because, two out of three machines are correct. If m1, m2 are correct, they already told C3 is lighter. If, m1 and m3 are correct then m1 says C is a lighter set and m3 says that C1 and C2 are not lighter. so C3 must be the lighter ball. Similarly if m2 and m3 are correct, C3 will still come out as the lighter ball.

Case 2 : (C1,C2) < (A3,B3)

Machine 3, says one of the C1 or C2 is lighter, which is a contradiction to machine 2 which said that one of the A3,B3 or C3 is lighter. Hence, machine 1 must be correct which said C is a lighter set.

Now measure C1 and C2 on machine 1 and find out which one is the lighter ball.

Case 3 : (C1,C2) > ( A3,B3)

Here machine m3 contradictions with machine 1 which said that C is the lighter set. Hence, m2 must be the correct machine. Measure A3,B3 on m2 and find out which one of A3,B3 or C3 is lighter.

Phew!!!! No wonder, it is a math olympiad question.

— Saurabh Joshi


Related post : here


Puzzle : Semi-circle covering n points

October 4, 2009


This is not much of a puzzle. Actually, it is a problem in continuous probability, in which, I am really not good at. This question was posted by saket.  Sagarmoy and Ramprasad could devise a solution, however, I will only describe RP’s solution because of its simplicity.

Problem :

Given n points drawn randomly on the circumference of a circle, what is the probability they will all be within any common semicircle?

Solution :

One might think that there are infinitely many semi-circle on the circumference of a circle. However, the beauty is that we need to consider only n semi-circle here.

If a semi-circle covering all n points, indeed exists, then, a semi-circle covering all n points and starting from one of the points in a clock-wise direction also exists.

So, given a semi-circle which starts at one of the point in clock-wise direction. The probability that the rest of the n-1 points will be in that semi-circle is \frac{1}{2^{n-1}}. So for n such semi-circle, the probability will be \frac{n}{2^{n-1}}

Such a simple solution!! But we really had a hard time when we were trying to solve, because we were focusing too much on the fact that the probability is continuous here.