Counting & Combinatorics
Module 05 of 06 · Full Solution Edition
Forming Numbers
Core Concept: The two pillars of counting
-
Multiplication Principle (slot-by-slot): if you fill slot 1 in
aways, slot 2 inbways, … then total =a × b × …Useful when each digit/position is chosen independently. - Complement Rule: count(bad) = total − count(good). When “at least one” appears, flip to “none” — it’s usually easier.
- Inclusion–Exclusion: |A ∪ B| = |A| + |B| − |A ∩ B|. Stops you from double-counting overlaps.
- Permutations arrange (order matters): n items in n! ways. Combinations select (order doesn’t): n items in groups.
How many two-digit numbers have at least one digit that is a 4?
Concept
“At least one 4” can mean the tens digit is 4, the units digit is 4, or both. Use inclusion–exclusion to avoid double-counting “44”.
Steps
- Tens digit is 4:
40, 41, …, 49→ 10 numbers. - Units digit is 4:
14, 24, 34, 44, 54, 64, 74, 84, 94→ 9 numbers (10–99 only, so 04 is out). - Both (overlap):
44→ 1 number. - Total =
10 + 9 − 1 = 18.
Pitfall
Forgetting to subtract 44 gives 19 (option E). Always remove the double-counted overlap.
Answer
C — 18
A four-digit number can be made by repeating a two-digit number. For example, 1111 is made by repeating 11, and 1919 is made by repeating 19. How many such numbers are there between 2000 and 10000?
Strategy
Each “repeated” 4-digit number abab is determined entirely by the 2-digit number ab. Just count how many 2-digit values ab produce a 4-digit number between 2000 and 10000.
Steps
- If
ab = 11, repeated gives1111— too small. - If
ab = 20, repeated gives2020— in range. - If
ab = 99, repeated gives9999— in range (under 10000). - Valid
abvalues: 20 through 99 =99 − 20 + 1 = 80numbers.
Answer
A — 80
A three-digit integer is from 100 to 999. It is called Tiny if no rearrangement of its digits gives a smaller three-digit integer. For example, 138, 207, and 566 are Tiny, but 452, 360, and 727 are not. How many three-digit integers are Tiny?
Concept
A Tiny number is uniquely determined by its multiset of digits — because given any 3 digits, there is exactly one smallest 3-digit number you can form. So counting Tiny numbers = counting digit multisets that produce a valid 3-digit number.
Strategy
Count all multisets of size 3 from {0, 1, …, 9}, then subtract the one impossible multiset (all zeros, which can’t form a 3-digit number).
Steps
- Multisets of 3 digits from 10 choices =
C(10+3−1, 3) = C(12, 3) = 220. - Subtract the impossible one:
{0,0,0}→ no valid 3-digit number. - Tiny count =
220 − 1 = 219.
Why this works
For digits like {2, 0, 7}, the smallest 3-digit arrangement is 207 (the only one that doesn’t start with 0). For {1, 3, 8}, sort ascending: 138. Every non-zero multiset yields exactly one Tiny number.
Answer
E — 219
An ant begins its path at A, travels only right or down, and remains on the line segments shown. The number of different paths from A to C that pass through B is
Concept
For lattice paths “right or down only”, paths from one corner to another in an m × n grid number C(m+n, m). For a path forced through an intermediate point B, multiply: (paths A→B) × (paths B→C).
Steps
- A → B is a
1 × 1sub-grid:C(2,1) = 2paths. - B → C is also a
1 × 1sub-grid:2paths. - Total =
2 × 2 = 4.
Answer
C — 4
The Gaussbot factory assembles robots. Each robot comes in one of three colours: red, blue, or green. Each robot also has a number stamped on its head: 1, 2, 3, or 4. The nth robot assembled is the first robot to have the same colour and the same number as a previously assembled robot. What is the greatest possible value of n?
Concept
Pigeonhole Principle. If there are k possible (colour, number) combinations and we assemble more than k robots, two must share. Here k = 3 × 4 = 12.
Steps
- Total distinct (colour, number) pairs:
3 × 4 = 12. - The first 12 robots can all be different — so the duplicate cannot occur before robot #13.
- The 13th robot must repeat one of the previous 12 pairs.
- So the greatest possible
nis13.
Answer
C — 13
Each of three doors is painted one colour: either black, white, or gold. Each colour is equally likely to be chosen for each door. What is the probability that at least one colour is not used?
Strategy
Complement. P(at least one missing) = 1 − P(all three used).
Steps
- Total paintings:
3 × 3 × 3 = 27. - “All three colours used” means the 3 doors get a bijection of 3 colours:
3! = 6ways. - P(all used) =
6/27. - P(at least one missing) =
1 − 6/27 = 21/27 = 7/9.
Pitfall
Trying to count “at least one missing” directly forces an inclusion–exclusion mess. The complement is always the move when “at least” appears.
Answer
A — 7/9
Each of four doors is painted one colour: either red, blue, green, or yellow. Each colour is equally likely to be chosen for each door. What is the probability that at least one colour is not used?
Strategy
Same trick as Q6: complement.
Steps
- Total paintings:
4⁴ = 256. - All four colours used: each door takes a different one, so
4! = 24ways. - P(at least one missing) =
1 − 24/256 = 232/256 = 29/32.
Answer
E — 29/32
Counting Figures
Core Concept: Count by size and orientation — systematically
To count squares/rectangles/parallelograms in a grid: pick lines, not shapes. A rectangle is determined by choosing 2 horizontal lines and 2 vertical lines.
-
Squares of size k in an
m × nsquare grid:(m−k+1)(n−k+1). - Always group by size first — list size 1, then size 2, then bigger.
- Tilted squares hide inside diagonal-laced grids. Check both axis-aligned and 45°-rotated squares.
The figure consists of 8 identical small parallelograms (a 2-row × 4-column grid). How many parallelograms appear in this figure?
Strategy
Each parallelogram in this grid is determined by choosing 2 of the 3 horizontal lines and 2 of the 5 slanted lines.
Steps
- The 2 × 4 grid has 3 horizontal lines (top, middle, bottom) and 5 slanted lines (vertical edges).
- Choose 2 of 3 horizontal lines:
C(3, 2) = 3. - Choose 2 of 5 slanted lines:
C(5, 2) = 10. - Total =
3 × 10 = 30.
Method check
By size: size 1 (8) + size 1×2 (6) + size 1×3 (4) + size 1×4 (2) + size 2×1 (4) + size 2×2 (3) + size 2×3 (2) + size 2×4 (1) = 30. ✓
Answer
B — 30
How many squares are there in the diagram (a 3 × 2 grid of unit cells, each cell containing both diagonals drawn — the whole figure is shown rotated 45°)?
Strategy
Catalog squares by orientation and size. There are two families: axis-aligned squares (using grid edges) and tilted (45°) squares (whose sides lie along cell diagonals).
Steps
- Axis-aligned 1×1 squares: the 6 unit cells → 6.
-
Axis-aligned 2×2 squares: position by upper-left corner →
(3−1) × (2−1) = 2. -
Tilted (45°) “small” squares: within each cell, the 4 half-diagonals from the corners to the centre form a small tilted square.
6 cells × 1 = 6. -
Tilted (45°) “medium” squares: centred on internal grid corners (1 row × 2 columns of such corners) →
2. -
Tilted square spanning two cells (vertices at cell corners):
1(the rhombus centred between two adjacent cells). - Total =
6 + 2 + 6 + 2 + 1 = 17.
Pitfall
Easy to miss the tilted squares whose sides are cell diagonals, not grid edges. Always rotate your eye 45° once you’ve counted the axis-aligned ones.
Answer
D — 17
17 toothpicks make a 2 × 3 grid of squares: 10 outer, 7 inner. Suppose a 20 × 24 grid is built. To the nearest percent, what percentage of toothpicks used are inner toothpicks?
Concept
For an m × n grid of unit squares: horizontal toothpicks = (m+1) × n, vertical = m × (n+1), outer (perimeter) = 2(m + n).
Steps
-
Total toothpicks for 20 × 24:
(20+1) × 24 + 20 × (24+1) = 504 + 500 = 1004. -
Outer toothpicks:
2 × (20 + 24) = 88. -
Inner toothpicks:
1004 − 88 = 916. -
Percentage:
916 / 1004 ≈ 0.9124 ≈ 91%.
Sanity check
2 × 3 case: 3×3 + 2×4 = 17 ✓ outer = 2(2+3) = 10 ✓ inner = 7 ✓.
Answer
E — 91%
The total number of triangles, parallelograms, and trapezoids in the figure (a side-3 equilateral triangle subdivided into 9 unit triangles) is ____.
Strategy
Count each shape family separately. In a side-n triangular grid, group by size and orientation (pointing up vs down).
Steps — Triangles
- Upward triangles: size 1 → 6, size 2 → 3, size 3 → 1. Total 10.
- Downward triangles: size 1 → 3, size 2 → 0. Total 3.
- Triangle subtotal =
10 + 3 = 13.
Steps — Parallelograms (rhombi)
- 3 orientations × 5 each (by exhaustive enumeration in the side-3 grid) = 15.
Steps — Trapezoids
- Each trapezoid = one triangle with a smaller similar triangle removed from one corner. Exhaustively: 7.
Final tally
13 + 15 + 7 = 35 shapes in total.
Answer
35
Number Matrix
Core Concept: Use the total sum and the shared cells
In number-matrix problems, three tools do most of the work:
-
Sum constraint: if a row sum equals a column sum equals
S, then2S − (shared cell) = (total of all distinct cells). -
Arithmetic progression: any 3 evenly-spaced terms satisfy
middle = (first + last) / 2. Two known entries pin down the whole row/column. - Latin-square logic: each row/column/region contains each symbol exactly once. Cross out impossible cells.
The squares of a cross-shaped diagram must be filled with the numbers 6 to 10 so that the sum of the row equals the sum of the column. The cross has 5 squares: 3 in the horizontal row, 3 in the vertical column, sharing the centre. The numbers 9 and 6 are already filled in (9 in the row, 6 in the column). What is the sum of the numbers in the row?
Concept
If row sum = column sum = S, and the centre cell c is shared, then (row) + (column) − c = (total of all 5 cells) → 2S − c = 40.
Steps
- Total of
6 + 7 + 8 + 9 + 10 = 40. - So
2S − c = 40, meaningc = 2S − 40. - Row has 9:
9 + c + x = S→x = S − 9 − c = S − 9 − (2S − 40) = 31 − S. - Column has 6:
y + c + 6 = S→y = 34 − S. - The three unknowns
{c, x, y}must equal{7, 8, 10}in some order. - Try
S = 24:c = 8, x = 7, y = 10— perfect ✓. - Row sum =
9 + 8 + 7 = 24.
Answer
B — 24
In the 4 × 4 grid, the numbers in each row form an arithmetic sequence, and the numbers in each column form an arithmetic sequence. Given that column 1 reads (top to bottom) 1, 4, 7, 10 and that two further entries are known (row 2 col 4 = 25, row 4 col 3 = 36), find x, the entry at row 3 col 4.
Strategy
Each row is determined by 2 entries. Each column also. Use known entries to pin down common differences, then propagate.
Steps
-
Row 2: starts at 4 (col 1), ends at 25 (col 4). Three gaps of equal size:
d₂ = (25 − 4)/3 = 7. Row 2 =4, 11, 18, 25. -
Row 4: starts at 10 (col 1), col 3 = 36. Two gaps of size
d₄:10 + 2d₄ = 36→d₄ = 13. Row 4 =10, 23, 36, 49. -
Column 2: row 2 = 11, row 4 = 23, gap of 2 row-steps, so column step =
(23 − 11)/2 = 6. Column 2 =5, 11, 17, 23. -
Row 1: starts at 1, col 2 = 5, so
d₁ = 4. Row 1 =1, 5, 9, 13. -
Column 4: row 1 = 13, row 2 = 25, column step = 12. Column 4 =
13, 25, 37, 49. - x = row 3 col 4 = 37.
Answer
A — 37
In the 5 × 5 diagram, each row, each column, and each thick-bordered region must contain the letters A, B, C, D, E. Given clues (row 1: D at col 4, A at col 5; row 2: C at col 3; row 5: B at col 4, E at col 5), find the letter in the shaded square at row 4, column 1.
Strategy
This is a 5×5 Latin square + region constraint (mini-Sudoku). Eliminate possibilities cell by cell. There are 5 thick regions, each containing exactly 5 cells.
Steps (CEMC official reasoning)
- [2,5] must be C (region 1 already has C in [3,2]; column 2 has C; only [2,5] left in row 2 for C).
- Row 5 already has E, so the E in region 5 goes at [4,2]. Row 2: missing B, E. Column 2 has E, so [2,1] = E, [2,2] = B.
- Row 1 missing A in region 2 → [1,1] = A. Column 4 already has A → A in region 5 must be at [5,2].
- Region 1 needs D in column 1 → [5,1] ≠ D, so region 5’s D goes at [5,4].
- Region 4: missing A, B, D. Column 4 has A, D → [3,4] = B.
- Region 1 missing B and D. Row 3 has B → [3,1] ≠ B, so [4,1] = B.
Answer
B — B
In the 3 × 3 table, the numbers 1, 2, 3 are placed so that each number appears exactly once in each row and once in each column. Given that [1,3] = 1, [2,1] = 3, [2,2] = X, [3,3] = Y, find X + Y.
Strategy
It’s a 3 × 3 Latin square. With [2,1] = 3 in column 1, the other entries in column 1 are 1 and 2. Use row/column constraints to deduce each cell.
Steps
- Row 1 ends with 1, so the other two are 2 and 3. Column 1 already has 3 (at row 2), so [1,1] ≠ 3 → [1,1] = 2, [1,2] = 3.
- Column 1: 2, 3, ? → [3,1] = 1.
-
Column 2: 3, X, ? → must contain {1, 2}. From row 2:
3 + X + ? = {1,2,3}with 3 fixed → {X, [2,3]} = {1, 2}. - Column 3: 1, [2,3], Y → must contain {2, 3}. So {[2,3], Y} = {2, 3}.
- If [2,3] = 2, then row 2 = {3, X, 2}, X must be 1. ✓ And Y = 3 (from col 3). Verify row 3: {1, [3,2], 3}, so [3,2] = 2. Check col 2: {3, 1, 2} ✓.
-
X + Y = 1 + 3 = 4.
Answer
E — 4
Homework
A parallelogram (rhombus) is made of 8 identical equilateral triangles (side-2 rhombus in the triangular grid). How many parallelograms of any size can you see in the diagram?
Strategy
In a side-2 rhombus on the triangular grid, parallelograms come in 3 orientations (each from a different pair of grid directions). Count by size in each orientation.
Steps
- Orientation 1 (the rhombus’s own orientation): 1×1 → 4, 1×2 → 2, 2×1 → 2, 2×2 → 1. Subtotal 9.
- Wait — the 9 includes the trivial 1×1 unit rhombi; we need to also count parallelograms in the other 2 grid orientations (these are “leaning” parallelograms whose sides run along different lattice directions).
- Orientations 2 & 3 together yield 4 more parallelograms (two per orientation: a unit rhombus and a long thin one).
- Total =
9 + 4 = 13.
Pitfall
Easy to miss the leaning parallelograms whose long axis isn’t aligned with the rhombus. Always check all 3 lattice directions.
Answer
B — 13
Study the figures made with matchsticks. Figure 1: one triangle. Figure 2: side-2 triangle subdivided. Figure 3: side-3 triangle subdivided. How many matchsticks are needed to make Figure 5?
Concept
A side-n triangular grid has n + (n−1) + … + 1 = n(n+1)/2 matchsticks in each of the 3 lattice directions.
Steps
- Matchsticks per direction:
T(n) = n(n+1)/2. - Total for Figure
n:3 × n(n+1)/2. - Verify:
n=1 → 3,n=2 → 9,n=3 → 18. ✓ - Figure 5:
3 × 5 × 6 / 2 = 45.
Answer
D — 45
Eddie is ordering lunch at a fast food restaurant that has sandwiches and burgers (food) along with coffee, milk, and tea (drinks). If Eddie chooses one food and one drink, he has ____ different ways to order lunch.
Concept
Multiplication principle: independent choices multiply.
Steps
- 2 food options × 3 drink options =
6orders.
Answer
C — 6
Each of the integers 334 and 419 has digits whose product is 36. How many 3-digit positive integers have digits whose product is 36?
Strategy
List all unordered digit triples {a, b, c} from 1–9 (no zeros — they’d give product 0) with a × b × c = 36. Then count arrangements for each.
Steps
- Factor 36 into three digit-factors (each 1–9):
-
{1, 4, 9}→3! = 6arrangements -
{1, 6, 6}→3!/2! = 3 -
{2, 2, 9}→3 -
{2, 3, 6}→6 -
{3, 3, 4}→3
-
- Total =
6 + 3 + 3 + 6 + 3 = 21.
Pitfall
Don’t forget that hundreds, tens, and units digits are positions — each rearrangement of the same digit-set gives a different number (e.g., 149, 194, 419, 491, 914, 941).
Answer
A — 21
Eddie, his dad, his mom, his grandpa, and his grandma are lining up for a family photo. Eddie does not want to be in the middle. How many ways can they line up?
Strategy
Use complement: (all arrangements) − (Eddie in the middle).
Steps
- Total arrangements of 5 people:
5! = 120. - Arrangements where Eddie is in position 3 (middle): the other 4 fill 4 spots →
4! = 24. - Answer =
120 − 24 = 96.
Direct count
Place Eddie first (4 valid spots, not middle) then the remaining 4: 4 × 4! = 96. Same answer.
Answer
B — 96
In how many ways can the letters in BEEKEEPER be rearranged so that two or more Es do not appear together?
Concept
BEEKEEPER has 9 letters: 5 Es and 4 distinct non-E letters (B, K, P, R). The “gap method” places non-E letters first, then inserts Es into the gaps.
Steps
- Arrange the 4 non-E letters B, K, P, R:
4! = 24ways. - This creates 5 gaps (before, between, after the 4 letters):
_ B _ K _ P _ R _. - To prevent any two Es from being adjacent, place at most one E in each gap. With 5 Es and 5 gaps, place exactly one E per gap:
C(5, 5) = 1way. - Total =
24 × 1 = 24.
Pitfall
The constraint “5 Es into 5 gaps, one each” is uniquely determined — there’s no extra freedom. So the gap multiplier is 1, not C(5,5)‘s value being any larger.
Answer
D — 24
The numbers 2, 3, 4, and 5 are filled into a cross-shape figure so that each line of the cross adds to the same total. Two numbers, 6 and 1, are already filled in the horizontal row (with 1 at the centre, 6 to its left). What number should be placed at the position of the question mark (right of the centre)?
Strategy
Let ? = x. The other 3 unknowns are the entries of the vertical column above and below the centre. Together with x, they make up the set {2, 3, 4, 5} (sum 14). Set row sum = column sum.
Steps
- Horizontal row sum =
6 + 1 + x = 7 + x. - The vertical column shares the centre (1) with the row. Let the other 3 vertical entries sum to
V. Column sum =V + 1. - The set
{x} ∪ {3 vertical entries} = {2, 3, 4, 5}, sum 14. SoV = 14 − x. - Set row sum = column sum:
7 + x = (14 − x) + 1 = 15 − x→2x = 8→x = 4.
Answer
C — 4
Jane starts at dot A. She tosses a fair coin: heads → move up one dot; tails → move right one dot. After 4 tosses she is at one of P, Q, R, S, or T (with P being all-heads and T being all-tails). What is the probability she is at dot R?
Concept
After 4 coin tosses, the number of heads (and the dot reached) follows a binomial distribution. R is reached by exactly 2 heads + 2 tails.
Steps
- Total outcomes:
2⁴ = 16. - Outcomes with exactly 2 heads (so 2 tails):
C(4, 2) = 6. - P(R) =
6/16 = 3/8.
Pascal's row 4
P, Q, R, S, T probabilities = 1/16, 4/16, 6/16, 4/16, 1/16 — the row 1 4 6 4 1 of Pascal’s triangle, divided by 16.
Answer
B — 3/8
Toothpicks make rectangular grids. A 1 × 10 grid uses 31 toothpicks. How many toothpicks are used in a 43 × 10 grid?
Concept
For an m × n grid of unit squares: horizontal toothpicks = (m+1) × n, vertical toothpicks = m × (n+1).
Steps
- Sanity-check the formula on 1 × 10:
2 × 10 + 1 × 11 = 20 + 11 = 31✓. - For 43 × 10: horizontal =
44 × 10 = 440; vertical =43 × 11 = 473. - Total =
440 + 473 = 913.
Answer
A — 913
In the triangle, each of the numbers 1, 2, 3, 4, 5, 6, 7, 8 is placed into a different circle. The sums of the numbers on each of the three sides of the triangle are equal to the same number, S. The sum of all of the different possible values of S is
Strategy
Let the three corner circles hold values a, b, c. Adding the three side sums counts each corner twice and each non-corner once: 3S = (1+2+…+8) + (a + b + c) = 36 + (a+b+c).
Steps
- Range of
a + b + c: smallest sum1+2+3=6, largest6+7+8=21. - So
3S = 36 + (a+b+c)with(a+b+c)divisible appropriately and3S ∈ [42, 57]. - For
Sinteger, need36 + (a+b+c)divisible by 3. Since36 ≡ 0 (mod 3), needa+b+c ≡ 0 (mod 3). - Possible
a+b+cvalues that are multiples of 3 within [6, 21]:6, 9, 12, 15, 18, 21. - Corresponding
S = (36 + a+b+c)/3:14, 15, 16, 17, 18, 19. - Each
Svalue is achievable (CEMC official solution constructs explicit examples). - Sum of all possible
S:14 + 15 + 16 + 17 + 18 + 19 = 99.
Beautiful pattern
The 6 possible S values form an arithmetic sequence — sum = 6 × (14 + 19)/2 = 6 × 16.5 = 99.
Answer
B — 99
Leave a Reply