Combination and Group Problems

Some of these puzzles count and some arrange. The counting ones ask in how many ways a thing can be done, and the traps are the same every time: counting an arrangement twice because it can be turned round or reflected, or missing a case because it looked like another. The arranging ones ask for a schedule, of diners, card players, rowers or walkers, in which every pair meets exactly as often as it should. Those are easy to check once written down and hard to find, and several of Dudeney’s schedules come from a family of designs that mathematicians were still working out in his day.

Every count below was made again by a program, usually by listing the cases one by one, and every schedule was checked pair by pair.

No. 262. Those Fifteen Sheep

No. 263. King Arthur’s Knights

No. 264. The City Luncheons

No. 265. A Puzzle for Card-Players

No. 266. A Tennis Tournament

No. 267. The Wrong Hats

No. 268. The Peal of Bells

No. 269. Three Men in a Boat

No. 270. The Glass Balls

No. 271. Fifteen Letter Puzzle

No. 272. The Nine Schoolboys

No. 273. The Round Table

No. 274. The Mouse-Trap Puzzle

No. 275. The Sixteen Sheep

No. 276. The Eight Villas

No. 277. Counter Crosses

No. 278. A Dormitory Puzzle

No. 279. The Barrels of Balsam

No. 280. Building the Tetrahedron

No. 281. Painting a Pyramid

No. 282. The Antiquary’s Chain

No. 283. The Fifteen Dominoes

No. 284. The Cross Target

No. 285. The Four Postage Stamps

No. 286. Painting the Die

No. 287. An Acrostic Puzzle

Those Fifteen Sheep

The encyclopaedia never said the pens were empty. The farmer had one sheep already in one pen; he drove three into it and four into each of the others, and there were four in every pen. He had placed fifteen sheep.

Answer One pen already held a sheep

King Arthur’s Knights

Second evening: A, F, B, D, G, E, C round the table; third evening: A, E, B, G, C, F, D. Beleobus sat next but one to the king both times, and Galahad three places away, the farthest possible. Beleobus cannot be nearer, because he sat beside Arthur on the first evening; the same goes for Galahad at the other side. A program listed every pair of seatings that keeps the rule and found that this is the only one that does as well, as Dudeney says.

Answer A F B D G E C, then A E B G C F D

The City Luncheons

The labour-saving idea is a rotation: seat A at the first table every day, write down one good first day, and get each later day by moving every other man one step along a fixed cycle of the eleven. Each line is a day and each column a table:

Apart from A, the letters in every column go down in the same cyclic order, B, E, G, F, K, H, I, C, D, L, J. The program confirms that the 66 pairs occur exactly once each.

Answer The eleven days above

A Puzzle for Card-Players

The same rotation as in the City Luncheons does the work: A stays put and the other eleven players move one step along the cycle B, C, …, L each evening, so only the first evening has to be found. Each line is an evening, each group a table, and each pair of letters a partnership:

Dudeney calls it absolutely perfect, and it is: the program finds that every player has every other once as partner and twice as opponent.

Answer The eleven evenings above

A Tennis Tournament

Call the men A, B, D, E and their wives a, b, d, e.

Nobody plays with anyone twice or against anyone twice, and no man ever plays with or against his own wife. Dudeney leaves eight couples on four courts on seven days to the reader.

Answer The three days above

The Wrong Hats

14,833 ways. Follow the hat of the first man. Among $n$ men it goes to one of the other $n - 1$, say to Smith. Either Smith gets the first man’s hat in return, and the other $n - 2$ men must all go wrong among themselves; or he does not, and then, treating the first man’s hat as Smith’s own forbidden hat, the $n - 1$ men other than the first must all go wrong. So the number of ways $W_n$ obeys $$W_n = (n - 1)(W_{n-1} + W_{n-2}),$$ as in $4 \times (2 + 9) = 44$ for five men. Starting from $W_1 = 0$ and $W_2 = 1$, the numbers for one to eight men are 0, 1, 2, 9, 44, 265, 1,854 and 14,833. (Dudeney’s rule, multiply by the number of men and add 1 when it is even, subtract 1 when it is odd, gives the same numbers.) A program that tries all 40,320 ways for eight men agrees. The chance that no man has his own hat is 14,833 in 40,320, a little under three in eight, and it hardly changes however many men there are: it settles down at $1/e = 0.3679\ldots$

Answer 14,833 ways

The Peal of Bells

Since no bell may move more than one place, each change swaps one or both pairs of neighbouring bells, so the peal is a walk through all 24 orders by such swaps; the third rule only stops any bell lingering at either end. A walk that obeys all three is:

