Intermediate combinatorics problems (ages 13 to 16)

Answer: C, 120

1. LEVELS has six letters: L twice, E twice, V once, S once.
2. All arrangements: 6! ÷ (2! × 2!) = 720 ÷ 4 = 180 (divide out swaps of identical letters).
3. Arrangements with the two Es together: glue them into one block EE, leaving five items L, L, V, S, EE.
4. Those arrange in 5! ÷ 2! = 60 ways.
5. Not together: 180 − 60 = 120 (C).

Why this works: ‘Not together’ = all − together, and ‘together’ is counted by gluing. Dividing by factorials of repeated letters removes arrangements that look identical.

Where it leads: ‘Not together’ is easiest by complement; the ‘gaps method’ (place the other letters, then drop the Es into gaps) is an alternative.

Answer: 40

1. 5 is in the subset, so 4 and 6 cannot be (no two consecutive numbers).
2. The rest splits into two separate pieces, {1, 2, 3} and {7, 8, 9, 10}, which cannot interact because 4 and 6 are out.
3. From {1, 2, 3} with no two consecutive: ∅, {1}, {2}, {3}, {1, 3}: 5 choices.
4. From {7, 8, 9, 10}: ∅, four single numbers, {7, 9}, {7, 10}, {8, 10}: 8 choices.
5. The choices are independent, so multiply: 5 × 8 = 40.

Why this works: Fixing one element splits the problem into independent pieces, and the counts multiply. The counts 5 and 8 are Fibonacci numbers again.

Where it leads: Subsets of {1, …, n} with no two consecutive numbers are counted by Fibonacci numbers, so this answer is a product of two of them.

Answer: 18

1. A path to (4, 4) has 4 R steps and 4 U steps. Changing direction 3 times means it is made of 4 straight runs.
2. Runs alternate, so the pattern is R, U, R, U or U, R, U, R.
3. For R U R U: the 4 R steps split into 2 non-empty runs: 1 + 3, 2 + 2 or 3 + 1 (3 ways). The 4 U steps likewise: 3 ways.
4. So 3 × 3 = 9 paths start with R.
5. By symmetry 9 paths start with U.
6. Total: 18.

Why this works: Describing a path by its runs rather than its steps turns ‘count turns’ into ‘split a number into positive parts’, which is a stars-and-bars count.

Where it leads: Counting paths by the number of turns leads to Narayana numbers when the path must also stay below the diagonal.

Answer: D, 495

1. The first digit is at least 1 and digits never decrease, so every digit is at least 1: 0 never appears.
2. The number is determined by how many 1s, 2s, …, 9s it uses (4 digits in total), because the order is forced.
3. So count the ways to choose 4 digits from 1–9 with repetition allowed: x₁ + x₂ + … + x₉ = 4 with each x ≥ 0.
4. Stars and bars: 4 stars and 8 bars, C(12, 4) = 12 × 11 × 10 × 9 ÷ 24 = 495.
5. Answer: 495 (D).

Why this works: When order is forced, you only choose a multiset. Choosing k items from n types with repetition gives C(n + k − 1, k).

Where it leads: Multisets of size k from n kinds are counted by C(n + k − 1, k): stars and bars.

Answer: 44

1. Give each child 1 sweet first. Now share the other 6 so that each child gets at most 3 more.
2. Without the upper limit: 6 identical sweets to 4 children is stars and bars, C(6 + 3, 3) = C(9, 3) = 84.
3. Remove the shares where some child gets 4 or more extra. Pick that child (4 ways), give them 4, and share the remaining 2 freely: C(2 + 3, 3) = C(5, 3) = 10. That is 4 × 10 = 40.
4. Two children cannot both get 4 extra (that needs 8 > 6), so nothing was removed twice.
5. Answer: 84 − 40 = 44.

Why this works: Lower limits are handled by handing them out first; upper limits by inclusion–exclusion on the cases that break them.

Where it leads: Upper limits are handled by inclusion–exclusion over the children who exceed the limit.

Answer: 200

1. Any three dots make a triangle unless they lie on one straight line.
2. Choices of three dots from 12: C(12, 3) = 220.
3. Collinear triples in rows: 3 rows of 4 dots, C(4, 3) = 4 each: 12.
4. In columns: 4 columns of 3 dots, 1 each: 4.
5. On diagonals of slope 1 or −1: lines with 3 dots start in the first or second column of the bottom (or top) row: 2 each way, 4 in total. No other slope passes through 3 dots in a 3 by 4 array.
6. Collinear triples: 12 + 4 + 4 = 20, so triangles: 220 − 20 = 200.

Why this works: Triangles = triples − collinear triples. The work is in finding every line with three or more dots, including the slanted ones.

Where it leads: Counting collinear triples on a grid is the tricky part; slanted lines through three grid points are easy to miss.

