Plow-Pair

Futoshiki is fun. It’s a number-puzzle where you use logic to re-create a 5×5 square in which every row and column contains the numbers 1 to 5. At first, most or all of the numbers are missing. You work out what those missing numbers are by using the inequality signs scattered over the futoshiki. Here’s an example:


There are no numbers at all in the futoshiki, so where do you start? Well, first let’s establish some vocabulary for discussing futoshiki. If we label squares by row and column, you can say that square (4,5), just above the lower righthand corner, dominates square (4,4), because (4,5) is on the dominant side of the inequality sign between the two squares (futōshiki, 不等式, means “inequality” in Japanese). Whatever individual number is in (4,5) must be greater than whatever individual number is in (4,4).

Conversely, you can say that (4,4) is dominated by (4,5). But that’s not the end of it: (4,4) is dominated by (4,5) but dominates (3,4), which in its turn dominates (2,4). In other words, there’s a chain of dominations. In this case, it’s a 4-chain, that is, it’s four squares long: (4,5) > (4,4) > (3,4) > (2,4), where (4,5) is the start-square and (2,4) is the end-square. Now, because 5 is the highest number in a 5×5 futoshiki, it can’t be in any square dominated by another square. And because 1 is always the lowest number in a futoshiki, it can’t be in any square that dominates another square. By extending that logic, you’ll see that 4 can’t be in the end-square of a 3-chain, (a,b) > (c,d) > (e,f), and 2 can’t be in the start-square of a 3-chain. Nor can 3 be in the start-square or end-square of a 4-chain.

Using all that logic, you can start excluding numbers from certain squares and working out sets of possible numbers in each square, like this:

[whoops: square contains errors that need to be corrected!]


Now look at column 1 and at row 4:


In column 1, the number 5 appears only once among the possibles, in (1,1); in row 4, the number 1 appears only once among the possibles, in (4,1). And if a number appears in only one square of a row or column, you know that it must be the number filling that particular square. So 5 must be the number filling (1,1) and 1 must be the number filling (4,1). And once a square is filled by a particular number, you can remove it from the sets of possibles filling the other squares of the row and column. I call this sweeping the row and column. Voilà:


Now that the 5 in (1,1) and the 1 in (4,1) have swept all other occurrences of 5 and 1 from the sets of possibles in column 1 and row 4, you can apply the only-once rule again. 2 appears only once in row 4 and 5 appears only once in column 4:


So you’ve got two more filled squares:


Now you can apply a more complex piece of logic. Look at the sets of possibles in row 3 and you’ll see that the set {2,3} occurs twice, in square (3,1) and square (3,4):


What does this double-occurrence of {2,3} mean? It means that if 2 is in fact the number filling (3,1), then 3 must be the number filling (3,4). And vice versa. Therefore 2 and 3 can occur only in those two squares and the two numbers can be excluded or swept from the sets of possibles filling the other squares in that row. You could call {2,3} a plow-pair or plow-pare, because it’s a pair that pares 2 and 3 from the other squares. So we have a pair-rule: if the same pair of possibles, {a,b}, appears in two squares in a row or column, then both a and b can be swept from the three other squares in that row or column. Using {2,3}, let’s apply the pair-rule to the futoshiki and run the plow-pare over row 3:


Now the pair-rule applies again, because {4,5} occurs twice in column 5:


And once the plow-pare has swept 4 and 5 from the other three squares in column 5, you’ll see that 3 is the only number left in square (1,5). Therefore 3 must fill (1,5):


Now 3 can be swept from the rest of row 1 and column 5:


And the pair-rule applies again, because {1,2} occurs twice in row 2:


Once 2 is swept from {2,3,4} in square (2,1) to leave {3,4}, 3 must be excluded from square (2,2), because (2,2) dominates (2,1) and 3 can’t be greater than itself. And once 3 is excluded from (2,2), it occurs only once in column 2:


Therefore 3 must fill (5,2), which dominates (5,1) and its set of possibles {2,3,4}. Because 3 can’t be greater than 4 or itself, 2 is the only possible filler for (5,1) and only 3 is left when 2 is swept from (3,1):


And here are the remaining steps in completing the futoshiki:

The complete futoshiki


Animation of the steps required to complete the futoshiki


Afterword

The pair-rule can be extended to a triplet-rule and quadruplet-rule:

• If three numbers {a,b,c} can occur in only three squares of a row or column, then a, b and c can be swept from the two remaining squares of the row or column.
• If four numbers {a,b,c,d} can occur in only four squares of a row or column, then a, b, c and d can be swept from the one remaining square of the row or column (therefore the number e must fill that remaining square).

But you won’t be able to apply the triplet-rule and quadruplet-rule as often as the pair-rule. Note also that the triplet-rule doesn’t work when {a,b,c} can occur in only two squares of a row or column. An n-rule applies only when the same n numbers of a set occur in n squares of a row or column. And n must be less than 5.


Post-Performative Post-Scriptum

Domination. Exclusion. Inequality. — an earlier look at futoshiki

Domination. Exclusion. Inequality.

Sudoku has conquered the world, but I think futoshiki is more fun — more concentrated, more compact and quicker. When complete, a 5×5 futoshiki will be a Roman square in which every row and column contains the numbers 1 to 5, but no number is repeated in any row or column. You have to work out the missing numbers using logic and the “inequality” signs that show whether one square contains a number more than or less than a number in a neighboring square — futōshiki, 不等式, means “inequality” in Japanese (fu- is the negative prefix). Here’s an example of a futoshiki puzzle:

Futoshiki puzzle, with 4 in square (3,2) and 3 in square (1,1)


If you identify the squares by row and column, 4 is in (3,2) and 3 is in (1,1). And you can say, for example, that the empty square (3,4) dominates the empty square (3,3) or that (3,3) is dominated by (3,4). I’ll describe one route (not the best or most efficient) to completing the puzzle. Let’s start by considering the general rules that 1 cannot appear in any square that dominates another square and that 5 cannot appear in any square dominated by another square.

If you extend that logic, you’ll see that 4 cannot appear in any square that is at the end of what you might call a chain of dominations, where one square dominates a second square that in turn dominates a third square. Therefore, in the puzzle above, 4 cannot appear in squares (2,1) and (4,1) of column 1. And it can’t appear in square (3,1), because that would mean two 4s in the same row. This leaves one place for 4 to appear: square (5,1). And if 4 is there, 5 has to be in square (3,1):


Now look at row 3. Two of the remaining three empty squares are dominators: (3,4) dominates (3,2) and (3,5) dominates (2,5). 1 cannot appear in a dominating square, so 1 has to be in the dominated square (3,3):


The next step I’ll take is a bit more complicated. In row 2, the number 4 cannot be in (2,1) and (2,4). It can’t be in (2,1) because that would mean 4 was greater than itself. And it can’t be in (2,4), because (2,4) is dominated by (3,4) and (3,4) can’t contain 5, the only number that dominates 4. Therefore 4 must be in either (2,3) or (2,4). But so must 5. Therefore (2,3) contains either 4 or 5 and (2,4) contains either 4 or 5. That means that the numbers [1,2,3] must be in the other three squares of row 2. Now, 3 can’t be in square (2,1), because the chain of dominations is too long. And 3 can’t be in (2,5), because (2,5) is dominated by (3,5), which contains either 2 or 3. Therefore 3 must be in (2,2):


Now consider column 2. Square (4,2) cannot contain 1 or 5, because it’s both dominated and dominating. And if it can’t contain 1 or 5, there’s only one number it can contain: 2. And it immediately follows that (4,1) must contain 1, the only number less than 2. And if four squares of column 1 now contain the numbers [1,3,4,5], the remaining empty square (2,1) must contain 2:


Now consider row 2. Squares (2,3) and (2,4) contain either 4 or 5, therefore (2,5) must contain 1:


Now consider row 5. The number 1 is logically excluded from three squares: from (5,3), because there’s a 1 in (3,3); from (5,4), because (5,4) dominates (5,5); and from (5,5), because there’s a 1 in (2,5). Therefore 1 must be in (5,2). And if 1 is in (5,2), the number 5 must be in (1,2):


Now 1 pops up in row 1 because it can only be in (1,4):


And 5 pops up in row 4 because it can only be in (4,5):


Once 5 is in (4,5), the number 4 must be in (4,4) and the number 3 in (4,3):


The 4 of (4,4) immediately collapses the ambiguity of (2,4), which must contain 5. Therefore (2,3) contains 4:


