Five by Five

knuth latin square puzzle

Computer science legend Donald Knuth offered this puzzle at the 29th International Puzzle Party in San Francisco in August 2009. It’s a partially completed Latin square: The challenge is to place letters in the remaining cells so that each row and column contains the same five letters and in the bottom row these spell a common English word. The solution is unique.

	Select Click for Answer
Two further (harder) Latin square puzzles by Knuth are here. Solutions are here. (Donald Knuth, “Latin Square Word Puzzles,” Word Ways 42:4 [November 2009], 248.)

July 27, 2016August 7, 2016 | Puzzles

Black and White

meyer chess problem

By Heinrich Friedrich Ludwig Meyer. White to mate in two moves.

	Select Click for Answer
1. Bc8! half-pins both black rooks. Now Black has his choice of 23 different rook moves, but each of them allows the white knight to hop into either f4 or g5, giving mate. From the Boy’s Own Paper, 1908.

July 18, 2016July 24, 2016 | Puzzles

Road Work

Fed up with endless traffic detours in 1830, London printer Charles Ingrey published a pointed puzzle, Labyrinthus Londoninensis, or The Equestrian Perplexed.

“The object is to find a way from the Strand [lower left] to St. Paul’s [center], without crossing any of the Bars in the Streets supposed to be under repair.”

Mending our Ways, our ways doth oft-times mar,
So thinks the Traveller by Horse or Car,
But he who scans with calm and patient skill
This ‘Labyrinthine Chart of London’, will
One Track discover, open and unbarred,
That leads at length to famed St. Pauls Church Yard.

The image above is a bit too small to navigate, but the British Library has an interactive zoomable version (requires Flash).

I don’t have the solution, but The Court Journal of Dec. 14, 1833, hints that “the farthest way round is the nearest way home.”

07/06/2022 UPDATE: A solution! (Thanks, Paul.)

July 16, 2016July 7, 2022 | Puzzles

Footwork

A poser from Penn State mathematician Mark Levi’s Why Cats Land on Their Feet (2012):

Using only a stopwatch and a sneaker, how can you find an approximate value for $\sqrt{2}$ ?

	Select Click for Answer
Suspend the sneaker by its lace to make a pendulum. Using the stopwatch, record the number of swings it makes in one minute, and call this n₁. Double the lace to halve its length and again record the number of swings in one minute. Call this n₂. Now $\sqrt{2}\approx n_{2}/n_{1}.$ For better precision, record the number of swings over a longer period of time. To estimate $\sqrt{3}$ , use a lace 1/3 as long, and so on.

Click for Answer

July 15, 2016July 24, 2016 | Puzzles

Hat Check

A puzzle from MIT Technology Review, July/August 2008:

Each of three logicians, A, B, and C, wears a hat that displays a positive integer. The number on one of the hats is the sum of the numbers on the other two. They make the following statements:

A: “I don’t know my number.”

B: “My number is 15.”

What numbers appear on hats A and C?

	Select Click for Answer
