Arabella’s Spider Web

A puzzle by National Security Agency mathematician Katrina J., from the agency’s September 2017 Puzzle Periodical:

Problem:

Arabella the Spider is saving food for the long winter. Arabella wants to store the bugs she caught on 26 fallen leaves, so she can find them later. But, Arabella doesn’t want to waste time by going through any leaves more than once.

In Arabella’s original web, Arabella can’t get to all of the leaves without crossing some of them more than once. But, if Arabella adds just one web between two of the leaves, she can get to every leaf without repeating. [NOTE: The NSA image shown here contains an error — there should be an additional strand between leaves 4 and 22.] There are four different pairs of leaves that Arabella could connect to solve her problem. Can you find all four possible solutions?

Note: Arabella may take any path she chooses as long as she begins on leaf 1 and ends on leaf 26.

Bonus Puzzle:

Can you show why Arabella cannot get to every leaf without repeats on her web as it is now?

	Select Click for Answer
Solution: This problem has 4 solutions and answers: 5-13, 5-22, 18-13, 18-22. Only the first solution is fully drawn on the solution illustration, but all four are explained below. Explanation: First, let’s re-draw the situation to be less messy! Once we’ve organized the leaves a bit, we see that there are 4 distinct groups of leaves which can only be accessed via one leaf: Group 1 is only accessible via leaf 23, Group 2 via leaf 3, Group 3 via leaf 10, and Group 4 via leaf 11. Here we see the problem — once Arabella has entered a group of leaves, she cannot get out again without crossing the ‘access leaf’ again. For Group 1 this is okay, since Arabella can start on leaf 1, move to leaf 6, then leaf 14, then exit at leaf 23, and doesn’t need to go back in. Similarly, Group 4 contains the last leaf, so Arabella can enter the group from leaf 11, then go to leaf 2, leaf 8, leaf 21, leaf 15, and exit at leaf 26. But for Group 2 and Group 3, Arabella must enter and exit the group. This is where the extra web comes in handy! If we connect a leaf in Group 2 and a leaf in Group 3, then Arabella can go from Group 1 to Group 2 using leaf 23, then Group 2 to Group 3 using the new web, and finally from Group 3 to Group 4 using leaf 7. However, not just any leaves from Group 2 and Group 3 will work. Arabella must cover all of Group 2 before moving to Group 3, and cover all of Group 3 before going to Group 4. This still allows for a few different combinations: from Group 2 we can use leaf 5 or leaf 18; from Group 3 we can use leaf 13 or leaf 22. Here are the different paths Arabella could take for each combination (there are minor variations in all of the paths, such as switching the order of leaves 6 and 14, which are unaffected by the solution choice, but we will not list those): Leaves 5 & 13 — 1, 6, 14, 23, 3, 18, 25, 12, 20, 17, 9, 5, 13, 16, 19, 24, 4, 22, 10, 7, 11, 2, 8, 21, 15, 26 Leaves 5 & 22 — 1, 6, 14, 23, 3, 18, 25, 12, 20, 17, 9, 5, 22, 4, 24, 19, 16, 13, 10, 7, 11, 2, 8, 21, 15, 26

Click for Answer

Solution:

This problem has 4 solutions and answers: 5-13, 5-22, 18-13, 18-22. Only the first solution is fully drawn on the solution illustration, but all four are explained below.

Explanation:

First, let’s re-draw the situation to be less messy! Once we’ve organized the leaves a bit, we see that there are 4 distinct groups of leaves which can only be accessed via one leaf: Group 1 is only accessible via leaf 23, Group 2 via leaf 3, Group 3 via leaf 10, and Group 4 via leaf 11.

Here we see the problem — once Arabella has entered a group of leaves, she cannot get out again without crossing the ‘access leaf’ again. For Group 1 this is okay, since Arabella can start on leaf 1, move to leaf 6, then leaf 14, then exit at leaf 23, and doesn’t need to go back in. Similarly, Group 4 contains the last leaf, so Arabella can enter the group from leaf 11, then go to leaf 2, leaf 8, leaf 21, leaf 15, and exit at leaf 26.

