Senior combinatorics problems (ages 16 to 18)

Answer: 171

1. Let t(n) be the number of tilings of a 2 by n board.
2. Look at the left-hand column. Either a vertical domino covers it (leaving 2 by (n − 1)), or two horizontal dominoes cover the first two columns, or a 2 by 2 square does (each leaving 2 by (n − 2)).
3. So t(n) = t(n − 1) + 2 t(n − 2).
4. Start: t(0) = 1 (the empty board) and t(1) = 1 (one vertical domino).
5. Then t(2) = 3, t(3) = 5, t(4) = 11, t(5) = 21, t(6) = 43, t(7) = 85.
6. t(8) = 85 + 2 × 43 = 171.

Why this works: Tilings of strips satisfy linear recurrences found by asking how the first column is covered. Here t(n) = (2ⁿ⁺¹ + (−1)ⁿ)/3, the Jacobsthal numbers.

Where it leads: t(n) = t(n − 1) + 2t(n − 2) gives the Jacobsthal numbers, (2ⁿ⁺¹ + (−1)ⁿ)/3.

Answer: 68

1. A good string splits into runs of equal letters, each of length 1 or 2, alternating A and B.
2. Once the first letter is chosen (2 ways), the letters are forced by the run lengths, so count sequences of 1s and 2s adding to 8.
3. Let c(n) be the number of sequences of 1s and 2s adding to n: the last part is 1 or 2, so c(n) = c(n − 1) + c(n − 2), with c(1) = 1, c(2) = 2.
4. c(3) = 3, c(4) = 5, c(5) = 8, c(6) = 13, c(7) = 21, c(8) = 34.
5. Total: 2 × 34 = 68.

Why this works: Describing strings by run lengths separates ‘which letter’ (fixed once the first is chosen) from ‘how long each run is’, a composition count.

Where it leads: The compositions of n into 1s and 2s are counted by Fibonacci numbers, so the answer is 2F₉ = 68.

Answer: 120

1. An angle inscribed in a circle is obtuse exactly when it stands on an arc greater than a semicircle; so a triangle is obtuse when its three vertices lie inside an arc smaller than a semicircle.
2. On a regular 12-gon, neighbouring vertices are 30° apart, so ‘less than a semicircle’ means the three vertices lie among 6 consecutive vertices (spanning at most 150°).
3. Count each obtuse triangle from its first vertex going clockwise: choose that vertex (12 ways), then the other two from the next 5 vertices: C(5, 2) = 10.
4. Each obtuse triangle has exactly one such first vertex, so there are 12 × 10 = 120.
5. Check: of C(12, 3) = 220 triangles, 60 are right-angled (a diameter, 6 ways, and a third vertex, 10 ways), and 220 − 120 − 60 = 40 acute.
6. Answer: 120.

Why this works: An inscribed angle is obtuse when it stands on an arc greater than a semicircle. Counting from a canonical starting vertex avoids counting the same triangle several times.

Where it leads: As the number of sides grows, three random vertices form an obtuse triangle with probability approaching 3/4.

Answer: 20

1. The path starts at (0, 0), where both coordinates are even.
2. From an even–even point, one step makes exactly one coordinate odd.
3. The next step must not make both odd, so it must change the same coordinate again, back to even: the path moves in double steps RR or UU between even–even points.
4. So the path is a route on the grid of even points, from (0, 0) to (6, 6) in steps of 2: 3 double steps right and 3 double steps up.
5. Number of routes: C(6, 3) = 20.

Why this works: Spotting an invariant (you can only be at an odd coordinate for one step at a time) turns the problem into a smaller, familiar one.

Where it leads: Shrinking the grid by a factor of 2 turns the problem into ordinary paths from (0, 0) to (3, 3): C(6, 3).

Answer: C, 540

1. Each book goes to one of 3 students: 3⁶ = 729 ways, but some leave a student with nothing.
2. Ways where a particular student gets nothing: 2⁶ = 64. Three students: 3 × 64 = 192.
3. Ways where two particular students get nothing (all books to the third) were subtracted twice: there are 3 of them, so add 3 back.
4. No way leaves all three with nothing.
5. Inclusion–exclusion: 729 − 192 + 3 = 540 (C).

Why this works: ‘Every box non-empty’ is the classic inclusion–exclusion count of onto functions: kⁿ − C(k,1)(k − 1)ⁿ + C(k,2)(k − 2)ⁿ − ….

Where it leads: This is 3! × S(6, 3), where S is a Stirling number of the second kind: surjections onto k students.

Answer: 282

1. Write every number from 0 to 9999 as four digits d₁d₂d₃d₄ (with leading zeros). 0 has digit sum 0, so it never counts.
2. Count solutions of d₁ + d₂ + d₃ + d₄ = 10 with d_i ≥ 0: stars and bars, C(13, 3) = 286.
3. Remove the ones where some ‘digit’ is 10 or more: that digit is 10 and the others 0: 4 cases. (Two digits ≥ 10 is impossible.)
4. So 286 − 4 = 282 numbers below 10 000.
5. 10 000 has digit sum 1, so the answer is 282.

Why this works: Leading zeros make every number the same length so stars and bars applies; the digit cap of 9 is handled by subtracting the few overflows.

Where it leads: Stars and bars with an upper limit needs one round of inclusion–exclusion; larger sums need more rounds.

Answer: C, 13

1. Let a(n) be the number of arrangements of 1 to n with every number at most one place from home.
2. Look at number 1. If it stays in position 1, the other n − 1 numbers form the same problem: a(n − 1) ways.
3. If 1 moves to position 2, position 1 must be filled by 2 (no other number may move that far). So 1 and 2 swap, and the rest is the problem for n − 2: a(n − 2) ways.
4. So a(n) = a(n − 1) + a(n − 2), with a(1) = 1 and a(2) = 2.
5. a(3) = 3, a(4) = 5, a(5) = 8, a(6) = 13 (C).