A is 10 and C is 5. The situation above, in which A doesn’t know his own number but B knows his after learning this, occurs if and only if (1) A and C have the same number or (2) A = 2C and B = 3C. Here’s the proof. If A and C have the same number, x, then B’s number must be 2x. Knowing this, A can conclude only that his own number must be either x or 3x, so he’ll declare that he doesn’t know his own number. B will see that both A and C bear the number x and declare that his own number is 2x. That takes care of (1). For (2), suppose that C’s number is x, A’s number is 2x, and B’s number is 3x. A can conclude only that his own number is either 2x or 4x, so he declares that he doesn’t know his own number. B can see that his own number must be x or 3x, but he realizes that he can eliminate x since, if that were the case, A would have seen two x‘s and could have concluded that his own number was 2x. So that shows that in cases (1) and (2) A and B will make the declarations presented in the puzzle statement. Now we have to show that these are the only cases that produce these two responses. So consider the three possibilities where A, then C, then B is the sum of the other two. (i) Here suppose C’s number is x, A’s is x + y, and B’s is y. If y = x, then A will see this and can conclude that his own number is 2x. If y ≠ x then A can’t know his own number. B knows that his own number must be either y or 2x + y. Neither of these numbers equals x, so both possibilities are consistent with A’s response, and B can’t know his number. (ii) Suppose C’s number is x + y, A’s is x, and B’s is y. A can’t tell whether his own number is x or x + 2y and so responds negatively. B knows that his number is either y or 2x + y. Neither number equals x + y, so B can’t eliminate either possibility and can’t know his own number. (iii) Here C’s number is x, A’s is y, B’s is x + y, and we know that x ≠ y (the case where x = y is covered under (1) above). So there are two possibilities: — If x > y then A responds negatively and B concludes that his own number must be either x + x or x – y. Neither of these possibilities equals x, so B can’t eliminate either one. — If x < y then A responds negatively and B concludes that his own number must be either x + y or y – x. Since x + y ≠ x, he can’t eliminate x + y. But he can eliminate y – x when y – x = x; that is, when y = 2x. This is (2) above, proving the claim. In this particular case we know that (1) is impossible since B claimed the number 15, an odd number. So (2) must be the case, and 3x = 15.

Click for Answer

A is 10 and C is 5. The situation above, in which A doesn’t know his own number but B knows his after learning this, occurs if and only if (1) A and C have the same number or (2) A = 2C and B = 3C.

Here’s the proof. If A and C have the same number, x, then B’s number must be 2x. Knowing this, A can conclude only that his own number must be either x or 3x, so he’ll declare that he doesn’t know his own number. B will see that both A and C bear the number x and declare that his own number is 2x.

That takes care of (1). For (2), suppose that C’s number is x, A’s number is 2x, and B’s number is 3x. A can conclude only that his own number is either 2x or 4x, so he declares that he doesn’t know his own number. B can see that his own number must be x or 3x, but he realizes that he can eliminate x since, if that were the case, A would have seen two x‘s and could have concluded that his own number was 2x.

So that shows that in cases (1) and (2) A and B will make the declarations presented in the puzzle statement. Now we have to show that these are the only cases that produce these two responses. So consider the three possibilities where A, then C, then B is the sum of the other two.

(i) Here suppose C’s number is x, A’s is x + y, and B’s is y. If y = x, then A will see this and can conclude that his own number is 2x. If y ≠ x then A can’t know his own number. B knows that his own number must be either y or 2x + y. Neither of these numbers equals x, so both possibilities are consistent with A’s response, and B can’t know his number.

(ii) Suppose C’s number is x + y, A’s is x, and B’s is y. A can’t tell whether his own number is x or x + 2y and so responds negatively. B knows that his number is either y or 2x + y. Neither number equals x + y, so B can’t eliminate either possibility and can’t know his own number.

(iii) Here C’s number is x, A’s is y, B’s is x + y, and we know that x ≠ y (the case where x = y is covered under (1) above). So there are two possibilities:

— If x > y then A responds negatively and B concludes that his own number must be either x + x or x – y. Neither of these possibilities equals x, so B can’t eliminate either one.

— If x < y then A responds negatively and B concludes that his own number must be either x + y or y – x. Since x + y ≠ x, he can’t eliminate x + y. But he can eliminate y – x when y – x = x; that is, when y = 2x. This is (2) above, proving the claim.

In this particular case we know that (1) is impossible since B claimed the number 15, an odd number. So (2) must be the case, and 3x = 15.

July 13, 2016July 24, 2016 | Puzzles

Person to Person

The president of a 100-member society receives word that the meeting place must be changed, and he needs to inform the rest of the members. He starts a telephone tree: He informs three members, each of whom informs another three members, and so on until all 100 members have received the news. Using this method, what is the greatest number of members who don’t have to make a call?

	Select Click for Answer
