Junior combinatorics problems (ages 11 to 13)

Answer: 20

1. A climbing number uses three different digits, written in increasing order.
2. Conversely, any choice of three different digits from {1, …, 6} can be written in increasing order in exactly one way.
3. So climbing numbers correspond one-to-one with 3-element subsets of {1, 2, 3, 4, 5, 6}.
4. Ordered choices: 6 × 5 × 4 = 120; each subset is counted 3 × 2 × 1 = 6 times.
5. Number of subsets: 120 ÷ 6 = 20.

Why this works: When the order is forced, counting arrangements becomes counting choices. That is the idea behind ‘n choose r’.

Where it leads: ‘n choose r’ counts increasing sequences, subsets and committees alike, which is why it appears everywhere.

Answer: 13

1. Use one coin of each kind first: 1p + 2p + 5p = 8p. We still need 12p, now with any number (including zero) of each coin.
2. Organise by the number of extra 5p coins, which can be 0, 1 or 2 (three would be 15p, too much).
3. 0 extra 5p: make 12p from 2p and 1p. The number of 2p coins can be 0, 1, …, 6 and the rest is 1p: 7 ways.
4. 1 extra 5p: 7p left. 2p coins: 0, 1, 2 or 3: 4 ways.
5. 2 extra 5p: 2p left. 2p coins: 0 or 1: 2 ways.
6. Total: 7 + 4 + 2 = 13.

Why this works: ‘At least one of each’ is easiest handled by paying one of each up front. Then organise by the largest coin, where there are fewest cases.

Where it leads: Counting coin combinations is the start of generating functions: the answer is a coefficient of (1 + x + x² + …)(1 + x² + …)(1 + x⁵ + …).

Answer: B, 6

1. Every route has 4 moves right (R) and 2 up (U): 6 moves in total.
2. All routes: choose which 2 of the 6 moves are U: 6 × 5 ÷ 2 = 15.
3. Routes through (2, 1): reach it with 2 R and 1 U in any order: 3 ways.
4. From (2, 1) to (4, 2): 2 R and 1 U again: 3 ways. Through-routes: 3 × 3 = 9.
5. Allowed routes: 15 − 9 = 6 (B).

Why this works: Counting the complement (the routes you do not want) is often easier, and routes through a point multiply: ways in × ways out.

Where it leads: Counting lattice paths with obstacles by subtracting is inclusion–exclusion; with many obstacles it becomes a dynamic-programming table.

Answer: 26

1. Count squares by size. A k by k square needs k consecutive rows and k consecutive columns of the 3 by 5 grid.
2. 1 by 1: 3 rows × 5 columns = 15 positions.
3. 2 by 2: (3 − 1) × (5 − 1) = 2 × 4 = 8 positions.
4. 3 by 3: (3 − 2) × (5 − 2) = 1 × 3 = 3 positions.
5. 4 by 4 or bigger cannot fit in 3 rows.
6. Total: 15 + 8 + 3 = 26.

Why this works: A k by k square fits in (rows − k + 1) × (columns − k + 1) positions. Organising by size makes sure nothing is missed or double counted.

Where it leads: Tilted squares with corners on grid points are not counted here; including them changes the count completely.

Answer: 24

1. Glue Bea and Cai into one block. The block covers two neighbouring chairs: 1–2, 2–3, 3–4 or 4–5, and inside it the order is BC or CB (2 ways).
2. Block at 1–2: free chairs 3, 4, 5. Ali may not take chair 5 (an end): 2 choices.
3. Block at 2–3: free chairs 1, 4, 5. Ali must take chair 4: 1 choice.
4. Block at 3–4: free chairs 1, 2, 5. Ali must take chair 2: 1 choice.
5. Block at 4–5: free chairs 1, 2, 3. Ali takes 2 or 3: 2 choices.
6. So 2 + 1 + 1 + 2 = 6 ways to place the block and Ali. Dan and Eve fill the last two chairs in 2 ways.
7. Total: 6 × 2 (block order) × 2 (Dan, Eve) = 24.

Why this works: ‘Must be next to’ is handled by gluing into a block; a ‘not at the ends’ rule is best handled case by case once the block is placed.

Where it leads: Combining ‘glue together’ with ‘not at the ends’ is typical of seating problems; doing the most restricted person first keeps the count simple.

Answer: 36

1. The odd digits are 1, 3, 5, 7, 9.
2. Hundreds digit: odd and the number below 600, so 1, 3 or 5: 3 choices.
3. Tens digit: any odd digit not already used: 4 choices.
4. Units digit: any odd digit not yet used: 3 choices.
5. Total: 3 × 4 × 3 = 36.