Why this works: Local rules (each item moves at most one place) force the arrangement into fixed points and adjacent swaps, which gives a Fibonacci recurrence.

Where it leads: a_n = a_n−1 + a_n−2: Fibonacci again, since the arrangements are tilings by ‘stay’ and ‘swap’ pieces.

Answer: 265

1. Let D_n count such arrangements (derangements). D₁ = 0, D₂ = 1.
2. Recurrence: number 1 goes to position k (n − 1 choices). Either k goes to position 1 (leaving D_n−2) or not (behaving like D_n−1). So D_n = (n − 1)(D_n−1 + D_n−2).
3. D₃ = 2(1 + 0) = 2, D₄ = 3(2 + 1) = 9, D₅ = 4(9 + 2) = 44, D₆ = 5(44 + 9) = 265.

Why this works: Splitting on where 1 goes, and whether the number it displaces swaps back, gives a recurrence that avoids listing 720 orders.

Where it leads: D_n/n! tends to 1/e, and D_n is the nearest whole number to n!/e: 720/e ≈ 264.9.

Answer: 377

1. Let a_n be the count for {1, …, n}. Subsets without n: a_n−1. Subsets with n: n − 1 is excluded, leaving a_n−2.
2. So a_n = a_n−1 + a_n−2 with a₁ = 2 ({}, {1}) and a₂ = 3.
3. a₃ = 5, 8, 13, 21, 34, 55, 89, 144, 233, a₁₂ = 377.

Why this works: Conditioning on the largest element gives a Fibonacci recurrence.

Where it leads: a_n = F_n+2. Counting by size instead gives F_n+2 = Σ C(n − k + 1, k): Fibonacci numbers are diagonal sums of Pascal’s triangle.

Answer: 57

1. Arrange the set in increasing order: a, a + d, a + 2d, a + 3d with d ≥ 1. Each set gives exactly one (a, d).
2. Need a + 3d ≤ 20, so a has 20 − 3d choices, and d ≤ 6.
3. Sum: 17 + 14 + 11 + 8 + 5 + 2 = 57.

Why this works: Matching each set to its first term and common difference makes the count a simple sum over d.

Where it leads: Van der Waerden’s theorem: colour 1 to N in two colours; for N large enough there is always a one-coloured arithmetic sequence of length 4 (N = 35 suffices, and is the smallest).

Answer: C, 68

1. Without the limit: stars and bars, C(10 + 3, 3) = 286.
2. A particular box has at least 5: pre-place 5, share the other 5 freely: C(8, 3) = 56. Four boxes: 224.
3. Two particular boxes with at least 5 each: all 10 used, 1 way. C(4, 2) = 6 pairs: 6. Three boxes is impossible.
4. Inclusion–exclusion: 286 − 224 + 6 = 68 (C).

Why this works: Upper limits are handled by counting the violations (pre-placing balls) and correcting overlaps with inclusion–exclusion.

Where it leads: This is the coefficient of x¹⁰ in (1 + x + x² + x³ + x⁴)⁴: generating functions and inclusion–exclusion are two views of one calculation.

Answer: 384

1. Glue each couple into a block: 4 blocks in a row, 4! = 24 orders.
2. Each couple can sit in 2 orders within its block: 2⁴ = 16.
3. Total: 24 × 16 = 384.

Why this works: Blocks handle ‘must sit together’; the internal orders multiply in independently.

Where it leads: The harder question, with no couple together, needs inclusion–exclusion over the couples. Around a circular table with men and women alternating it becomes the ménage problem.

Answer: 35

1. Write the six 0s in a row. They create 7 gaps: before, between and after them.
2. No two 1s adjacent means each gap gets at most one 1. Choose 4 of the 7 gaps.
3. C(7, 4) = 35.

Why this works: Placing the unrestricted symbols first creates slots in which the restricted ones automatically stay apart.

Where it leads: This ‘gaps’ method gives C(n − k + 1, k) for k non-adjacent items among n. Summing over k gives Fibonacci numbers again.

Answer: B, 28

1. A path that avoids the diagonal except at its ends stays strictly below it or strictly above it; by reflection these are equally many.
2. Strictly below: the first step is right to (1, 0) and the last step is up from (5, 4). In between it goes from (1, 0) to (5, 4) without crossing y = x − 1: shifting left by 1, that is a path from (0, 0) to (4, 4) never above y = x, counted by the Catalan number C₄ = 14.
3. Total: 2 × 14 = 28 (B).

Why this works: Symmetry halves the work, and stripping off the forced first and last steps reveals a Catalan count.

Where it leads: By the same argument the probability that a random 2n-step path to (n, n) avoids the diagonal is 2C_n−1/C(2n, n) = 1/(2n − 1).

Answer: 155

1. Remainders 0, 1, 2 each occur 5 times in 1 to 15.
2. Sum ≡ 0 (mod 3) when the remainders are all equal (0 + 0 + 0, 1 + 1 + 1, 2 + 2 + 2) or all different (0 + 1 + 2).
3. All equal: 3 × C(5, 3) = 30. All different: 5 × 5 × 5 = 125.
4. Total: 155.

Why this works: Only remainders matter for divisibility, so classify the numbers into three equal classes and count combinations of classes.

Where it leads: 155 is very close to C(15, 3)/3 = 151.67: sums are spread almost evenly among the remainders. Roots of unity make this exact in generating-function proofs.