# Chess mysteries

Some of the best puzzles I’ve ever seen are the Chess Mysteries, created by Raymond Smullyan. They have given me hours and hours of intellectual stimulation.

Here is a typical example from his book ‘Chess Mysteries of Sherlock Holmes’. Consider the following chessboard. Black is in check-mate from White. Which side (north or south) is white, and which side is white?

The first observation is that this is very different from the normal kind of chess puzzle, which is of the type ‘White to mate in 3 moves’ or similar.

So how would you go about solving the seemingly intractable problem of which side is White?

The only clues you have are the ones from the chess board. Obviously, since black is in checkmate, the last move must have been white’s. So what was white’s last move?

Since Black is in check from the White bishop, either the bishop must have moved to administer check, or some other piece must have moved out of the way to discover check from the bishop. Consider the former case.

If the Bishop moved to administer check, where could it have moved from? Obviously only along the main diagonal. But on any square on that diagonal, it would already have been administering check to the king! That would invalidate Black’s previous move, and therefore it is not a valid possibility.

That leaves only the option that something moved out of the way to administer check. What could it have been? Not the queen, because it could have only moved away from b7 to discover check by the bishop, but at b7, the queen would already have been checking the black king. Not the White bishop on c5, obviously - it is on a black square. So it must have been one of the pawns. Either the pawn on d4 moved there from d5, or the pawn on e5 moved there from e4, or the pawn on h3 moved there from g2 (capturing a black piece). In the first of these cases, White is North; in the second and third, White is South. So which of these is it?

We can eliminate the last option straightaway. If there was a pawn on g2 until one move back, how could the white bishop have gotten to h1 in the first place? So no – that option is verboten.

In order to resolve the question of which pawn moved (of e4 and d5), it is necessary to cast your mind one step further back. Assume that the pawn (whichever it was) was moved out of the way to discover check by the bishop. What could Black’s previous move have been? If it was with the King, where could the King have moved from? It could not have moved into a8 (where it currently is) from a7, because at a7 it was in check from both the queen and the bishop on c5, and there is no prior move by white which could have discovered both checks at the same time. Of course it could not have moved from b7, due to the White King’s presence on c3.

So Black’s King could not have moved to a8 from anywhere! It seems an impossible position and a fruitless quest…

But there is another possibility. Could black’s last move have been, not with the King, but instead with another piece? What other piece, I hear you ask. There’s nothing else on the board! Well, it’s true that there’s no other piece on the board now, but there may have been a piece when Black made the last move. That piece was captured by the Bishop to deliver check.

This doesn’t seem to be any more promising, because where did the Bishop come from to capture this piece X?

Then (if you are the kind of person who solves this kind of problem) you will have an epiphany. Perhaps, before the bishop captured the piece X, it wasn’t a bishop at all!

How is that possible? It’s possible if the Bishop was a pawn that got promoted. And since it captured X on promotion, it must have promoted on h1. So white’s last move was bxa8=B.

And Black’s move before that was Xa8. (X could have been a rook or a queen or a knight).

And if white was moving down the board to promote, then obviously, white was playing North.

Nice, no? Here’s a link to Smullyan’s book, if you are interested in this kind of problems: http://www.amazon.com/dp/0486482014. He also came up with a sequel called Chess Mysteries of the Arabian Knights. Both are fantastic.

# The nature of intelligence

I really cannot get yesterday’s audacious idea out of my mind, that there is no such thing as pure mathematics. Why is it so fascinating? I guess one reason is because I have always been fascinated by the nature of intelligence. What it is, where it comes from, how it relates to being human.

I remember when I was about 15 years old, I attended my first talk about AI. It was by a man called Vidyasagar but I wish I could remember more about him. He asked the question, if a computer program comes up with a new theorem in mathematics and proves it, where is the intelligence? In the computer? In the program? In the programmer? In the person who proves that the program works? And he went on to say that his own opinion was the last. It struck me as dreadfully strange. I was to bashful at that time to ask him why, and hoped someone else would, but no one did. So I never knew…