It’s easy enough to work this out by counting: Round #1: 4 members informed (the president plus the 3 members he calls) Round #2: 13 members informed (the original 4 plus the 3 × 3 additional members) Round #3: 40 members informed (the 13 from Rounds #1-2, plus 9 × 3 additional members) Round #4: 100 members informed (the 40 from Rounds #1-3, plus the 60 remaining members, requiring 20 callers) Altogether, 4 + 9 + 20 = 33 members have to make calls, so 67 do not. But it’s easier to work backward. After the president has received the news, 99 members remain to be called. That will require 33 callers.

Click for Answer

June 29, 2016July 10, 2016 | Puzzles

Black and White

Florentine chess problem

From a Florentine manuscript, 1600. White to mate in two moves.

	Select Click for Answer
1. Nb4! Ka5 2.Qc5#.

June 27, 2016July 10, 2016 | Puzzles

Moving Day

Is it possible to pack six 1 × 2 × 2 blocks and three 1 × 1 × 1 blocks into a 3 × 3 × 3 box?

	Select Click for Answer
Yes: Image: Wikimedia Commons The answer comes when we realize that the 1 × 1 × 1 blocks must occupy a diagonal of the box. Each of the 9-cube layers, in every direction, contains an odd number of cubes, but each 1 × 2 × 2 block can fill only an even number of positions (2 or 4). So every layer must contain one 1 × 1 × 1 block. It’s called the Slothouber–Graatsma puzzle, after Dutch architects Jan Slothouber and William Graatsma. Princeton mathematician John Conway invented a more complex puzzle that also yields to an insight regarding parity.

Click for Answer

June 23, 2016July 3, 2016 | Puzzles

Cross Purposes

A perplexing problem from the Pi Mu Epsilon Journal, Spring 1983:

In the little hamlet of Abacinia, the people use two base systems.

One resident says, “26 people use my base, base 10, and only 22 people speak base 14.”

Another says, “Of the 25 residents, 13 are bilingual and 1 is illiterate.”

All the residents speak the truth, but each (naturally) expresses numbers in her own base. How many residents are there?

	Select Click for Answer
Let the first resident speak base b. Then the second speaks base b + 4. By the second resident’s statement, then, the total population is 2(b + 4) + 5 = 2b + 13. And, according to the first speaker, the number of people who speak base b is 2b + 6 and the number who speak base b + 4 is 2b + 2. The second resident says that 1(b + 4) + 3 = b + 7 people speak both bases and 1 is illiterate. So, putting all this together, the total population is (2b + 6) + (2b + 2) + 1 – (b + 7) = 3b + 2. Setting this equal to 2b + 13, we conclude that the two bases are b = 11 and b + 4 = 15. So the total population (in base 10) is 35. (Proposed by Stanley Rabinowitz of Digital Equipment Corp., Merrimack, N.H. The solution is in PMEJ 7:10 [Spring 1984], page 676.)

Click for Answer

June 21, 2016July 3, 2016 | Puzzles

Coming and Going

In 1978 the Chronicle of Higher Education mentioned an old exam question:

Q. How far can a dog run into the woods?

A. Halfway. The rest of the time he is running out.

Harvard’s Richard E. Baym wrote in to take issue with the answer:

The correct answer is ‘All the way’. Certainly we understand that the dog is running ‘in’ only until he reaches the middle of the forest, but this is in fact, all the way in. If the dog ran only half ‘in’, he would not yet be at the middle. Indeed if the dog ran halfway in and then ran halfway out, he would still be in the woods.

The editors noted, “It occurs to us that the dog’s continued presence there would be useful, in case something happens to that tree that we’ve been hearing about since high school physics — the one that falls when no one is in the forest and since there is no eardum to register sound waves, makes no noise. You know what a fine sense of hearing a dog has. Let him run halfway in (or as Mr. Baym argues, all the way), settle there, and keep an ear cocked for that tree.”

(from Robert L. Weber, ed., Science With a Smile, 1992.)

June 11, 2016June 10, 2016 | Puzzles