Why this works: Always fill the most restricted position first; after that, the other positions have a fixed number of choices and you can multiply.

Where it leads: ‘Deal with the most restricted position first’ is the golden rule of counting with conditions.

Answer: 21

1. Let a(n) be the number of good colourings of n squares in a row.
2. If the last square is blue, the first n − 1 squares can be any good colouring: a(n − 1) ways.
3. If the last square is red, the square before must be blue, and the first n − 2 are any good colouring: a(n − 2) ways.
4. So a(n) = a(n − 1) + a(n − 2).
5. Start: a(1) = 2 (R or B), a(2) = 3 (BB, BR, RB).
6. Then a(3) = 5, a(4) = 8, a(5) = 13, a(6) = 8 + 13 = 21.

Why this works: Splitting on the last position gives a recurrence. This one produces the Fibonacci numbers, which turn up whenever ‘no two in a row’ is the rule.

Where it leads: The answers are Fibonacci numbers. Avoiding two adjacent reds on a circle instead gives the Lucas numbers.

Answer: 60

1. Six different letters could be arranged in 6! = 720 ways.
2. TATTOO has three Ts and two Os. Each real arrangement is counted 3! = 6 times (the orders of the Ts) × 2! = 2 times (the orders of the Os).
3. So the number is 720 ÷ (6 × 2) = 60.

Why this works: Counting as if the letters were all different and then dividing by the overcount is often easier than counting directly.

Where it leads: The answer 6!/(3! 2! 1!) is a multinomial coefficient; it is the coefficient of t³a o² in (t + a + o)⁶.

Answer: B, 10

1. The odd digits are 1, 3, 5, 7, 9.
2. Any choice of three different odd digits can be written in decreasing order in exactly one way.
3. The number of ways to choose 3 of the 5 digits is (5 × 4 × 3) ÷ (3 × 2 × 1) = 10.
4. So there are 10 such numbers (B).

Why this works: When the order is forced (decreasing), counting numbers is the same as counting sets of digits.

Where it leads: This is why ‘n choose r’ counts so many things: increasing sequences, subsets, paths and committees are all the same count in disguise.

Answer: 10

1. With n members, each shakes hands with n − 1 others.
2. n(n − 1) counts each handshake twice (once for each person), so the number of handshakes is n(n − 1)/2.
3. n(n − 1)/2 = 45 gives n(n − 1) = 90 = 10 × 9.
4. So there were 10 members.

Why this works: Counting from each person’s point of view and then correcting for double counting is a reliable way to count pairs.

Where it leads: n(n − 1)/2 is the triangle number T_n−1 and also ‘n choose 2’. In graph theory it is the number of edges of the complete graph K_n.

Answer: 89

1. Let w(n) be the number of ways to climb n steps. w(1) = 1 and w(2) = 2 (1 + 1 or 2).
2. The last stride onto step n is a 1-step from n − 1 or a 2-step from n − 2, so w(n) = w(n − 1) + w(n − 2).
3. w(3) = 3, w(4) = 5, w(5) = 8, w(6) = 13, w(7) = 21, w(8) = 34, w(9) = 55, w(10) = 89.
4. There are 89 ways.

Why this works: Splitting by the last move turns a big count into two smaller counts of the same kind: a recurrence.

Where it leads: These are the Fibonacci numbers. The same recurrence counts domino tilings of a 2 × n strip and appears in nature in the spirals of sunflowers.

Answer: C, 30

1. Every rectangle is fixed by its top and bottom edges (two of the 3 horizontal lines) and its left and right edges (two of the 5 vertical lines).
2. Pairs of horizontal lines: 3. Pairs of vertical lines: 5 × 4 ÷ 2 = 10.
3. Each combination gives a different rectangle: 3 × 10 = 30 (C).

Why this works: Describing each rectangle by the lines that bound it turns a fiddly picture count into a simple product of choices.

Where it leads: An m by n grid holds (m + 1 choose 2)(n + 1 choose 2) rectangles. Counting squares only is harder: try it for an 8 × 8 chessboard.

Answer: 15

1. Take any one person, say the tallest. Their partner can be any of the other 5.
2. Of the 4 people left, take one; their partner can be any of the other 3.
3. The last 2 people form the last pair.
4. Total: 5 × 3 × 1 = 15.

Why this works: Always pairing up a chosen person first avoids counting the same set of pairs in different orders.