But for Group 2 and Group 3, Arabella must enter and exit the group. This is where the extra web comes in handy! If we connect a leaf in Group 2 and a leaf in Group 3, then Arabella can go from Group 1 to Group 2 using leaf 23, then Group 2 to Group 3 using the new web, and finally from Group 3 to Group 4 using leaf 7.

However, not just any leaves from Group 2 and Group 3 will work. Arabella must cover all of Group 2 before moving to Group 3, and cover all of Group 3 before going to Group 4. This still allows for a few different combinations: from Group 2 we can use leaf 5 or leaf 18; from Group 3 we can use leaf 13 or leaf 22.

Here are the different paths Arabella could take for each combination (there are minor variations in all of the paths, such as switching the order of leaves 6 and 14, which are unaffected by the solution choice, but we will not list those):

Leaves 5 & 13 — 1, 6, 14, 23, 3, 18, 25, 12, 20, 17, 9, 5, 13, 16, 19, 24, 4, 22, 10, 7, 11, 2, 8, 21, 15, 26

Leaves 5 & 22 — 1, 6, 14, 23, 3, 18, 25, 12, 20, 17, 9, 5, 22, 4, 24, 19, 16, 13, 10, 7, 11, 2, 8, 21, 15, 26

July 31, 2024July 31, 2024 | Puzzles

Tangle

A maze by Wikimedia user Marianov. Make your way from one black circle to the other.

	Select Click for Answer

July 29, 2024July 28, 2024 | Puzzles

Black and White

NRK chess puzzle

Norwegian broadcaster NRK presented this problem during its coverage of the 2021 FIDE World Chess Championship in Dubai. White is to give mate on the move. (Warning — there’s a trick.)

	Select Click for Answer
It’s natural to suppose that we’re looking at this from Black’s side of the board, but that can’t be the case — if it were, Black could not have swapped king and queen without moving a pawn. So we’re looking at the position from White’s point of view, and that means that Black’s pawns are moving down, not up, the board. So 1. Nd3# immediately ends the game:

July 18, 2024July 17, 2024 | Puzzles

Cryptarithm

A pleasing puzzle by Eric LeVasseur:

PI × R² = AREA

If each letter in this expression (but not the exponent 2) is replaced with a corresponding digit, the resulting equation will be valid. What are the digits?

	Select Click for Answer
96 × 7² = 4704 (Leonard J. Gordon, “Literary Cryptarithmetic by Computer,” Word Ways 23:2 [May 1990], 67-70.) 07/17/2024 UPDATE: Reader Dave Lawrence points out that other solutions are possible: 76 × 8² = 4864 77 × 7² = 3773 86 × 9² = 6966 (Thanks, Dave.) 07/18/2024 Wait, I jumped the gun — these alternatives lack the required one-to-one correspondence between letters and numbers. So I believe LeVasseur’s solution is unique. Thanks to everyone who pointed this out.

Click for Answer

July 17, 2024July 18, 2024 | Puzzles

Alice’s Number

Alice and Bob are two infinitely intelligent logicians. Each has a number drawn on their forehead. Each can see the other’s number but not their own. Each knows that both numbers are positive integers. An observer tells them that the number 50 is either the sum or the product of the two numbers. Alice says to Bob, “I do not know my number,” and Bob replies, “I do not know my number either.” What is Alice’s number?

	Select Click for Answer
If Bob’s number isn’t a divisor of 50, then 50 must be the sum and Alice will know her number. If Bob’s number is 50, then 50 must be the product and again Alice should know her number. She doesn’t, so Bob’s number must be a proper divisor of 50, that is, 1, 2, 5, 10, or 25. By the same reasoning, if Alice’s number isn’t a proper divisor of 50 then Bob should know his number. Also, after Alice’s utterance Bob can infer that his own number is a proper divisor of 50, following her thinking above. So each number is a proper divisor of 50. Now, if 50 is the sum of the two numbers, then both numbers are 25 (as 25 + 25 is the only way to combine two of the candidate divisors to get 50). This means that if Alice’s number isn’t 25, then Bob can conclude that 50 is a product and can infer his own number. The fact that he can’t do this shows that Alice’s number must be 25 (and Bob’s number is either 2 or 25). (Via Matvey Borodin et al., “It’s Common Knowledge,” Recreational Mathematics Magazine 6:12 [December 2019], 9-32.)

