The Mathematical Craze of the Crossword

In 1924, a new craze swept America. This was not of the same kind as the dance marathons, flagpole sitting and goldfish-eating competitions that gained popularity during this period. No, this was a much less lively pastime. After last week’s post about the Rubik’s Cube, it’s time to move on to a new type of puzzle – the crossword.

Indeed, the New York Times noted the craze of the crossword with alarm, calling it a “sinful waste in the utterly futile finding of words the letters of which will fit into a prearranged pattern, more or less complex.” However, since then, crosswords have become an important part of the daily lives of many not only in the US, but also in the UK. Indeed, a new type of crossword has sprung up which provides another dimension to the puzzle – the cryptic.

Here is an example of a cryptic crossword clue:

BIRDS SIT ON THIS FISH (5)

On the surface, this idea seems ridiculous. However, the aim is to correctly deconstruct the clue so as to find two separate clues, which both give the same answer:

Clue 1: BIRDS SIT ON THIS

Clue 2: FISH

Now our task seems much simpler. We need to find the name of a fish, which is also something which birds sit on. The answer, in this case, is PERCH. From what seemed a difficult task, a clear answer has been obtained.

The above clue needed to be split into two parts in order to be solved – however, this is not the only kind of cryptic clue. Indeed, there are many different rules to follow and different types of clue to consider when solving such a crossword, including anagrams, double-meaning clues and hidden words. The mark of a good clue is often the cleverness of the interpretation required to move from its ‘surface’ (the idea immediately suggested by the clue, such as a bird sitting on a fish in the above example) to its solution.

An interesting aspect of cryptic crosswords is that the people who like to solve them are often not linguists or authors, but scientists and mathematicians. Those from mathematical and IT backgrounds are particularly good at solving these kinds of crosswords, which require the correct deconstruction of difficult clues.

What is it about these puzzles that attracts numerical minds? I have a few ideas. The first is that these crosswords require a certain kind of creative, out-of-the-box way of thinking. It is this kind of thinking that leads to new theories and the solutions of new mathematical problems. There is also a similarity between crossword clues and algebraic expressions. Both have a set of ‘terms’ which change and interact with one another in some way, providing a final ‘solution’. The only real difference is that crossword clues can be interpreted in many different ways, and a certain word or punctuation mark does not always produce the same effect. Mathematicians, unlike crossword solvers, do not spend hours trying to figure out the correct ‘interpretation’ of an algebraic expression – there is only one correct way of looking at it.

I also think it might be related to the ‘penny-drop’ moment when a solver finally comes to the answer of a difficult clue. Personally, it is this satisfaction at the end of a difficult problem that attracts me to both mathematics and crosswords. And I suspect that this is the same for many others.

Moreover, with crosswords as with mathematics, there’s a set of rules to follow – but, like in maths, it isn’t enough just to know these rules. You have to be able to apply them in new situations. This might be the fundamental difference between mathematicians and linguists in terms of their crossword-solving capabilities – language is full of oddities and exceptions that simply do not occur in the mathematical world. A mathematician’s brain is trained to apply rules, a skill which a blank crossword gives it ample opportunity to use.

 

Rubik’s Cube, God’s Number and the Superflip

On the 22nd of November, 2015, a US teenager solved the 3×3 Rubik’s Cube in 4.90 seconds.

Sounds impressive, but if (like most people) you don’t have much experience of the Rubik’s Cube beyond hours and hours of frustration and despair, you probably won’t be able to put that figure into much context.

The number of different combinations (known as ‘permutations’) on the 3×3 version of the cube is 43,252,003,274,489,856,000. And the task of any would-be solver of the cube, whether a professional or bored teenager wanting to kill time, is to organise these into the 1 permutation considered the cube’s ‘solution’.

As most of us know who’ve tried the puzzle without first learning to solve it, this is – if you’ll excuse a major understatement – easier said than done.