Where it leads: 2n people can be split into pairs in 1 × 3 × 5 × … × (2n − 1) ways (the double factorial). Pairings like this count Feynman diagrams in physics.

Answer: 20

1. A sum is even when both numbers are even or both are odd.
2. Two of the five even numbers: 5 × 4 ÷ 2 = 10 ways.
3. Two of the five odd numbers: also 10 ways.
4. Total: 20.

Why this works: Parity (odd or even) splits the choices into two simple cases.

Where it leads: Out of the 45 pairs, 20 have an even sum and 25 an odd sum. With a different set of numbers the balance changes: when is it exactly even?

Answer: C, 36

1. First letter: 4 choices.
2. Second letter: anything except the first: 3 choices.
3. Third letter: anything except the second: 3 choices (it may equal the first).
4. Total: 4 × 3 × 3 = 36 (C).

Why this works: Building the code one letter at a time and counting the choices at each stage (the multiplication principle) works because the number of choices never depends on which earlier letters were picked.

Where it leads: This counts walks on a graph: 4 letters joined to each other. Colouring a path with k colours so neighbours differ gives k(k − 1)ⁿ⁻¹; cycles are harder.

Answer: 30

1. A triangle cannot have all three corners on one line, so it has two corners on one line and one on the other.
2. Two of the 4 points (6 ways) and one of the 3 points (3 ways): 18 triangles.
3. Two of the 3 points (3 ways) and one of the 4 points (4 ways): 12 triangles.
4. Total: 18 + 12 = 30.

Why this works: Splitting by where the corners lie gives cases that do not overlap and cover every triangle.

Where it leads: You can also count all choices of three points, C(7, 3) = 35, and subtract the collinear ones: C(4, 3) + C(3, 3) = 5. Both methods agree, a good check.

Answer: 19

1. Write 0 to 99 as two-digit strings 00 to 99: 100 strings. Those with no 7: 9 × 9 = 81.
2. So 100 − 81 = 19 strings contain a 7. None of these is 00, and 100 has no 7.
3. So 19 numbers from 1 to 100 contain a 7 (7, 17, 27, …, 97 and 70 to 79, with 77 counted once).

Why this works: ‘At least one’ is often messy to count directly; ‘none’ is a single product. Count the opposite and subtract.

Where it leads: From 1 to 10ⁿ the proportion of numbers with no 7 is about 0.9ⁿ, which tends to 0: almost all very large numbers contain a 7.

Answer: C, 48

1. Treat Priya and Sam as one block. Then there are 4 objects to arrange: 4! = 24 ways.
2. Inside the block they can sit Priya–Sam or Sam–Priya: 2 ways.
3. Total: 24 × 2 = 48 (C).

Why this works: Gluing objects that must stay together reduces the problem to an ordinary arrangement, then you correct for the order inside the glue.

Where it leads: To count arrangements where they are not together, subtract: 120 − 48 = 72. Gluing plus complements handles most seating problems.

Answer: 35

1. From any corner you can draw a diagonal to every other corner except itself and its two neighbours: 10 − 3 = 7 diagonals.
2. 10 corners × 7 = 70 counts every diagonal twice (once from each end).
3. So there are 70 ÷ 2 = 35 diagonals.

Why this works: Counting from each corner then halving is the same double-counting trick as in handshake problems.

Where it leads: An n-gon has n(n − 3)/2 diagonals. A harder question: at most how many points where two diagonals cross? (C(n, 4): each crossing comes from four corners.)

Answer: 45

1. Let the number be abc with a ≥ 1 and a + b = c, where c is at most 9.
2. For a units digit c, a can be 1, 2, …, c (then b = c − a is fixed): c numbers.
3. Adding over c = 1 to 9: 1 + 2 + … + 9 = 45.

Why this works: Fixing the digit that is most constrained (the units digit) leaves a simple count for each case.

Where it leads: Each such number is 100a + 10b + (a + b) = 101a + 11b. Since 101 leaves remainder 2 on division by 11, none of them is a multiple of 11. Algebra on digits explains patterns like this at once.

Answer: D, 35

1. Three different flavours: choose 3 of 5: 10 tubs.
2. Exactly two flavours (one doubled): 5 choices for the doubled flavour and 4 for the single one: 20 tubs.
3. One flavour (all three scoops the same): 5 tubs.
4. Total: 10 + 20 + 5 = 35 (D).

Why this works: Organising by ‘how many different flavours’ gives three cases that are easy to count and cannot overlap.

