Math

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.

Advertisements

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.

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?”

Casting out 9s
Most of us know the rule to check whether a number is divisible by 9. You sum the digits of the number and if the result is a multiple of 9, then the number itself is a multiple of 9. For example, 4572 is a multiple of 9 as 4 + 5 + 7 + 2 = 18 (or if you want to go further, 1 + 8 = 9) which is a multiple of 9. But not many of us know why this is so. Why should the numbers sum to a multiple of 9 (or to 9 if you keep summing till you end up with one digit)?

Well, it is because we have a decimal (base 10) number system. Take any general number, say 3587. We have 3587 = 3×1000 + 5×100 + 8×10 + 7×1, and each of the elements in the set {1, 10, 100, 1000,…} is one away from a multiple of 9 {0, 9, 99, 999,…}. This means 3587 is 5 (3 + 5 + 8 + 7 = 23, 2 + 3 = 5) away from a multiple of 9. This in essence is modulo 9 arithmetic; summing the digits gives us the remainder when a number is divided by 9. The same trick works for 3 insofar as checking for divisibility. Casting out 9s is useful to check the correctness of your arithmetic (all 4 basic operations). More on that here.

Can you extend the same logic to check why the following rule holds for divisibility by 11? (A number is divisible by 11 only if you arrive at 0 or 11 while alternately adding and subtracting the digits of the number, eg. 25476 is divisible by 11 as 2 – 5 + 4 – 7 + 6 = 0)