Lucas Etter managed to take one of the 43,252,003,274,489,856,000 permutations of the Rubik’s Cube, and convert it into another of these 43,252,003,274,489,856,000 in under 5 seconds.

An interesting aspect of the Rubik’s Cube is something known as ‘God’s Number’. This is the greatest number of moves needed to solve the hardest possible permutation of the cube. In other words, any permutation can be solved in 20 moves or less.Superflip

The most difficult permutation to solve is called the superflip (see right). This is the furthest away from being solved that you can get. It was proven that this permutation could not be solved in anything less than 20 moves. Even with the best computer program in the world, no combination of 19 moves can solve the cube in this position. It has to be 20. This is what led to the consideration the 20 was God’s Number. Of course, as with any mathematical conjecture, it’s not enough just to assume that it is true. You actually have to prove it.

It took a long time to prove this – after all, it’d be impossible to check all 43,252,003,274,489,856,000 permutations. Wouldn’t it? Well, that – in effect – is exactly what was done. Almost. The number of combinations they needed to check was gradually whittled down as it was realised that some permutations are effectively identical. Turn a scrambled Rubik’s Cube upside down, and it still has the same permutation. It’s just – well – upside down. As the number of cases needed to be checked was gradually reduced, the computers and programs used became more and more powerful – powerful enough to check every single permutation. This was done at Google’s Headquarters in San Francisco. This method of checking every available option is called a proof by exhaustion. This is an apt name – finding the proof by this method is, after all, absolutely exhausting.

But the 3×3 is not the only kind of Rubik’s Cube. The largest cube used in competitions is the 7×7 (the ‘V-Cube 7′). I thought about learning to solve this one before learning that it’s only got a small matter of 19 500 551 183 731 307 835 329 126 754 019 748 794 904 992 692 043 434 567 152 132 912 323 232 706 135 469 180 065 278 712 755 853 360 682 328 551 719 137 311 299 993 600 000 000 000 000 000 000 000 000 000 000 000 combinations.

I think I’ll stick with the 3×3.

 

 

The Banana Paradox

The process of mathematical reasoning is one aspect of the subject that fascinates me. But the idea of ‘logic’ could be considered a subject in itself. Logic can be thought of as the systematic study of the form of arguments. A valid argument makes use of assumptions or premises, and comes to a conclusion based on these assumptions.

But what if I told you that we can use logic to gain information about anything by looking at – well – anything? The contents of your local Walmart or Morrisons supermarket can give you minute amounts of evidence about the nature of distant galaxies – things that could not be further from your mind as you wonder down the biscuit aisle during your weekly shop, wondering whether to buy choc-chip cookies or custard creams (or both, in my case).

This idea comes in the form of what I to call the Banana Paradox. There are some different versions of this, but all are essentially the same:

(1) All ravens are black.

(2) Everything that is not black is not a raven.

(3) A banana is not black, and therefore is not a raven.

We have therefore gained evidence to support the idea that all ravens are black -by looking at a banana.

Wikipedia provides a long list of solutions to this problem. But the solution might be quite straightforward:

(4) There are far more black objects than there are ravens.

(5) There is a limited number non-black objects (call this n).

(6) One of these happens not to be a raven.

(7) If all of the non-black objects are also non-ravens, proposition (1) is true.

(8) By proving that 1 of the n non-black objects is indeed not a raven (i.e. proving that the banana is yellow), we have completed a very, very, very small fraction (1/n) of our proof that all ravens are black.

In order to prove the proposition that all ravens are black, we would have to prove that all of the n non-black objects are non-ravens.

This process is not confined only to ravens. You could replace ‘raven’ with ‘planet’ or ‘galaxy’ (with the appropriate colour) and obtain the same result – provided that the assumption of your object of choice having only one colour is a reasonable one to make.

So do not doubt the wisdom of the banana – it can give you a (very, very small) amount of evidence about almost anything you want it to.