Month: July 2010

Common knowledge

In this post, I want to talk about some puzzles which deal with common knowledge, or rather a change in the common knowledge. In logic, something is a common knowledge if it is known to all, if they know that they all know it, if they know that they know… so on ad infinitum.

The first one involves cheating husbands. In a village it so happens that  some all the husbands cheat on their wives but the more interesting part is that everyone knows about the cheaters but for the poor wives. The wife of a cheater knows all the cheaters in the village except her husband because if she knew she would surely kill him (No compromises). So they don’t talk to each other about  this cheating business. One day a fakir who always speaks the truth  (as opposed to the truth , the whole truth and nothing but the truth) comes to the village and tells the villagers that there is at least one cheater in the village. What effect if any do the fakir‘s words have on the lives of the villagers?1

An identical problem that had been circulating on the web a while ago concerned a group of 1000 islanders who either had blue eyes or brown eyes. They know the eye colour of every other person but theirs and their religion forbids them from conversing about their eye colours. This was because once they know their eye colour they have to sacrifice themselves to the God (and they are so loyal that they do). Once a foreigner comes to the island and oblivious to these rules exclaimed that he was happy to see at least one other blue eyed person on the island. For the sake of answering the question, we can assume that there are 250 people with blue eyes. Again would the foreigner’s statement in any way affect the islanders?

As always the hard problem (at least it was for me) comes last. A questioner  hands out an envelope each to two people with a number written on them. The  questioner tells them that the two numbers are consecutive (n and n+1). Each person knows the number on his envelope but not on the other person’s. Then he asks them one after  another whether they know what the two numbers are to which they are to reply  either “I know” or “I don’t know” and nothing else. It turns out that after a few such rounds of saying “I don’t know”, one of them suddenly says “I know” following the other person immediately says “Now, I know too”  (Don’t nitpick. The game is over.) What was the logic if any that was used by the two people to come up with the numbers? There was no planning before, no cheating and the two people are eminent logicians.

SPOILER ALERT! Answers in the next paragraph.

In all of the above cases, it so happens the new information radically changes the common knowledge of the group and leads to the death of all the cheating husbands in the first problem and the suicide of all the islanders in 1000 days in the second problem. In the last puzzle, no matter how big the two consecutive numbers are they always get the two numbers in the end if questioned enough number of times.

1.Thanks Anant (LK) for clearing up “some” issues. If all the husbands are not cheaters, then there is a good chance that innocent husbands would get killed.


The Tower of Brahma

Three needles are fixed on a flat plate. On one of these needles are placed sixty-four discs, the largest disc resting on the plate and the others getting smaller and smaller up to the top one. The objective is to move all the discs from one needle to another subject to the following rules. You must only move one disk at a time, and there must never be a smaller disc below a larger one during the transfer. What is the minimum number of moves required to complete the transfer of all the sixty-four discs? (Hint: Start with two discs and then three and so on. Do you see a pattern?)

This puzzle is popularly known as the Tower of Brahma (Tower of Hanoi). Instead of providing a solution, it is interesting to look at another related puzzle which has a lot of similar elements. In fact, it is not much of a puzzle as it is a hint to the previous question.

There was a king who was so pleased with his minister for teaching him the game of chess that he offered him a reward of his choice. The minister asked the king to give him one grain of wheat to put on the first square of the chessboard, two on the second square, four on the third square and so on doubling the number of grains for each square all the way up to the 64th square. The king agreed to his request while silently enjoying the thought that his minister has turned down a golden opportunity to ask for a part of his kingdom or treasury. But he soon realized his folly and had to behead the minister to avoid the shame of being indebted to him.

Well, it turns out that the number of grains of wheat the king had to give the minister equals the number of moves required to transfer the discs from one needle to another and it is such an astronomically huge number1 that the king was left with no other choice. It is said that Lord Brahma placed sixty-four golden discs on diamond needles in a temple in Benares at the moment of Creation. And when all the discs are transferred to another needle, the world along with all his creations will come to an end.

While these two puzzles are relatively simpler, there is another problem which a shopkeeper near my house once asked me. Though I figured out the solution after much effort, I still don’t have any kind of a proof which would take me to the answer. Any help in this regard would be much appreciated. Here’s the question:

He had a weight of mass 40kg which fell down one day and split neatly into four pieces2. On later inspection he realized that he could now weigh any mass from one through forty using these four new pieces. How much do each of the new pieces weigh3?

1. 264 – 1
2. Of course it didn’t happen to him. That’s the way he told me the puzzle.
3. 1kg, 3kg, 9kg and 27kg.

Can’t hear you

With the final match of the 2010 World Cup finals about to start in a few minutes, I decided to post a bit about those annoying little stadium horns called vuvuzelas. Kroor already wrote a post on this and I was wondering what is it about these horns that irritate people. I used to mute the television while watching the matches to prevent further hearing loss (My hearing is bad as it is.)

A standard vuvuzela is tuned roughly to B flat below middle C and has a frequency similar to speech tones. I found the following bit of info on wiki.

Notch filtering, an audio filtration technique, is proposed to reduce the vuvuzela sound in broadcasts and increase clarity of commentary audio. The vuvuzela produces notes at a frequency of approximately 235 Hz and its first partial at 465 Hz. However, this filtration technique affects the clarity of commentary audio. The publication of adaptive filters by universities and organisations address this issue by preserving the amplitude and clarity of the commentators’ voices and crowd noise. Such filtration techniques have been adopted by some cable television providers.

