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

Squooh You

Here’s an interesting little puzzle:

Winnie-the-Pooh and Piglet set out to visit one another. They leave their houses at the same time and walk along the same road. But Piglet is absorbed in counting the birds overhead, and Winnie-the-Pooh is composing a new “hum,” so they pass one another without noticing. One minute after the meeting, Winnie-the-Pooh is at Piglet’s house, and 4 minutes after the meeting Piglet is at Winnie-the-Pooh’s. How long has each of them walked? — “A puzzle by S. Sefibekov” viâ Futility Closet

If you’re good at maths, you should see the answer in an intuitive instant. I’m not good at maths, so it took me much longer, because I didn’t understand what was going on. But I can explain the answer like this. Pooh is obviously walking faster than Piglet. Therefore, Pooh and Piglet can’t have met after one minute, because that would mean Pooh takes one minute to walk the distance walked by Piglet in one minute.

So let’s suppose Pooh and Piglet met after two minutes. If Pooh takes one minute to walk the distance walked by Piglet in two minutes, then Pooh is walking twice as fast as Piglet. Does that work? Yes, because Piglet walks Pooh’s distance in four minutes, which is twice as long as Pooh took. Therefore Piglet is walking twice as slowly as Pooh. It’s symmetrical and we can conclude that they did indeed meet after two minutes. Pooh then walks another minute, for three minutes in total, and Piglet walks another four minutes, for six minutes in total.

But guessing is not a good way to find the answer to the puzzle. Let’s try to reason it through properly. Suppose that Pooh and Piglet meet after one unit of time, during which Piglet has walked one unit of distance and Pooh has walked x units of distance, where x > 1. In other words, Pooh is walking x times faster than Piglet. The distances they walk before meeting are therefore in the ratio:

1 : x

Next, note that Pooh will cover the distance Piglet has already walked in 1 unit / x = 1 minute, while Piglet covers the distance Pooh has already walked in x / 1 = 4 minutes. The times they take are therefore in the ratio:

1 / x : x → 1 : x^2 → 1 : 4

And if 1 : x^2 is 1 : 4 (the ratio of the minutes they walk after meeting), then 1 : x (the ratio of the distances they walk before meeting) = 1 : √(x^2) = 1 : √4 = 1 : 2. Pooh is therefore walking 2x faster than Piglet and Piglet is walking 2x slower than Pooh. If Pooh covers Piglet’s distance in 1 minute, Piglet must have taken 2 minutes to walk that distance. And if Piglet covers Pooh’s distance in 4 minutes, Pooh must have taken 2 minutes to walk that distance.

Therefore, when they meet, each of them has been walking for 2 minutes. Pooh therefore walks 2 + 1 = 3 minutes in total and Piglet walks 2 + 4 = 6 minutes in total.

The result can be generalized for all relative speeds. Suppose that Pooh and Piglet meet after m1 minutes and that Pooh then takes m2 minutes to walk the distance Piglet walked in m1 minutes, while Piglet takes m3 minutes to walk the distance Pooh walked in m1 minutes. The time they walk before they meet, m1 minutes, is therefore supplied by this simple equation:

m1 = √(m3 / m2)

And you can call √(m3 / m2), the square root of m3 / m2, the squooh function:

m1 = √(m3 / m2) = squooh(m2,m3)

Now suppose the distance between Pooh’s and Piglet’s houses houses is 12 units of distance and that Piglet always walks at 1 unit a minute. If Pooh walks at the same speed as Piglet, i.e. 1 unit a minute, then:

After they meet, Pooh walks 6 more min = m2, Piglet walks 6 more min = m3.

How long do they walk before they meet?

m1 = m3 / m2 = 1, √1 * 6 = 6

They meet after 6 min.

Now suppose that after they meet, Pooh walks 2 more min, Piglet walks 8 more min.

Therefore, m3 / m2 = 4, √4 * 2 = 2 * 2 = 4 = m1

Therefore they walk for 4 min before they meet and Pooh walks 2x faster than Piglet.

After they meet, Pooh walks 1 more min, Piglet walks 9 more min (m3 / m2 = 9, √9 * 1 = 3)

Therefore they walk for 3 min before they meet and Pooh walks 3x faster than Piglet.

