Brain Teasers - 1

Anyone with some interest in mathematics and logic will find solving brain teasers a very rewarding way to pass time. Yes, it is fraught with some dangers of over exertion on some very fiendish puzzles, as is the case with most puzzle solvers worth their salt, they just cannot shut down the process of thinking about a puzzle unless they solve it in some satisfactory way. I too am a little enthusiastic about solving puzzles, though I claim no special intelligence or special skills to demand to be any exceptional in this case. My experience of solving any puzzle has taught me some valuable lessons in structured thinking in solving general problems. For example I will just describe how the following puzzle was solved by me and the corresponding learning from the method employed to solve it.

When a brain teaser or puzzle is posed, Ones' initial aim is to find the key idea to solve this problem. A problem could be solved based on combinatorial reasoning, probabilistic reasoning, pigeon hole principle, logic etc, which is almost always clearly asked for in the problem statement itself. But in some cases, a translation of the problem to some analogical problem only will lead to clues as to the general method to solve it. Some of the guidelines, as followed in good puzzle books, to solve brainteasers are 1) Try to start from simple cases and then generalize to find patterns 2) Try to start from an analogical problem based on your experience in solving puzzles 3) Trying to work backward from the result to construct a method to solve the problem 4) Use of conditions in a clever way, unanticipated in a superficial reading of problem, to lead the way to the key of the puzzle etc etc

Puzzle

There are 60 blue ribbons in a box such that  all 120 ends are hanging out and you cannot see which ends belong to which ribbons. You randomly join all 120 ends together into pretty bows and dump out the box. Depending on chance you will form anywhere from 1 to 60 loops. How many loops would you expect?

Ok. This sounds like a difficult puzzle. Why? This problem sounds very neat and quite simple to understand though. Atleast according to me, a superficial thinking about the puzzle will leave one clueless about the mechanism of increase in number of loops in each step. There are 120!/2^30 different ways of joining the ends of 60 ribbons, a number so large that any cursory glance at solving sigma(P)E(P) will be an undoubtedly daunting task beyond your limit. So we evidently cant solve this problem, using pen and paper by brute force method. (We could very well simulate it in computer but I think this is cheating in a way to solve a puzzle). I grappled with the creation of loops in each step and the expected increase in number of loops for some time. I tried to start from an arbitrary step, where "k" number of ribbons are joined with E(k) number of loops and finding expectation of E(k+1) based on transitional probability. This didnt work without a key idea. That is - How many free ends can one expect at the end of "k" number of ribbons are joined? It is a simple idea, the solving of which was the key to the puzzle. Suffice to say, I wrestled with steps 1, 2 and 3 (as indicated above) in many combinations and performed some messy calculations till step 3 to no avail. I started from backwards, middle (general case), try to think of analogical puzzles (none came to my mind) and was stumped for some time. The key idea still eluded me and thus the solution to puzzle.

But working out the solution using different ways finally had its result.

Pattern recognition is one key component of successful solution of may problems. For example E(1) = 1/119 and E(2) = 2*118/119*117 or 1/119+1/117 which points to a way to solution. Another key thing is to understand the physicality of the whole problem and try visualize the knotting of ribbons and forming of loops in an abstract way. By this time, it became apparent to me that, whether a new ring in formed or not, at every step, the number of free ribbons reduces by 1 each. This was the key idea that I was waiting for, then the expectation calculation can be easily derived for a general case.

Now, coming back to all of earlier reasoning, it was a simple exercise to write a recursion relation for expected knots at the end of tying k ribbons together as follows

E(k) + 1*(60-k)/2*(60-k)*(119-2k)/2 = E(k+1) ------>; (1)

Simplifying

E(k) + 1/(119-2k) = E(k+1) -----------> (2)

Now E(0) = 0. E(1) = 1/119

Thus E(60) = 1/119+1/117+.....+1/3+1 = 3.028933 loops on average, as the answer.

This is a simple and elegant answer which makes immediate sense.

For example, we can see that on an average it is very difficult for the rings to form in beginning, but ring formation will be more common as we reach the end of this exercise.