A Packing Problem

You need to pack for a midnight flight and the power is out. Your closet contains six pairs of shoes, six black socks, six gray socks, six pairs of brown gloves, and six pairs of tan gloves, but it’s too dark to distinguish colors or to match shoes. How many of each item must you take to be sure of having a matched pair of shoes, two socks of the same color, and a pair of matching gloves?

	Select Click for Answer
Imagine the very worst case: You might pack six non-matching shoes, two non-matching socks, six left-hand gloves of one color, and six right-hand gloves of the other. You can make each of these failures impossible by adding one more item. So you’ll need to pack seven shoes, three socks, and 13 gloves. From Peter Winkler’s excellent collection Mathematical Puzzles, 2021.

April 20, 2021April 19, 2021 | Puzzles

Black and White

heathcote chess problem

This problem, by G. Heathcote, won second prize in the Norwich Mercury‘s “King in the Corner” problem tournament, which required that Black’s king begin each problem in one of the board’s four corners. White to mate in two moves.

	Select Click for Answer
1. Nd2! (Via S.S. Blackburne, Terms and Themes of Chess Problems, 1907.)

April 19, 2021April 17, 2021 | Puzzles

Egg Hunt

A puzzle by Tim C., an applied research mathematician at the National Security Agency, from the agency’s January 2017 Puzzle Periodical:

Alice has a dozen cartons, arranged in a 3×4 grid, which for convenience we have labeled A through L:

She has randomly chosen two of the cartons and hidden an Easter egg inside each of them, leaving the remaining ten cartons empty. She gives the dozen cartons to Bob, who opens them in the order A, B, C, D, E, F, G, H, I, J, K, L until he finds one of the Easter eggs, whereupon he stops. The number of cartons that he opens is his score. Alice then reseals the cartons, keeping the eggs where they are, and presents the cartons to Chris, who opens the cartons in the order A, E, I, B, F, J, C, G, K, D, H, L, again stopping as soon as one of the Easter eggs is found, and scoring the number of opened cartons. Whoever scores lower wins the game; if they score the same then it’s a tie.

For example, suppose Alice hides the Easter eggs in cartons H and K. Then Bob will stop after reaching the egg in carton H and will score 8, while Chris will stop after reaching the egg in carton K and will score 9. So Bob wins in this case.

Who is more likely to win this game, Bob or Chris? Or are they equally likely to win?

	Select Click for Answer
Bob is more likely to win. Label a carton with a “b” (respectively, a “c”) if Bob (respectively, Chris) reaches that carton more quickly, and also record Bob’s (respectively, Chris’s) score upon reaching that carton. Label cartons A and L with “xx” since both players reach those cartons simultaneously. We obtain: xx b2 b3 b4 c2 c5 b7 b8 c3 c6 c9 xx Note that there are five b cartons and five c cartons. So the cases in which Alice selects carton A or carton L are equally split between Bob and Chris. Similarly if Alice selects two b cartons then Bob necessarily wins, but these are balanced out by an equal number of cases in which Alice selects two c cartons and C necessarily wins. The crucial cases occur when Alice selects one b carton and one c carton. Bob wins if the b carton has a lower score than the c carton: b2 and (c3 or c5 or c6 or c9) b3 and (c5 or c6 or c9) b4 and (c5 or c6 or c9) b7 and c9 b8 and c9 Chris wins if the c carton has a lower score than the b carton: c2 and (b3 or b4 or b7 or b8) c3 and (b4 or b7 or b8) c5 and (b7 or b8) c6 and (b7 or b8) Since this yields 12 cases in Bob’s favor and only 11 cases in Chris’s favor, Bob has the advantage.

Click for Answer

April 16, 2021 | Puzzles

Throughput

A bedeviling little puzzle from Dickinson College mathematician David Richeson.

A topologist, it is said, is someone who can’t tell his donut from his coffee mug.

April 10, 2021 | Puzzles · Science & Math

Double Duty

On Nov. 5, 1996, Election Day in the United States, the New York Times crossword puzzle carried a surprising clue:

39. Lead story in tomorrow’s newspaper (!), with 43A

43 across turned out to be ELECTED, but 39 across might be either CLINTON or BOBDOLE — both possibilities had seven letters. Was the Times venturing to guess the outcome of the day’s election?

No. Composer Jeremiah Farrell had contrived each of the seven down clues to admit of two possible answers, so that no matter which candidate won, the newspaper might claim a “correct” result.