Various vuvuzela filters are available in the market. But Trevor Cox, the president of the Institute of Acoustics (UK) and professor of acoustics at Salford University suspects the  efficacy  of these “notch out”  gadgets.

I’m looking at its wave patterns and there are at least six very strong harmonics in there. It would sound really horrible to notch these out – if one coincides with the vowel sound e, you won’t be able to hear the –es in the commentary. It would sound unnatural. It’s physically impossible to play a sound to cancel out another sound coming from your television. It sounds constant, but the noise is too random to be cancelled out.

So blocking the sound is out of the question as it disrupts commentary. Sound engineers in broadcasting stations have been advised to dip certain frequencies when the massed horns are blowing particularly loudly.

Get used to it. It’s a part of African  footballing culture. says FIFA president Sepp Blatter. This is the same dimwit who had earlier announced that technology has no place in football (Yeah that helps! Ask any England or Mexican fan what they think about that.)

Hearing loss is permanent you see, as the hair cells in the inner ear won’t regenerate. This is why your sense of hearing deteriorates as you grow old. We apparently know very little about how hearing works. We for instance don’t exactly know how the hair cells transform acoustic waves into neural signals which we interpret as sound (source).

Are vuvuzelas going to be banned in future matches? I don’t know. But I really don’t want to watch football matches in mute. Do you?

Science and Mathematics

Mathematics deals with perfection, with absolute truths. Scientific theories on the other hand always have a sense of approximation. Whereas a mathematical statement like the theorem of Pythagoras holds true for all right angled triangles (and hence may be used to define a right angled triangle), scientific theories like the theory of gravitation are subject to constant revision and updating. In science, people come up with hypotheses to explain phenomena. If experiments then corroborate the predictions made by these hypotheses, then they gain credibility and are elevated to the status of a theory and become part of our everyday understanding of the world around us.

Here’s a question which serves to illustrate the difference. You have a chessboard in which two squares from opposite corners are removed. So instead of 64 squares, you now have 62. And you are given 31 dominoes that cover 2 squares each. Is it possible to cover the board with the dominoes? (source : Simon Singh, Fermat’s Last Theorem)

The scientific way to answer this question would be to try filling the board in different ways and see for yourself whether the question permits a solution. After a few dozen attempts you may come to the conclusion that it is not possible to fill the squares with dominoes but still an element of doubt prevails. This is now a theory based on experiment and is readily overturned if even a single counter-example can be produced.

Another way is to argue using logic. You notice that the squares on opposite corners of a chessboard are always of the same colour (say, black). Hence, if you remove those squares you’ll be left with 32 white squares and 30 black squares. Also any two adjacent squares in a chessboard (which we wish to cover using dominoes) must necessarily be of opposite colours. Hence after 30 dominoes, we’ll be left with two white squares and a single domino. But since the two white squares cannot be adjacent, we can conclude with absolute certainty that  it is impossible to fill the squares with the dominoes. It is this absolute nature that gives mathematics its beauty.

Prof. V. Balakrishnan once told us in class that although we (physicists) know that the photon has zero rest mass, the state-of-the-art experiments can only confirm that its mass is less than 10-54 kg. So if the photon has a mass, it must be less than 10-54 kg. This blatant acceptance of its limitations, I believe,  may be why we  would never be able to convince a creationist (or a climate-change denier) of the truth and explanatory power of some of the theories in science. They just don’t understand the way science works1, that there is such a thing called the relativity of wrong. As Asimov nicely puts it:

When people thought the earth was flat, they were wrong. When people thought the earth was spherical, they were wrong. But if you think that thinking the earth is spherical is just as wrong as thinking the earth is flat, then your view is wronger than both of them put together.

The shape of the Earth is not oblate spheroidal either though it is a better approximation still. Now the shape of the Earth has a special name – geoid – which in Greek means “shaped like the Earth” (The mathematics now gets more complicated though.) So our  Earth is a geoid (no surprises there). To me, it is this sense of adventure and exploration, deepening our knowledge  while at the same time remaining humble of its limitations that gives science its beauty.

1. There is this funny little story about the philosopher Ludwig Wittgenstein (1889-1951). Once he asked one of his friends why people always say that it was natural for men to assume that the sun went around the earth rather than the earth was rotating. His friend said: “Well, obviously, because it just looks as if the sun is going around the earth.” To which the philosopher replied: “Well, what would it look like if it had looked as if the earth were rotating?”

Are you my friend?

Are you my friend, my friend?
If so then please do reveal
Whether you feel as I feel
That it sometimes is all just a means to an end.

Isn’t true friendship as Platonic a notion as a perfect triangle?
So feeble, fickle and frivolous
Fed to minds ever so credulous
Who but then find themselves in a tangle

Why don’t you make friends and see you say
Write poems I cannot, but I do try
Make friends I dare not, for I may cry
At least I’m not so unhappy this way.

All the world’s a stage and we all are players
Making friends and forgetting them so fast
Today’s friends are tomorrow’s past
In our constant search for new foyers.

Where can I find a friend, where?
Who’ll my foolish notions upend
You might say that you’ll, my friend
But you’re not there when you’re not there.