Click for Answer

July 11, 2024July 10, 2024 | Puzzles

Rebus

A Brooklyn bookseller distributed this card during the 1880 U.S. presidential race between James Garfield and Winfield Scott Hancock. What does it say?

	Select Click for Answer
“You can bet your last dollar that you will see Garfield defeated by Hancock.” 07/09/2024 UPDATE: Oh, probably it’s “last bottom dollar” — I should have seen that. (Thanks, John.)

July 9, 2024July 9, 2024 | Puzzles

Making the Case

Alexander Shapovalov suggested an unusual coin-weighing problem for the sixth international Kolmogorov math tournament in 2007:

A judge is presented with 80 coins that all look the same, knowing that there are either two or three fake coins among them. All the real coins weigh the same and all the fake coins weigh the same, but the fake coins are lighter than the real ones.

A lawyer knows that there are exactly three fake coins and which ones they are. The lawyer must use a balance scale to convince the judge that there are exactly three fake coins and that it is impossible for there to be only two fake coins. She is bound by her contract not to reveal any information about any particular coin. How should she proceed?

The lawyer might try dividing the 80 coins into three groups of 26, each group containing one fake coin, with two coins left over. With two weighings she could then show that the three groups have the same weight. From this the judge could conclude that either (a) there are 3 fake coins, one in each group, or (b) there are 2 fake coins, both in the leftover group. The lawyer could then weigh one of the leftover coins against a real coin taken from one of the three groups, to show that these balance. This would prove to the judge that there are 3 fake coins (because if there were only 2 then possibility (b) above would be ruled out). However, this strategy is “indiscreet” — it would reveal to the judge the true character of each of the leftover coins, which the lawyer has pledged not to do. How should she proceed instead?

	Select Click for Answer
Divide the coins into nine piles — call them A₁, B₁, C₁, A₂, B₂, C₂, A₃, B₃, and C₃, with sizes 24, 1, 2, 24, 1, 2, 23, 2, 1, respectively. Now use the scale to show that A₁ + B₁, A₂ + B₂, and A₃ + B₃ balance one another, as do B₁ + C₁, B₂ + C₂, and B₃ + C₃. This shows the judge that there are three different ways in which the fake coins might be distributed: one fake coin in each of A₁, A₂, A₃ (sizes 24, 24, 23) one fake coin in each of B₁, B₂, B₃ (sizes 1, 1, 2) one fake coin in each of C₁, C₂, C₃ (sizes 2, 2, 1) Each possibility involves 3 fake coins, not 2, and we’ve managed to convey that fact without revealing the character of any particular coin. (Nicholas Diaco and Tanya Khovanova, “Privacy and Counterfeit Coins,” Mathematical Intelligencer 38:3 [September 2016], 6-10.)

Click for Answer

July 8, 2024July 7, 2024 | Puzzles

Getting There

I just stumbled into this — in October 1967, IBM published this problem in Eureka, the journal of the Cambridge University Mathematical Society (page 2):

The triplets (whose abilities at walking, cycling, and donkey riding are identical) always leave home together at the last possible minute and arrive at school together on the last stroke of the bell.

They used to walk the 4 1/2 miles, and so had to set out at 8.00; then they acquired a bicycle and found that they did not have to leave home until 8.15 (Charles rode it for the first 1 1/2 miles, left it, and walked on; Donald walked 1 1/2 miles, cycled 1 1/2 miles, and walked again; Edward walked 3 miles and cycled the rest). More recently they have been given a donkey. After experiments to determine the donkey’s speed and to verify that it stood stock still when left, they found that — using the bicycle and the donkey — they did not need to leave home until 8.25. There were several schemes of changing over which they could use to do this, of course; but naturally they chose a scheme which involved the minimum number of changes. Going to school tomorrow Charles will start on foot and Edward will arrive on foot. How far will Donald walk?