Next, 5 pops up in (5,3):


And 3 must be in (5,4), dominating 2 in (5,5):


With 3 in (5,4) and 2 in (5,5), the ambiguity of (3,4) and (3,5) collapses:


And the square is completed like this:


Here’s an animated version of the steps to completion:

Futoshiki puzzle animated

Russell in Your Head-Roe (Re-Visited)

“Ordinary language is totally unsuited for expressing what physics really asserts, since the words of everyday life are not sufficiently abstract. Only mathematics and mathematical logic can say as little as the physicist means to say.” — Bertrand Russell, The Scientific Outlook (1931)


Previously pre-posted

Russell in Your Head-Roe — Bertrand Russell on mathematics
A Ladd Inane — Bertrand Russell on solipsism
Math Matters — Bertrand Russell on math and physics
Whip Poor Wilhelm — Bertrand Russell on Friedrich Nietzsche

A Ladd Inane

“I once received a letter from an eminent logician, Mrs. Christine Ladd-Franklin, saying that she was a solipsist, and was surprised that there were no others.” — Bertrand Russell, Human Knowledge: Its Scope and Limits (1948)


Peri-Performative Post-Scriptum

The title of this post is, of course, a radical reference to core Jethro Tull album Aladdin Sane (1973).

Pigmental Paradox

From Raymond Smullyan’s Logical Labyrinths (2009):

We now visit another knight/knave island on which, like on the first one, all knights tell the truth and all knaves lie. But now there is another complication! For some reason, the natives refuse to speak to strangers, but they are willing to answer yes/no questions using a secret sign language that works like this:

Each native carries two cards on his person; one is red and the other is black. One of them means yes and the other means no, but you are not told which color means what. If you ask a yes/no question, the native will flash one of the two cards, but unfortunately, you will not know whether the card means yes or no!

Problem 3.1. Abercrombie, who knew the rules of this island, decided to pay it a visit. He met a native and asked him: “Does a red card signify yes?” The native then showed him a red card.

From this, is it possible to deduce what a red card signifies? Is it possible to deduce whether the native was a knight or a knave?

Problem 3.2. Suppose one wishes to find out whether it is a red card or a black card that signifies yes. What simple yes/no question should one ask?

Shick Shtick

Slightly adapted from Joseph Degrazia’s Math is Fun (1954):

Six Writers in a Railway Car

On their way to Chicago for a conference of authors and journalists, six writers meet in a railway club car. Three of them sit on one side facing the other three. Each of the six has his specialty. One writes short stories, one is a historian, another one writes humorous books, still another writes novels, the fifth is a playwright and the last a poet. Their names are Abbott, Blake, Clark, Duggan, Eccles and Farmer.* Each of them has brought one of his books and given it to one of his colleagues, so that each of the six is deep in a book which one of the other five has written.

Abbott reads a collection of short stories. Clark reads the book written by the colleague sitting just opposite him. Blake sits between the author of the short stories and the humorist. The short-story writer sits opposite the historian. Duggan reads a play. Blake is the brother-in-law of the novelist. Eccles sits next to the playwright. Abbott sits in a corner and is not interested in history. Duggan sits opposite the novelist. Eccles reads a humorous book. Farmer never reads poems.

These facts are sufficient to find each of the six authors’ specialties.


*In the original, the surnames were Blank, Bird, Grelly, George, Pinder and Winch.

The Brain in Train

I feel odd when I consider this possibility: that all my thoughts are strictly determined, no more under my control than a straw in a gale or a stone in an avalanche. It seems paradoxical to have strictly determined thoughts about strictly determined thoughts. But is it? And is strict determinism fatal for finding the truth? I don’t think so. In fact, I think that strict determinism is essential for truth. But irrelevant associations get in the way of our understanding this. If our thoughts are determined, they seem like automatic trains running on rigid tracks. We might want to go to the station marked “Truth”, but if the switches are set wrong, the train will never get there. Or it will thunder through and never stop.


Continue reading The Brain in Train

The Brain in Pain

You can stop reading now, if you want. Or can you? Are your decisions really your own, or are you and all other human beings merely spectators in the mind-arena, observing but neither influencing nor initiating what goes on there? Are all your apparent choices in your brain, but out of your hands, made by mechanisms beyond, or below, your conscious control?