Answer: 102

1. Committees of 4 from 9 people: C(9, 4) = 126.
2. Remove the all-boy ones, C(5, 4) = 5, and the all-girl one, C(4, 4) = 1: 120 mixed committees.
3. Now remove mixed committees containing both Asa and Bo. With both in, choose 2 more from the other 7: C(7, 2) = 21.
4. Of those 21, the ones with no girl use 2 of the 3 other boys: C(3, 2) = 3. They are all-boy, already removed. So 21 − 3 = 18 mixed ones remain to remove.
5. Answer: 120 − 18 = 102.

Why this works: Apply one restriction at a time and be careful not to subtract the same committee twice — the all-boy committees with Asa and Bo were already gone.

Where it leads: Layering several conditions is safest by complement, one condition at a time, checking that removed sets do not overlap.

Answer: 120

1. Choose the 3 occupied chairs first. Squeeze out one empty chair after each of the first two chosen chairs: this matches non-adjacent choices from 8 chairs with any choices from 6.
2. So there are C(6, 3) = 20 ways to choose the chairs.
3. The 3 people can then sit in those chairs in 3! = 6 orders.
4. Total: 20 × 6 = 120.

Why this works: Removing the forced gaps turns ‘no two adjacent’ into an unrestricted choice from fewer chairs.

Where it leads: In general, k non-adjacent items from n in a row can be chosen in C(n − k + 1, k) ways. Around a circle the answer changes slightly: try it.

Answer: B, 14

1. Write at each allowed point (y ≤ x) the number of allowed paths reaching it; each number is the sum of the left and lower neighbours.
2. Row y = 0: all 1s. Row y = 1: 1, 2, 3, 4 at x = 1, 2, 3, 4. Row y = 2: 2, 5, 9 at x = 2, 3, 4. Row y = 3: 5, 14 at x = 3, 4.
3. Point (4, 4): 14 (only from below, since (3, 4) is above the line).
4. There are 14 paths (B).

Why this works: Building up counts point by point respects the restriction automatically: forbidden points just get no number.

Where it leads: These are the Catalan numbers 1, 1, 2, 5, 14, 42, …, which also count bracket sequences, triangulations of polygons and binary trees. Formula: C(2n, n)/(n + 1).

Answer: 10

1. 0 red: 1 way. 1 red: 1 way (any face can be turned to the top).
2. 2 red: the two red faces are opposite or adjacent: 2 ways.
3. 3 red: either all three meet at one corner, or two are opposite and the third touches both (a ‘band’): 2 ways.
4. 4, 5, 6 red are the same as 2, 1, 0 blue: 2, 1, 1 ways.
5. Total: 1 + 1 + 2 + 2 + 2 + 1 + 1 = 10.

Why this works: Organising by the number of red faces, then describing the shape they make, counts each pattern once regardless of how the cube is turned.

Where it leads: Burnside’s lemma counts such patterns by averaging over the 24 rotations of the cube. With 3 colours it gives 57.

Answer: 3360

1. With 8 different letters there would be 8! = 40320 arrangements.
2. The three Ls can be swapped among themselves in 3! = 6 ways and the two As in 2! = 2 ways without changing the word.
3. So the number is 40320 ÷ (6 × 2) = 3360.

Why this works: Every distinct word is counted 3! × 2! times among the 8! labelled arrangements, so divide by that.

Where it leads: How many of these have the three Ls together? Glue them into one block: 6!/2! = 360. Gluing and dividing combine to answer most word-arrangement questions.

Answer: C, 7

1. Write the sides a ≤ b ≤ c with a + b + c = 15. The triangle inequality a + b > c means c < 7.5, and c ≥ 5 since it is the largest.
2. c = 7: a + b = 8 with a ≤ b ≤ 7: (1, 7), (2, 6), (3, 5), (4, 4): 4 triangles.
3. c = 6: a + b = 9 with a ≤ b ≤ 6: (3, 6), (4, 5): 2 triangles.
4. c = 5: a + b = 10 with b ≤ 5: (5, 5): 1 triangle.
5. Total: 7 (C).

Why this works: Ordering the sides avoids repeats, and the triangle inequality reduces to one condition on the longest side.

Where it leads: For perimeter n the count is the nearest whole number to n²/48 when n is even and to (n + 3)²/48 when n is odd (Alcuin’s sequence). Here 18²/48 = 6.75, and the nearest whole number is 7.

Answer: 8

1. Going round the hexagon, the three gaps between chosen corners add up to 6. The patterns are {1, 1, 4}, {1, 2, 3} and {2, 2, 2}.
2. Equal gaps mean equal sides. {1, 1, 4}: two equal sides (three neighbouring corners): 6 triangles, one for each middle corner.
3. {2, 2, 2}: equilateral: 2 triangles. {1, 2, 3}: all gaps different, so scalene (these are the 12 right-angled triangles).
4. Isosceles: 6 + 2 = 8. (Check: 6 + 2 + 12 = 20.)