In place of an answer they listed the address of their London office, as an invitation to prospective systems analysts. I can’t see that they ever published a solution to the puzzle; I’m posting it here for what it’s worth.

07/01/2024 UPDATE: Reader Catalin Voinescu supplies the solution:

Riding the bicycle for 1.5 miles takes 15 fewer minutes than walking the same distance, so the bicycle saves 10 minutes per mile (compared to walking).

Another way to look at it is that riding the bicycle 4.5 miles saves three people 15 minutes, or an aggregate of 45 person-minutes (see ‘man-month’, another concept popular at IBM at the time; ‘The Mythical Man-Month’, an excellent book by Frederick P. Brooks, Jr, explores this in detail).

Riding the donkey 4.5 miles saves a total of 30 person-minutes, or 6 2/3 minutes per mile (compared to walking).

It’s not possible for any person not to change means of transportation, because they would arrive too late (walking) or too early (other means of transportation). For the same reason, it’s not possible for each person to change only once, because whoever got the bike and the donkey and did not walk at all would also arrive too early. Thus, the minimum number of changes is four, with one person walking and riding the donkey, another person walking and riding the bike (not necessarily in this order), and the third doing all three.

The person who walks and rides the bike needs to save 25 minutes, so they need to ride the bike for 2 1/2 miles and walk 2 miles. Assume they do it in this order (see below). The person who switches twice needs to ride the bike for the final 2 miles.

The person who walks and rides the donkey needs to save the same 25 minutes, which, at a rate of 6 2/3 minutes saved per mile, means 3 3/4 mile of riding the donkey and 3/4 mile of walking. They have to walk first and then ride the donkey, because the person who switches twice needs to ride the donkey for the remaining 3/4 mile, and they can only do this at the beginning (we already have them biking at the end).

The person who switches twice rides the donkey for 3/4 mile at the beginning, and bikes for 2 miles at the end. In between, they walk the remaining 1 3/4 mile.

So: Edward bikes 2 1/2 miles then walks 2 miles. Donald rides the donkey 3/4 mile, walks 1 3/4 mile, then rides the bike 2 miles. Charles walks 3/4 mile, then rides the donkey for the remaining 3 3/4 miles.

If we assume the person who walks and rides the bike does them in the opposite order, we get a mirrored solution: Edward rides the donkey for 3 3/4 miles and walks 3/4 mile; Donald rides the bike for 2 miles, walks 1 3/4 mile, then rides the donkey 3/4 mile; and Charles walks 2 miles, then picks up the bike and rides it for the remaining 2 1/2 miles.

In both cases, Donald walks 1 3/4 mile.

Other solutions exist, but they require more than four changes. It’s even possible for the three people to each walk, ride the donkey and bike equal distances (1 1/2 mile of each, each), but I don’t know what minimum number of changes that would require (more than six, and not all 1 1/2 mile stretches can be contiguous).

(Thanks, Catalin.)

July 1, 2024July 1, 2024 | Puzzles

Roll Play

These two handcarts have the same mass. Newton tells us that equal forces applied to equal masses impart equal accelerations. So why does the second handcart pick up speed more quickly than the first? (This is a Soviet problem; Н is the Russian abbreviation for newtons.)

	Select Click for Answer
In each case a force of 2 newtons is acting to set the body in motion. But in the first case the force of gravity acts on the handcart and the weight itself, while in the second the force imparts an acceleration only to the handcart. From V.N. Lange, Physical Paradoxes and Sophisms, 1987.

June 29, 2024June 28, 2024 | Puzzles

Tower Records

From reader Éric Angelini: During a standard chess game, after Black’s fifth move we notice that three rooks have been captured on the same dark square. Which square is it?

	Select Click for Answer
a3. The game runs: 1. b4 a5 2. h4 axb4 3. Rh3 Rxa2 4. Ra3 Rxa3 5. Rxa3 bxa3 The moves are illustrated here (line b). (Thanks, Éric.)

June 26, 2024July 13, 2024 | Puzzles