Where it leads: Choosing r items from n kinds with repetition allowed gives C(n + r − 1, r): here C(7, 3) = 35. This is the ‘stars and bars’ formula.

Answer: 27

1. Every even amount from 2p up is made with 2p stamps alone: 15 amounts (2p to 30p).
2. An odd total needs an odd number of 7p stamps, so at least one: the amount is at least 7p.
3. Every odd amount from 7p up works: 7p, then add 2p stamps for 9p, 11p, …, 29p: 12 amounts.
4. Only 1p, 3p and 5p are impossible, so 27 amounts can be made.

Why this works: A parity argument splits the amounts into even (always possible) and odd (needs a 7p stamp), and each case is then simple.

Where it leads: For two stamp values a and b with no common factor, the largest impossible amount is ab − a − b (here 5). This is the Frobenius coin problem; for three stamp values there is no simple formula.

Answer: 13

1. Pointing up: size 1: 6 (rows of 1, 2, 3). Size 2: 3. Size 3: 1 (the whole triangle). That is 10.
2. Pointing down: size 1: 3 (in the gaps between upward ones). Size 2 does not fit in a side-3 triangle.
3. Total: 10 + 3 = 13.

Why this works: Splitting by orientation and then by size makes sure every triangle is counted exactly once.

Where it leads: For a triangle of side n the total is ⌊n(n + 2)(2n + 1)/8⌋. Try n = 4 by the same method and check the formula.

Answer: C, 12

1. There are 4! = 24 possible finishing orders.
2. Swap Ann and Ben in any order: Ann-ahead orders and Ben-ahead orders pair up exactly.
3. So half the orders have Ann ahead: 24 ÷ 2 = 12 (C).

Why this works: A symmetry (swapping two people) pairs every order with exactly one other, so the two kinds are equally common.

Where it leads: By the same argument, the chance that Ann, Ben and Cal finish in that exact relative order is 1/3! = 1/6. Symmetry arguments like this are central to probability.

Answer: 70

1. Total pairs: 20 × 19 ÷ 2 = 190.
2. The product is not a multiple of 5 exactly when neither number is. There are 16 such numbers, giving 16 × 15 ÷ 2 = 120 pairs.
3. So 190 − 120 = 70 pairs have a product divisible by 5.

Why this works: ‘At least one is a multiple of 5’ has overlapping cases; ‘neither is’ is a single clean count.

Where it leads: Because 5 is prime, 5 divides ab only if 5 divides a or b (Euclid’s lemma). For 4 that fails: 2 × 6 = 12 is a multiple of 4.

Answer: 72

1. The first rook can go on any of 16 squares.
2. It attacks the other 3 squares of its row and 3 of its column, so the second rook has 16 − 1 − 6 = 9 safe squares.
3. 16 × 9 = 144 counts each placement twice (the rooks are identical).
4. Answer: 144 ÷ 2 = 72.

Why this works: Placing objects one at a time, then dividing by the number of orders when they are identical, avoids double counting.

Where it leads: Placing n non-attacking rooks on an n × n board is choosing a permutation: n! ways. Rook placements are a tool for counting permutations with forbidden positions.

Answer: 5

1. One number: impossible (the largest is 6).
2. Two numbers: 4 + 6 only (5 + 5 repeats). 1 set.
3. Three numbers: 1 + 3 + 6, 1 + 4 + 5, 2 + 3 + 5. 3 sets.
4. Four numbers: the smallest possible sum is 1 + 2 + 3 + 4 = 10, so only {1, 2, 3, 4}. 1 set. Five or more numbers sum to at least 15.
5. Total: 1 + 3 + 1 = 5.

Why this works: Sorting by the size of the set and using the smallest possible sum for each size makes sure nothing is missed or counted twice.

Where it leads: Counting subsets with a given sum is the ‘subset sum’ problem: easy for small sets, but believed to be very hard for computers when the sets are huge.

Answer: C, 9

1. Worst case: Tom takes 2 red, 2 green, 2 blue and 2 yellow: 8 sweets and still no three the same.
2. So 8 is not enough.
3. With 9 sweets in 4 colours, if every colour had at most 2 there would be at most 8 sweets. So some colour has at least 3.
4. The answer is 9 (C).

Why this works: To be certain, imagine the worst case. The pigeonhole principle then guarantees the result one step later.

Where it leads: In general, to be sure of k of one colour with c colours you need c(k − 1) + 1 items. The same principle proves that two Londoners have exactly the same number of hairs.