Conundrums

I made an honest confession to myself yesterday- I suck at math puzzles. Unless the puzzle has a familiar character, attacking the conundrum is to feel like a monkey trying to pluck a banana using two long wooden sticks. To begin with, he feels confident and sophisticated thanks to the impeccable machinery in possession- sticks and opposable thumbs. But he soon realizes that neither of the sticks is long enough to reach the banana and finds himself unable to conjure a successful contraption with the tools at hand. Incapacity turns into frustration and the monkey begins to gnaw his teeth in exasperation. And finally, he ends up doing what he always wanted to avoid- break the entire creeper with his might for that one measly banana. That's the (similar) feeling that this monkey gets when all intuition fails and one has to resort to the savage way of doing puzzles. And when out pops an elegant solution from a smarter friend or the answers on the back of the book or the bottom of the page, one feels really really stupid.

I spent a nearly half an hour trying to write down the solution to a pretty looking problem that was suggested by Onkar yesterday morning- Given any group of 6 people, prove that you can always find a sub-group of three individuals that has one of the following properties - (a) Everybody knows everybody in that group (b) Nobody knows anybody in that group. (Also, assume that only two kinds of relationships exist between a pair of individuals- they either know each other or they don't; eliminating one-sided acquaintances). I have this infatuation with generalization. Naturally I started playing with variables, started writing comprehensive combinatorial possibilities, applying PHP and doing all sorts of tortuous things that only made life more difficult. Ultimately, I arrived at a solution that I knew was far from elegant as soon as I had finished it. A complicated solution is worth the effort if it leads to new insights about the problem- (say) like what should be the minimum number of people to make the same statement about groups of four, five, etc. But my solution was a mess; brute, lacking any new insight and boring.

But I still felt the relief of solving a problem; or to rephrase, this was how I felt until I heard the solution from Onkar, after which I felt incredibly stupid, like a monkey who's outsmarted by a smarter monkey in the banana game. The elegant solution proceeds like this. Imagine you are one of those five people. Then (convince yourself) that there will be (at least) three people, all of whom are either your acquaintances or completely unfamiliar. Assume without loss of generality that it is the former case (for if it is the latter, the arguments are completely analogous). Now among the three people who are your acquaintances, if you can find two persons who know each other then, combined with you, we have a group of three individuals, all acquaintances of each other. If this does not happen, then we have three individuals, all strangers and we have the required set. Complementary arguments apply if the original set of three are complete strangers to you and it can be trivially seen that one can always find a set of three individuals satisfying either of the two properties required. Incidentally, one needs a minimum of seventeen people (I haven't checked this yet) to be assured of having a sub group of four individuals who are all acquaintances or complete strangers.

Well, I have reconciled myself to this fate of mine- I suck at math puzzles. However, there have been a handful of times when I have felt the bulb glow in my head while working on a puzzle/problem and those times have been memorable. But the great thing about these puzzles even to someone who is fairly mediocre at solving them like me is that solutions often contain brilliant insights that stretch your intuition. In spite of possessing fairly competent analytical skills, people often get their intuition wrong with these puzzles. The best examples come from those involving probabilistic reasoning involving variable change (or conditional probability). I shall quote two examples:

1. The first is the often mentioned Monty Hall Problem or The Game Show Host problem- You are playing a game show where the host shows you three shut doors (A, B, C) and asks you to select one. In one out of the three doors lies the sports car of your dreams while inside the other two, sits a goat each. You select 'door A' because your mother's name starts with the letter 'A' and you think that will bring you luck. The host the opens door 'C' that contains a goat, and asks you, "Mr. K, so would you like to stick with door A or would you like to switch your choice?". The question is, what must you do to maximize the chances of winning the car? Stick or switch?

There used to be a show called 'Khulja Sim Sim' on television some years ago with the same format. And whenever confronted with above question, most people used to stick to their choices. There is a certain sense poetic justice, a moral high ground that people associate with following a set of ideals and that makes them avoid caprice. I am not aware of the statistics of the show but I won't be far from the truth if I claimed that two out of three people who would have stuck to their choices would have ended up with the goat. That's what simple probabilistic bookkeeping tells us. Though I cannot remember the exact details, I think I was properly bowled by this question when I had heard it first as a kid. It is very likely I would have felt that the prudent (and moral) thing to do is to stick to your choice.

Now that I know the solution to the problem (if you switch, you are likely to win the car 2 out of 3 times), I know what was wrong in my thinking so. But since the time I understood the problem, I have posed this question to many people and I have observed that it shocks most of them. It was just yesterday when I communicated the problem and explained its solution to an acquaintance and while he acknowledged the solution he kept wondering that there was some 'deep mathematical flaw' in the reasoning. It is not surprising that when Marilyn vos Savant posed the problem and the solution in 1984, many people, including PhD graduates and professors disagreed with her solution. In spite of the fact that the mathematical reasoning was as clean as a virgin's honeypot (and not terribly difficult either, one had to simply account for the conditional probability) vos Savant arguments had to be validated using computer simulations and mock trials in classrooms. I shall not bother writing down the solution here; it can be looked up online in hundreds of sites.

2. The other problem is called the double toss problem and is much more straightforward compared to the earlier one. The problem goes as this: I have tossed a coin (assume unbiased) twice and I tell you that one of the tosses turned out to be a head. I ask you the probability that the other toss was also a head.

Most respondents (primarily non-mathematicians) tend to answer half as the probability. Their reasoning is simple yet specious - since the tosses are independent why would the outcome of the other toss depend upon this one. While this is true in the literal sense, the context of the problem asks you to go a little deeper. To make a small digression, suppose I told you instead that my first toss was a head and asked you what is the probability that the second toss turned out to be a head. Many people cannot differentiate between this and the original problem. Yet they are fundamentally different.

Let us look at the set of possible outcomes of the two tosses - TT, TH, HT, HH, each with a probability 0.25 with H denoting 'head' and T denoting a 'tail'. Now when I say that 'one of the tosses turned out to be a head', this confines us to the sample space - TH, HT, HH. Now the only case where both the outcomes were a head is the case 'HH' but since it is one of three possible outcomes, the chance associated with it is 0.33. But when I say that 'the first outcome was a 'head'' as in the second case, the set of possible outcomes are - HT and HH. In this case, the probability is 0.5.

Interestingly, even this problem created a lot of controversy leading to lot of experimental validation in spite of a clean mathematical explanation. But the funny part is that the problem was not posed in this form in its original version. The original problem went something like this : You meet a person who confesses to having two children. If she tells you that one of them is a boy, what is the probability that the other one is too. Incidentally, survey forms were dispensed to mothers known to have two children of whom one was a boy to calculate the chance that the other one was too. The survey results showed that 35 % of respondents had a second boy-child, a figure that is close to 33% than to 50%. But it is nonetheless funny that such an experimental validation had to be carried out to resolve a clean mathematical argument (assuming of course that the sex ratio was 1:1).

While I often despair my lack of the fast mathematical intuition to penetrate such simple yet confounding problems, I am happy to know that I can fairly easily grasp the arguments that explain these riddles. I refer to the feeling as 'enjoying artificially sweetened sour grapes' :P.