Crossword editor Will Shortz called Farrell’s ambiguous effort his favorite puzzle of all time.

(Thanks, Andrew.)

April 7, 2021April 6, 2021 | Puzzles

Moving Day

https://commons.wikimedia.org/wiki/File:All_5_free_tetrominoes.svg — Image: Wikimedia Commons

Will these 5 tetrominoes fit into a 5 × 4 rectangle?

	Select Click for Answer
No. When colored like a checkerboard, the rectangle has an equal number of light and dark squares. So does each of the tetrominoes … with one exception. So the task is impossible.

April 5, 2021April 4, 2021 | Puzzles

Black and White

baird chess problem

A problem “for juvenile solvers” by Edith Baird, from Womanhood, May 1899. White to mate in two moves.

	Select Click for Answer
1. Bg5! leads to two pretty mates: 1. … Kf5 2. Rc5# 2. … Kd6 2. Bf4#

March 30, 2021March 29, 2021 | Puzzles

A Confusing Country

Philosopher Nelson Goodman published this puzzle anonymously in the Boston Post in 1931, at age 24. He later called it “by far the most popular and widely circulated of all my writings.”

All the men of a certain country are either nobles or hunters, and no one is both a noble and a hunter. The male inhabitants are so nearly alike that it is difficult to tell them apart, but there is one difference: nobles never lie, and hunters never tell the truth.

Three of the men meet one day and Ahmed, the first, says something. He says either, ‘I am a noble’, or ‘I am a hunter.’ (We don’t know yet which he said.)

Ali, the second man, heard what Ahmed said, and in reply to a query, answered, ‘Ahmed said, “I am a hunter”.’ Then Ali went on to say, ‘Azab is a hunter.’

Azab was the third man. He said, ‘Ahmed is a noble.’

Now the problem is, which is each? How do you know?

	Select Click for Answer
No one in this country can ever claim to be a hunter — a noble who did so would be lying, and a hunter who did so would be telling the truth. This means that Ali must have been lying when he attributed that claim to Ahmed — which tells us that Ali is a hunter. And if Ali always lies, then his statement that Azab is a hunter is false, which tells us that Azab is a noble. That means that we can trust Azab when he tells us that Ahmed is a noble. (From Goodman’s Problems and Projects, 1972.)

Click for Answer

March 23, 2021March 22, 2021 | Puzzles

Bright Idea

A jailer will send each of a group of n prisoners alone into a certain room. Each prisoner will visit the room infinitely often, but the order of the visits will be determined arbitrarily by the jailer. The prisoners can confer in advance, but once the visits have commenced they can communicate with one another only by means of a light in the room, which they can turn on or off. How can they ensure that some prisoner will eventually be able to determine that everyone has visited the room?

	Select Click for Answer
The prisoners agree that one of them (say, Alice) will try repeatedly to turn the light on, and each of the others will turn it off twice. That is, if Alice finds the light off she’ll turn it on, and if she finds it on she’ll leave it on. Each of the others will turn it off the first two times he finds it on and otherwise leave its state unchanged. Alice counts the number of times she finds the room dark after her first visit. When she’s returned to find the room dark 2n – 3 times, she can announce that everyone has visited the room. Each time Alice returns to the room and finds it dark, that’s a sign that one of the other n – 1 prisoners has visited it. If a prisoner exists who still hasn’t visited the room, then the light can’t have been turned off more than 2(n – 2) = 2n – 4 times. So once Alice’s total exceeds that, reaching 2n – 3, she knows that everyone’s visited the room. (Note that the light’s initial state doesn’t matter: If the first visitor isn’t Alice and he finds the light on, he’ll turn it off, and that sign of his presence won’t be evident to her. But she’ll have to turn the light on again before he can perform his second off-turning, and that ensures that she’ll register his second visit.) (From Peter Winkler’s excellent Mathematical Puzzles: A Connoisseur’s Collection, 2003.)

Click for Answer

March 16, 2021March 15, 2021 | Puzzles

Black and White

steinwig chess problem

A simple but pretty “lightweight” problem by R. Steinweg. White to mate in three moves.

	Select Click for Answer
1. Kc6 Ka7 2. c8=R! Ka6 3. Ra8# From Arthur Ford Mackenzie, Chess Lyrics: A Collection of Chess Problems, 1905.

March 10, 2021March 9, 2021 | Puzzles