In short, do you have free will? This is a big topic – one of the biggest. For me, the three most interesting things in the world are the Problem of Consciousness, the Problem of Existence and the Question of Free Will. I call consciousness and existence problems because I think they’re real. They’re actually there to be investigated and explained. I call free will a question because I don’t think it’s real. I don’t believe that human beings can choose freely or that any possible being, natural or supernatural, can do so. And I don’t believe we truly want free will: it’s an excuse for other things and something we gladly reject in certain circumstances.


Continue reading The Brain in Pain

Neuclid on the Block

How many blows does it take to demolish a wall with a hammer? It depends on the wall and the hammer, of course. If the wall is reality and the hammer is mathematics, you can do it in three blows, like this:

α’. Σημεῖόν ἐστιν, οὗ μέρος οὐθέν.
β’. Γραμμὴ δὲ μῆκος ἀπλατές.
γ’. Γραμμῆς δὲ πέρατα σημεῖα.

1. A point is that of which there is no part.
2. A line is a length without breadth.
3. The extremities of a line are points.

That is the astonishing, world-shattering opening in one of the strangest – and sanest – books ever written. It’s twenty-three centuries old, was written by an Alexandrian mathematician called Euclid (fl. 300 B.C.), and has been pored over by everyone from Abraham Lincoln to Bertrand Russell by way of Edna St. Vincent Millay. Its title is highly appropriate: Στοιχεῖα, or Elements. Physical reality is composed of chemical elements; mathematical reality is composed of logical elements. The second reality is much bigger – infinitely bigger, in fact. In his Elements, Euclid slipped the bonds of time, space and matter by demolishing the walls of reality with a mathematical hammer and escaping into a world of pure abstraction.

• Continue reading Neuclid on the Block

Ear Will An Thee

(This is a guest-review by Norman Foreman, B.A.)

Yr Wylan Ddu, Simon Whitechapel (Papyrocentric Press, ?)

If, like me, you froth at the mouth and roll on the floor biting the carpet when you hear the phrase “Pre-order now”, then relief is at hand. You might have thought that “pre-ordering now” was as logical as “ordering pre-now”. You were wrong. Here is a book that really can be pre-ordered now, because it doesn’t exist yet. If it ever does exist, it will cease to be pre-orderable now. In the meantime, you’re pre-ordering it whether you know it or not. In fact, the less you know, the more you’re pre-ordering it. All life-forms in the Universe, actual and otherwise, are pre-ordering it at this very moment, from the humblest virus to the mightiest hive-mind.

Front cover of yr wylan ddu by slow exploding gulls

Yr Wylan Ddu (2003) by Slow Exploding Gulls

There’s no escape, in other words. And no more review, you might think, given that the book doesn’t exist yet. True, but I can review the title. It’s Welsh, it means “The Black Gull”, and it’s pronounced something like “Ear Will An Thee”. It was also originally the title of an album in 2003 by the Exeter electronistas Slow Exploding Gulls. Whether S.E.G. will object to the appropriation remains to be seen. If they do, it can be pointed out that Dirgelwch Yr Wylan Ddu, or Secret of the Black Gull, was the title of a children’s book by Idwal Jones (1890-1964) published in 1978.

Front cover of Dirgelwch Yr Wylan Ddu by Idwal Jones

Idwal Jones’ Secret of the Black Gull (1978)

There is nothing corresponding to “of” in the original title of that book, but then Welsh grammar doesn’t work like that. Yr Wylan Ddu contains some good examples of how it does work. It’s an active, almost clockwork or organic, phrase compared to its static English equivalent. In isolation, the Welsh words for “the”, “black” and “gull” would be y, du, and gwylan, pronounced something like “ee”, “dee” and “goo-ill-an” in southern Welsh. But put them together and they mutate in more ways than one: Yr Wylan Ddu (adjectives generally follow the noun in Welsh). The similarity between gwylan and “gull” isn’t a coincidence: the English word is borrowed from Celtic.

However, it is unlikely that Yr Wylan Ddu will actually be written in Welsh or any other Celtic language. First, Whitechapel doubtless feels that this would reduce his already small audience. Second, he doesn’t speak Welsh. Or write it. So the book will probably follow past trends and be written in English. It’s also safe to predict that it will refer to at least one black gull. So: pre-order now. And please carry on doing so until further notice.