Read across the rows. The program checks every condition: all 24 orders once, no bell ever moving more than one place, including from the last change back to the first, and no bell three times running in first or last place.

Answer The peal above

Three Men in a Boat

This is Kirkman’s problem of the fifteen schoolgirls, set in 1850, who walk out in threes on seven days with no two together twice; the boats are the new twist, and ten are enough.

The number over each group is its boat.

No two men go out together twice and no man uses the same boat twice, as the program checks.

Dudeney says that without conditions the men could row in $455^7$ ways. That cannot be right. There are 455 different threes to be chosen from fifteen men, but a day’s rowing divides all fifteen into five threes, which can be done in 1,401,400 ways. His count of 15,567,552,000 schedules in which no two men meet twice has not been checked here.

Answer Ten boats, as above

The Glass Balls

Name the strings A, B, C and D. An order of breaking is an arrangement of four A’s, four B’s, four C’s and four D’s in sixteen places, since the balls on each string must go from the bottom up. A’s balls can take any 4 of the 16 places in 1,820 ways, B’s any 4 of the remaining 12 in 495, C’s any 4 of the last 8 in 70, and D’s take what is left: $$1{,}820 \times 495 \times 70 = 63{,}063{,}000 = \frac{16!}{(4!)^4}.$$

Answer 63,063,000 ways

Fifteen Letter Puzzle

Take the letters A, E, I, O, U, Y and B, C, G, L, M, N, P, R, T:

The first three columns are twenty-seven words; PIU is an Italian musical term, so twenty-six are good English. The program checks that there are thirty-five groups and that every pair of letters appears in exactly one of them, as it must, since thirty-five threes hold 105 pairs and fifteen letters have exactly 105. Dudeney’s first grouping, with A to O and twenty-one words, passes the same test. Which groups are words is his judgement.

Answer Twenty-six good words and PIU

The Nine Schoolboys

Every boy walks beside every other exactly once: the program counts the 36 pairs side by side, each once. Dudeney adds that $12n + 9$ boys can walk like this on $9n + 6$ days; that is his statement.

Answer The six days above

The Round Table

Dudeney gives schedules for every number up to twelve, writing each as a few lines from which the rest follow by moving every person except the fixed ones, which he calls repeaters, one step round a cycle. For six people, for example, 1 is fixed, the others go round $2 \to 3 \to 4 \to 5 \to 6 \to 2$, and the lines 1 2 3 6 4 5 and 1 2 4 5 6 3 each give five sittings. His key lines are:

The middle column gives the fixed people and the cycles. A program writes out every schedule and checks that in each everybody sits exactly once between every pair of the others. All nine are correct. Dudeney says in 1917 that nobody had yet solved thirteen people on sixty-six occasions.

Answer The schedules above

The Mouse-Trap Puzzle

Exchange cards 6 and 13 and begin at 14: the catches come in the order 6, 8, 13, 2, 10, 1, 11, 4, 14, 3, 5, 7, 21, 12, 15, 20, 9, 16, 18, 17, 19. Or exchange 10 and 14 and start at 16, or 6 and 8 and start at 19. A program tried every exchange of two cards and every starting card: these three are the only ways.

Answer Exchange 6 and 13 and begin at 14

The Sixteen Sheep

Here is one way for each number of hurdles replaced, 2 to 7, the moved hurdles in .

A program tried every way of laying the nine hurdles with no loose end and counted the layouts that enclose 6, 6 and 4 sheep: 2 by moving two hurdles, 6 by moving three, then 12, 24, 28 and 16 for four to seven. None needs eight or nine.

Answer Possible for every number from two to seven

The Eight Villas

2,035 ways. Only the four corner houses matter, since each middle house must hold whatever makes its side up to nine; the corners can take any numbers so long as each side’s two corners hold nine or fewer between them. Dudeney counts by putting 9, 8, 7 and so on in one corner in turn, finding 10, 37, 77, 126, 180, 235, 287, 332, 366 and 385 ways. The program counts every choice of corners and agrees.

Answer 2,035 ways

Counter Crosses

The Greek cross can be done in 2,592 ways and the Latin cross in 10,368. The counters add to 45, and the middle one is in both arms, so each arm’s other four make $(45 - m)/2$ with $m$ in the middle: $m$ must be odd. Listing the sets of four for each odd middle gives 4, 3, 4, 3 and 4 ways of splitting the other eight into two sets of equal sum for $m = 1, 3, 5, 7, 9$, eighteen in all. Each set can be arranged on its arm in 24 ways, giving $18 \times 24 \times 24 = 10{,}368$ with the first set upright. A Greek cross can be turned and reflected into eight forms, but only four of them keep the first set upright, so divide by four: 2,592. A Latin cross repeats only in a mirror, which halves the count, but its two sets may also change places between upright and cross-bar, which doubles it again: 10,368. A program that tries all 362,880 placings agrees with both.