Why this works: In a regular polygon, the length of a chord depends only on how many sides it skips, so gaps describe the triangle’s shape completely.

Where it leads: The same gap method counts isosceles triangles in any regular n-gon. For n = 12 it is a nice challenge.

Answer: 20

1. Put a = 2x + 1, b = 2y + 1, c = 2z + 1, d = 2w + 1 with x, y, z, w ≥ 0.
2. Then 2(x + y + z + w) + 4 = 10, so x + y + z + w = 3.
3. The number of ways to split 3 into 4 ordered parts (zeros allowed) is C(3 + 3, 3) = 20 (stars and bars).
4. So there are 20 lists.

Why this works: Substituting to remove the restriction (oddness) turns the problem into a standard stars-and-bars count.

Where it leads: This is the coefficient of t¹⁰ in (t + t³ + t⁵ + …)⁴ = t⁴/(1 − t²)⁴: generating functions do these counts automatically.

Answer: D, 70

1. Two diagonals that cross inside use four different corners of the octagon.
2. Conversely, any four corners form a convex quadrilateral whose two diagonals cross exactly once.
3. So crossings match choices of 4 corners: C(8, 4) = 70 (D).

Why this works: Matching each crossing to a set of four corners (a one-to-one correspondence) replaces a hard picture count by a simple choice.

Where it leads: Counting the regions the diagonals cut the polygon into uses the same idea plus Euler’s formula: for n points on a circle the regions are C(n, 4) + C(n, 2) + 1.

Answer: 6

1. Let f(n) be the number of tilings of a 3 by n rectangle. The left column (3 squares) is covered either by one upright tile, leaving 3 by (n − 1), or by three flat tiles stacked, leaving 3 by (n − 3).
2. So f(n) = f(n − 1) + f(n − 3), with f(0) = f(1) = f(2) = 1.
3. f(3) = 2, f(4) = 3, f(5) = 4, f(6) = 6.
4. There are 6 tilings.

Why this works: Deciding how the first column is covered splits the tilings into cases that are smaller versions of the same problem.

Where it leads: Recurrences like this count tilings of all kinds of strips. For 2 by n with dominoes you get Fibonacci; for 3 by n with dominoes the answer only exists for even n and grows like (2 + √3)^n/2.

Answer: 4

1. All three reds together: RRRBBB. 1 pattern.
2. None together: RBRBRB. 1 pattern.
3. Exactly two together: the pair and the single red are separated by gaps of blue beads that are 1 and 2 long; going clockwise from the pair, the gap after it can be 1 or 2, giving RRBRBB and RRBBRB. These are different under rotation (they are mirror images). 2 patterns.
4. Total: 4.

Why this works: Grouping by the ‘runs’ of red beads gives cases that rotation cannot mix up.

Where it leads: If flipping is allowed too, RRBRBB and RRBBRB become the same and the answer is 3. Burnside’s lemma handles these counts in general.

Answer: B, 225

1. 7 in the hundreds place: the other two digits are anything but 7: 9 × 9 = 81.
2. 7 in the tens place: the first digit is 1–9 except 7 (8 choices), the units anything but 7 (9): 72.
3. 7 in the units place: likewise 8 × 9 = 72.
4. Total: 81 + 72 + 72 = 225 (B).

Why this works: Splitting by the position of the 7 gives cases that cannot overlap (exactly one 7), each a simple product.

Where it leads: ‘At least one 7’ is easier by complement: 900 − 8 × 9 × 9 = 252. Exactly two 7s and three 7s make up the difference: 252 − 225 = 27.

Answer: 20

1. Each square sits inside a smallest upright bounding box, a k by k square on the grid with k = 1, 2 or 3.
2. Inside a k by k box, a square touching all four sides has one corner on each side, k units around: there are exactly k of them.
3. Number of k by k boxes: (4 − k)²: 9, 4, 1 for k = 1, 2, 3.
4. Total: 9 × 1 + 4 × 2 + 1 × 3 = 20.

Why this works: Matching each tilted square to its bounding box organises the count and makes sure tilted squares are not missed.

Where it leads: For an n by n array of dots the total is n²(n² − 1)/12. That formula hides a sum of k(n − k)².

Answer: 90

1. Any route consists of 6 unit steps: 2 in x, 2 in y and 2 in z, in some order.
2. Different orders give different routes, so count arrangements of xxyyzz.
3. 6!/(2! 2! 2!) = 720/8 = 90.

Why this works: Recording a route as a string of directions turns a 3D path count into counting arrangements of letters.