Now, however, I have a slightly better understanding about the nature of mathematics, so I can guess why. Let’s use Egan’s argument as a starting point. In Luminous, he asks (and I have asked this before), could there be a physical system that constitutes a proof of, say, Fermat’s last theorem? A certain configuration of billions of quarks, perhaps, that by its very existence proves it? Egan’s answer is, yes; if nothing else, a certain configuration of neurons in Andrew Wiles’s head is the physical proof of Fermat. This is still a bit bizarre for me to wrap my head around, but if true, then intelligence being defined as the place where the proof dwells is somewhat more acceptable.

The corollary, and this is another of Egan’s favorite themes, is that intelligence is a configuration. It is a certain state of matter and energy, a pattern, that doesn’t have to be spatially or even temporally contiguous. (This is the theme he explores in such detail in Dust.) This, too, mirrors my own belief. Do you remember that scene in Hofstadter’s GEB, where a character called Aunt Hillary is introduced? She is an intelligence that emerges from an ant hill. The ants perform a function in the anthill that mimics neurons in our brain, each ant having no intelligence at all but by their patterns being able to represent thoughts as deeply as any human.

The problem with recognizing this as intelligence is the limitation that we cannot communicate with it. Hofstadter introduces some whimsical way in which this anthill communicates with the world through pheromone trails, but I don’t remember the details.

I do remember thinking, though, that this mirrors a long held belief of mine, that trees are intelligent, albeit in a timescale and space scale that are so different from us that we cannot communicate with them.

At least, not yet. But as we slowly come to terms with artificial intelligence, I have faith that we will establish ways of communication with the millions of non human intelligences that lurk in nature, too.

# Dirty Mathematics

I got my first tangible reward for my conscientious blogging yesterday: Dinesh had commented on my Simulators post, recommending a Greg Egan book called Luminous, and I bought it. An introduction to a new book: what could be more valuable? Thanks, Dinesh .

The book contains a short story of the same name. It’s only about 30 pages long, and by normal standards, I would have polished it off in a single sitting. However, a few pages into the story, the author makes such an incredibly audacious claim that I was completely shell-shocked, gob-smacked, and had to keep the book down and think for several hours before I can get back to it.

What Egan claims is: there is no such thing as pure mathematics.

This is as bold as it gets. Mathematics – isn’t its purity something that we were always brought up to believe in? Men may come and men may go, but maths goes on forever.

Even xkcd concurs:

And Egan disagrees. I love this guy!

According to Egan, even the most abstract theorems in Mathematics – Fermat’s Last, for example – have some physical basis. This may be a property of the real world in some cases (for example geometry modeling the real world). But even the so-called ‘abstract mathematics’ – even pure logic – has a physical basis; it exists as a sequence of thoughts in human brains, and therefore as a sequence of neurotransmitters, perhaps, that fire in a particular sequence in the brain. Alternatively, they exist as patterns of charge and current in a semiconductor wafer; but the point is, whatever the manifestation, there is a manifestation.

We are able to see the truth or falsity of mathematical statements without recourse to experiment because of a series of chemical actions and states in the brain.

So if our brains were wired differently, would we perceive mathematical truths differently? Likely, but it’s not that simple. Animals, for instance, could be said to perceive mathematical truths similar to us (though their deductive and inductive capabilities are much lower than ours).

So what would have to be different for us to perceive maths differently?

Egan asks the question a bit differently. Where, he asks, did mathematics come from? Did it exist before the big bang? Or, shortly after the event, did the early quarks and gluons ‘create’ mathematics? Shortly after, he says. And if physics were different, maths would be different.

I am enormously intrigued by Egan’s suggestion. I want to believe it is true – it appeals to my engineering-centric conceptualization of the universe! But I also have my own reasons for believing that pure mathematics is not so pure after all.

The crux of my opinions around this was developed around an investigation of the way we perceive infinity. We are able to assert (and mathematically substantiate) that a statement like the ‘infinite primes’ theorem (that there are infinitely many prime numbers) must be true. Certainly we do not have the physical experience of infinity in order to establish the validity of this theorem by experiment. How, then, are we able to prove it?