Answer 2,592 and 10,368

A Dormitory Puzzle

Thirty-two nuns. Rows run north to south, the stair being the middle of the middle row.

A program checks these six nights and finds that no smaller number of nuns can do all six.

Answer Thirty-two nuns

The Barrels of Balsam

Forty-two ways. Place the barrels in order, 1 first, each in the top or the bottom row. An arrangement is allowed exactly when, at every stage, the top row has at least as many barrels as the bottom, for a barrel put in the bottom row must have a smaller one above it. Six barrels in two rows of three show the pattern: writing T and B for the rows, the allowed orders are TTTBBB, TTBTBB, TTBBTB, TBTTBB and TBTBTB, five of the $\binom63 = 20$ ways of choosing the top row. These are the ballot sequences, and the classical count of them (the Catalan numbers) is the number of choices of the top row divided by one more than its length: $20/4 = 5$, and for ten barrels $\binom{10}{5}/6 = 252/6 = 42$, which is Dudeney’s rule. A program tried every choice of the top row and found 42 and 5.

Answer Forty-two ways

Building the Tetrahedron

3,840 ways. The six sticks can go on the six edges in 720 orders, each either way round, 46,080 in all; and each pyramid can be turned to stand in 12 positions, all of them different placings since the sticks are all different. So there are $46{,}080 / 12 = 3{,}840$ pyramids. The mirror image of a pyramid is a different one, as Dudeney says. The program groups every placing with its turned copies and counts 3,840 groups.

Answer 3,840 ways

Painting a Pyramid

245 ways. The pyramid can be turned to 12 positions. Four different colours can go on in $4! = 24$ orders, which fall into $24/12 = 2$ different pyramids, mirror images. With three colours one is used twice, and which one is the only choice that matters, since every placing of a given set can be turned into every other: 3 ways. Two colours go three and one (2 ways, choosing the single colour) or two and two (1 way): 3. One colour gives 1. Seven colours give 35 choices of four, 35 of three, 21 of two and 7 of one, so $35 \times 2 + 35 \times 3 + 21 \times 3 + 7 = 245$. A program lists all $7^4$ colourings and groups those that turn into one another.

Answer 245 ways

The Antiquary’s Chain

Nine links go in a row in 362,880 orders, 282,240 of them with the two round links apart. The 8-shaped link can be joined by either end, which doubles that, and each of the nine links can lie either side up, a factor of $2^9$. Turning the whole chain over, or end for end, gives the same chain, and no chain is carried into itself by those turns, so the total is divided by four: 72,253,440. The chances against the second smith matching the first are 72,253,439 to 1. The program counts the orders directly.

Answer 72,253,439 to 1

The Fifteen Dominoes

126,720 ways. Leave the doubles out, and think of the numbers 0 to 4 as the corners of a pentagon with all its sides and diagonals: each domino is a line, and a ring of dominoes is a route over every line once. There are 264 such routes. Each double can be put in at either of the two places its number comes up, $2^5$ ways, and each ring can be broken into a line at any of 15 places: $264 \times 32 \times 15 = 126{,}720$. A program counts the lines of dominoes directly and gets the same.

Dudeney adds that the full set of twenty-eight can be laid in 7,959,229,931,520 ways. By the same rule, with seven numbers, each coming up three times, that is the number of routes over all the lines of a heptagon, 129,976,320, times $3^7$ times 28. A short program counts those routes and confirms his figure.

Answer 126,720 ways

The Cross Target

Twenty-one squares; Dudeney sorts them into five sizes, nine, four, four, two and two of each. A program finds every set of four circles forming a square, in any position, and counts 21. Dudeney notes that every square uses one of the six shaded circles, and the program confirms that too.

Answer Twenty-one squares

The Four Postage Stamps

Sixty-five ways. Dudeney counts them by shape: three in a straight line of four, six as a square, twenty-eight as an L, fourteen as a T and fourteen as a zigzag. A program tried every set of four stamps, kept those joined edge to edge, and found sixty-five.

Answer Sixty-five ways

Painting the Die

Forty-eight ways: the 1 can go on any of the six faces, the 2 on any of the four faces next to it, and the 3 on either of the two left, which fixes the rest. That counts each die in all 24 of its positions. A die that may be turned round comes in only two different kinds, mirror images of each other, as the program finds.

Answer Forty-eight, or two different dice

An Acrostic Puzzle

676: twenty-six first letters, each with twenty-six last letters, the square of the number of letters.

Answer 676