Where it leads: The same count, (a + b + c)!/(a! b! c!), is a multinomial coefficient: the coefficient of x^ay^bz^c in (x + y + z)^a+b+c.

Answer: C, 180

1. There are 6! = 720 arrangements.
2. Swapping the positions of 1 and 2 pairs arrangements up, so exactly half have 1 before 2: 360.
3. Swapping 3 and 4 independently halves again: 180.
4. Answer: 180 (C).

Why this works: Swapping two labels is a symmetry that splits the arrangements into two equal halves; independent swaps halve independently.

Where it leads: The probability that k given items appear in a given order is 1/k!. This is used to show quicksort is fast on average.

Answer: 512

1. There are 2¹⁰ = 1024 subsets.
2. Toggle the number 1 (add it if missing, remove it if present). This pairs the subsets up, and the two in each pair have sums differing by 1.
3. So exactly one in each pair has an odd sum: half the subsets, 512.

Why this works: A pairing that always changes parity proves the two kinds are equally numerous without counting either.

Where it leads: Toggling an element is a bijection. Bijections prove equal counts in many places, e.g. that a set has as many even-sized subsets as odd-sized ones.

Answer: 112

1. Horizontal pairs: each of the 8 rows has 7 neighbouring pairs: 56.
2. Vertical pairs: likewise 56.
3. Total: 112 pairs (these are the 112 positions of a domino on the board).

Why this works: Counting the shared edges instead of the squares makes the count immediate.

Where it leads: A domino tiling of the chessboard uses 32 of these 112 positions. The number of tilings is 12,988,816, found by a formula involving cosines (Kasteleyn, Temperley and Fisher).

Answer: 19

1. Count the opposite: strings with no two adjacent As. Let g(n) count those of length n.
2. A string ends in B (any good string of length n − 1 before it) or in BA (any good string of length n − 2 before it). So g(n) = g(n − 1) + g(n − 2), with g(1) = 2, g(2) = 3.
3. g(3) = 5, g(4) = 8, g(5) = 13.
4. So 2⁵ − 13 = 19 strings contain AA.

Why this works: Avoiding a pattern gives a recurrence (by looking at how a string ends); the complement then answers the question asked.

Where it leads: Strings avoiding AA are counted by Fibonacci numbers. Avoiding longer patterns like ABA leads to the Goulden–Jackson cluster method.

Answer: C, 96

1. The rooks use 3 different rows: C(4, 3) = 4 choices. And 3 different columns: 4 choices.
2. Match the 3 chosen rows with the 3 chosen columns: 3! = 6 ways.
3. Total: 4 × 4 × 6 = 96 (C).

Why this works: Separating ‘which rows and columns’ from ‘how they are matched’ gives three independent choices.

Where it leads: The number of ways to put k non-attacking rooks on an n × n board is C(n, k)² k!. Rook numbers like these count permutations with restrictions.

Answer: 3

1. If k teams each win 5, their wins total 5k. But they can only win the C(k, 2) games among themselves plus their k(7 − k) games against the other teams.
2. So 5k ≤ k(k − 1)/2 + k(7 − k), which simplifies to 5 ≤ 7 − (k + 1)/2, i.e. k ≤ 3.
3. k = 3 is possible: the three teams beat each other in a cycle (A beats B, B beats C, C beats A) and each beats all four others: 1 + 4 = 5 wins each.
4. The largest number is 3.

Why this works: Counting the wins available to a group of teams gives an upper bound; an explicit construction shows the bound is reached.

Where it leads: Counting arguments in tournaments lead to Landau’s theorem, which says exactly which lists of win totals are possible.

Answer: 60

1. 72 = 2³ × 3². Choosing (a, b, c) is the same as sharing out the exponents of each prime.
2. The three factors of 2 go into a, b, c in C(3 + 2, 2) = 10 ways (stars and bars).
3. The two factors of 3 go in C(2 + 2, 2) = 6 ways.
4. Total: 10 × 6 = 60.

Why this works: Each prime is shared out independently, so the counts multiply.

Where it leads: The number of ordered ways to write n as a product of k factors is a multiplicative function; for k = 2 it is just the number of divisors.

Answer: B, 18

1. Top and bottom never meet, so they may match. Left and right must each differ from both top and bottom.
2. Top = bottom: 3 choices; left and right each avoid one colour: 2 × 2. Total 12.
3. Top ≠ bottom: 3 × 2 = 6 choices; left and right must use the third colour: 1 × 1. Total 6.
4. Altogether: 12 + 6 = 18 (B).

Why this works: Splitting on whether two non-touching sides match makes the remaining choices independent.

Where it leads: This is colouring a 4-cycle: with k colours the answer is (k − 1)⁴ + (k − 1). Graph colouring formulas like this are chromatic polynomials.