The analogy to explain this is that of a chess puzzle. Say we are given a fairly complex chess position, and are asked to prove something about it; for example, to prove that black can never win from that position. Prima facie, it may appear that such a proof is impossible. Since we do not have a limit on the number of moves that are allowed, even if we comprehensively list all possible moves starting from the current position, we cannot eventually exhaust the infinite length of time for which the moves may go on. What is to say that black will not check-mate in the trillion-trillionth move?

Cast this way, the statement cannot be proved. However, there is another way of establishing the proof. On a chessboard, with a finite number of chess pieces, there are only a finite (though large) number of positions possible. Since any valid chess move is one of these positions, a game of chess is then a way of moving from one chess position to another. For a finite number of positions, there are a finite number of interconnections between the positions. To prove something like the ‘black will not checkmate’ hypothesis, therefore, we do not need to reason infinitely; we need only check (and this can be done with a computer in a finite amount of time) whether it is possible to go from the node representing the current position, to one of the nodes representing a white check-mate. If such a path exists, black can win.

The cleverness here is that we have converted the infinity of chess moves into the ‘finity’ of chess positions. This is the same process that works at multiple meta levels in mathematics to allow us to make general statements about infinite sets of mathematical objects. Because underlying the infinity of mathematical operations, there is the equivalent of a ‘finite chessboard’, which is a combination of all the axioms and rules of inference that our minds accept as true, and which we manipulate to go from ‘truth’ to ‘truth’ in logical sequence.

The frightening question is: is this ‘chessboard’ a feature of neuroscience and physics?

Because if it is – and this is what Egan’s story seems to be about – then ‘pure’ mathematics has the same clay feet as the rest of human knowledge, held up by a complex scaffolding of experimental physics.

I’ll get back to finishing Luminous now…

# T T T

Sitting at the office, burning the midnight oil, I realize today’s blog post is going to be a poetry one. This one by Piet Hein:

Put up in a place

where it is easy to see

T.T.T

When you feel how depressingly

slowly you climb

it’s well to remember that

Things Take Time.

Piet Hein is the Renaissance Man of the 20th century. He was Danish, and he was Danish everything – writer, poet, philosopher, scientist, engineer, freedom fighter, socialite.

I came to be acquainted with Piet Hein because he designed one of the toys of my childhood – the Soma Cube. Piet Hein discovered (or perhaps re-discovered) that if you took all possible concave shapes that can be assembled with 4 or fewer unit cubes, you will find that there are seven of them; and more interestingly, you will find that these seven shapes can be reassembled to form a 3x3x3 cube. This reassembling can be done in a number of different ways, but if you eliminate all rotations and reflections, you come down to 2 ways. You can also assemble from the seven Soma cube cubelets a number of other shapes and figures, which is what makes them fun.

After having played with a lovely rosewood Soma cube for several years in my childhood, I came upon a ‘grook’. That’s what Piet Hein’s poems (like the one above) are called. The first grook I read was quite short:

Love is like

A pineapple:

Sweet, and

Undefinable.

I was going through my ‘crazy rhymes’ period at that point in my life, so I found the rhyme for pineapple quite irresistible. I found out that Piet Hein had created thousands of grooks, and these were required reading (and required quoting) for pretty much all Danish people. I myself spent a lot of time memorizing a fairly sizeable number of grooks in those heady collegiate years.

When I discovered used book stores in the US, I also started collecting grook books. I have seven of them now, and am immensely proud of the effort with which that collection was assembled.

In addition, I found out, Piet Hein had invented a shape: the super-ellipse. This shape was invented in response to a competition to design a traffic roundabout in Stockholm, and Piet Hein’s winning proposal was a kind of squashed ellipse with a beautiful mathematical formula. Piet Hein said about the super-ellipse:

Man is the animal that draws lines which he himself then stumbles over. In the whole pattern of civilization there have been two tendencies, one toward straight lines and rectangular patterns and one toward circular lines. There are reasons, mechanical and psychological, for both tendencies. Things made with straight lines fit well together and save space. And we can move easily — physically or mentally — around things made with round lines. But we are in a straitjacket, having to accept one or the other, when often some intermediate form would be better. To draw something freehand — such as the patchwork traffic circle they tried in Stockholm — will not do. It isn’t fixed, isn’t definite like a circle or square. You don’t know what it is. It isn’t esthetically satisfying. The super-ellipse solved the problem. It is neither round nor rectangular, but in between. Yet it is fixed, it is definite — it has a unity.

Not content with a 2D shape, Piet Hein also invented the super-ellipsoid, which is a 3D variant of the same thing.

And with the super-ellipsoid, he made an interesting gadget: the superegg. The superegg is a small, stainless steel object the size of an egg and the shape of a super-ellipsoid. The inside of it is filled with water, but the outside is completely seamless; if you hold it to your ear and shake it, you will hear the water sloshing around in a faraway sort of way. What you do with a super-ellipsoid is that you keep it in your freezer.

And the purpose of the supereggs is that when you break out the scotch, or the expensive brandy, you pop out the supereggs and drop them in your drink. And voila! – your drink is cooled - without adding ice – without diluting it!

Quite obviously, Piet Hein also had a sense of humour, albeit a rather esoteric one. Needless to say, I am the proud owner of 4 super-eggs, and gladly offer to demonstrate them to anyone who wishes to share a drink with me.

# A very puzzling proof

I have an abiding (if amateur) interest in mathematics, one reason being that (in all modesty) I am good at it.

While my interest a decade back was in problem-solving, I find I am unable to concentrate hard enough to dispatch the problems that would have hardly teased me back then. It’s a worrying trend, and one reason why I want to do the Ironmind.

But I digress. My interest now is primarily in what I would call the ‘philosophy of mathematics’ and this post is about a very interesting proof to an interesting theorem. I first encountered this theorem in high school mathematics, so it’s hardly the dizzying heights of mathematics.

The problem is simple enough to state: Prove that the product of ‘r’ consecutive numbers is divisible by r! (r factorial).

For example, if we pick 5 numbers 83, 84, 85, 86 and 87, we need to prove that their product (83x84x85x86x87) is divisible by 5! (1x2x3x4x5).

The textbook proof to this theorem is using a double-barreled induction, once over the starting number in the sequence and once over the number of numbers in the sequence. It’s a bit tedious, but otherwise not particularly difficult.

I only state this because I want to communicate that yes, this theorem is correct, that it can be proved without any controversy.

Now onto the controversial part.

When I was in class 12, my mathematics teacher gave us a very cute proof of this theorem.

He said, consider the value:

If we can prove that this is an integer, it means the numerator is divisible by the denominator.

Now for a moment, let’s consider a different problem. Say we have 87 people in a room, and we need to pick 5 of them for a lunch treat. How many ways do we have to do this?

We can pick the first person in 87 ways, the second in 86, the third in 85, the fourth in 84 and the fifth in 83 ways. But if we do that, we’ll have repetitions because the order in which we pick people is not important. How many repetitions will we have? This is the number of ways in which we can arrange 5 people, which is 5 times 4 times 3 times 2 times 1.

So the effective number, which is known in high-school mathematics as 87 C 5, or in notation form,

It’s the same number!

And because it represents the number of ways in which we do something, it has to be an integer. You can’t have 8 and a half ways of choosing people, right?

So it’s a neat little proof.

For a very long time since I heard this proof, there was something gnawing at the back of my head about it. I felt there was something a bit spooky about this proof, but I couldn’t put my finger on it.

And then I realized something weird.

This is a different proof because it is an experimental proof of a theorem.

Can you believe that? An experimental proof of a mathematical theorem.

The proof doesn’t base itself on the underlying axioms of mathematics.

It bases itself on the underlying realities of our universe.

The final statement in the proof – the climax – is not that this theorem is the last link in a chain of deductions reasoned from a set of axioms using a set of logical steps.

The climax in the proof is: this number represents a countable quantity in the real world, so it must be a countable number.

Which is very, very weird.

What do you think?