After they meet, Pooh walks 0·6 more min, Piglet walks 9·6 more min (m3 / m2 = 16, √16 * 0·6 = 4 * 0·6 = 2·4)

Therefore they walk for 2·4 min before they meet and Pooh walks 4x faster than Piglet:

After they meet, Pooh walks 0·4 more min, Piglet walks 10 more min (m3 / m2 = 25, √25 * 0·4 = 5 * 0·4 = 2)

Therefore they walk for 2 min before they meet and Pooh walks 5x faster than Piglet.

And so on.

Shareway to Seven

An adaptation of an interesting distribution puzzle from Joseph Degrazia’s Math is Fun (1954):

After a successful year of plunder on the high seas, a pirate ship returns to its island base. The pirate chief, who enjoys practical jokes and has a mathematical bent, hands out heavy bags of gold coins to his seven lieutenants. But when the seven lieutenants open the bags, they discover that each of them has received a different number of coins.

They ask the captain why they don’t have equal shares. The pirate chief laughs and tells them to re-distribute the coins according to the following rule: “At each stage, the lieutenant with most coins must give each of his comrades as many coins as that comrade already possesses.”

The lieutenants follow the rule and each one in turn becomes the lieutenant with most coins. When the seventh distribution is over, all seven of them have 128 coins, the coins are fairly distributed, and the rule no longer applies.

The puzzle is this: How did the pirate captain originally allocate the coins to his lieutenants?


If you start at the beginning and work forward, you’ll have to solve a fiendishly complicated set of simultaneous equations. If you start at the end and work backwards, the puzzle will resolve itself almost like magic.

The puzzle is actually about powers of 2, because 128 = 2^7 and when each of six lieutenants receives as many coins as he already has, he doubles his number of coins. Accordingly, before the seventh and final distribution, six of the lieutenants must have had 64 coins and the seventh must have had 128 + 6 * 64 coins = 512 coins.

At the stage before that, five of the lieutenants must have had 32 coins (so that they will have 64 coins after the sixth distribution), one must have had 256 coins (so that he will have 512 coins after the sixth distribution), and one must have had 64 + 5 * 32 + 256 coins = 480 coins. And so on. This is what the solution looks like:

128, 128, 128, 128, 128, 128, 128
512, 64, 64, 64, 64, 64, 64
256, 480, 32, 32, 32, 32, 32
128, 240, 464, 16, 16, 16, 16
64, 120, 232, 456, 8, 8, 8
32, 60, 116, 228, 452, 4, 4
16, 30, 58, 114, 226, 450, 2
8, 15, 29, 57, 113, 225, 449

So the pirate captain must have originally allocated the coins like this: 8, 15, 29, 57, 113, 225, 449 (note how 8 * 2 – 1 = 15, 15 * 2 – 1 = 29, 29 * 2 – 1 = 57…).

The puzzle can be adapted to other powers. Suppose the rule runs like this: “At each stage, the lieutenant with most coins must give each of his comrades twice as many coins as that comrade already possesses.” If the pirate captain has six lieutenants, after each distribution each of five will have n + 2n = three times the number of coins that he previously possessed. The six lieutenants each end up with 729 coins = 3^6 coins and the solution looks like this:

13, 37, 109, 325, 973, 2917
39, 111, 327, 975, 2919, 3
117, 333, 981, 2925, 9, 9
351, 999, 2943, 27, 27, 27
1053, 2997, 81, 81, 81, 81
3159, 243, 243, 243, 243, 243
729, 729, 729, 729, 729, 729

For powers of 4, the rule runs like this: “At each stage, the lieutenant with most coins must give each of his comrades three times as many coins as that comrade already possesses.” With five lieutenants, each of them ends up with 1024 coins = 4^5 coins and the solution looks like this:

16, 61, 241, 961, 3841
64, 244, 964, 3844, 4
256, 976, 3856, 16, 16
1024, 3904, 64, 64, 64
4096, 256, 256, 256, 256
1024, 1024, 1024, 1024, 1024

For powers of 5, the rule runs like this: “At each stage, the lieutenant with most coins must give each of his comrades four times as many coins as that comrade already possesses.” With four lieutenants, each of them ends up with 625 coins = 5^4 coins and the solution looks like this:

17, 81, 401, 2001
85, 405, 2005, 5
425, 2025, 25, 25
2125, 125, 125, 125
625, 625, 625, 625