Puzzles
Counting & Combinatorics
These puzzles turn a concrete counting question into a general formula. The pattern worth noticing across all of them is the same one behind dynamic programming and combinatorial algorithms: observe a small case, find the rule connecting it to the next case, and let that rule scale to any size.
1. The Handshake Problem
At a party of n people, every person shakes hands with every other person exactly once.
Rules
- Each pair shakes hands exactly once
- No one shakes their own hand
- Order within a handshake doesn't matter
Your task — Find a formula for the total number of handshakes in terms of n, and check it for n equal to 10.
Difficulty — Easy
Hint 1 — Think of choosing pairs.
Hint 2 — Each person shakes n minus 1 hands.
Hint 3 — Avoid counting each handshake twice.
Main idea — Counting each person's handshakes and then correcting for double-counting lands on the same answer as simply choosing 2 people out of n.
Solution
- Each of the n people shakes hands with the other n minus 1 people.
- Multiplying gives n times (n minus 1), but this counts every handshake twice, once from each side.
- Dividing by 2 gives the formula n(n minus 1) divided by 2. For n equal to 10, that's 10 times 9 divided by 2, which is 45.
Reasoning
This is exactly the combinatorial idea of choosing 2 items from a set of n without regard to order, written as "n choose 2."
It also matches the number of edges in a complete graph on n vertices, a connection that shows up throughout graph algorithms and combinatorial counting in programming.
2. How Many Squares on a Chessboard?
A standard chessboard is an 8 by 8 grid of unit squares.
Rules
- Squares can range from 1x1 to 8x8
- Squares must align with the grid lines
- Every position counts separately
Your task — Find the total number of squares of all sizes that can be found on the board.
Difficulty — Medium
Hint 1 — Count squares size by size.
Hint 2 — A size k square fits (9 minus k) ways per row.
Hint 3 — Sum the squares of those counts.
Main idea — The number of positions for each size of square is itself a perfect square, so the total is simply the sum of the first 8 square numbers.
Solution
- A 1x1 square can start at 8 different rows and 8 different columns, giving 8 times 8, which is 64 positions.
- A size k square can start at (9 minus k) rows and (9 minus k) columns, giving (9 minus k) squared positions.
- Summing (9 minus k) squared for k from 1 to 8 gives 64 plus 49 plus 36 plus 25 plus 16 plus 9 plus 4 plus 1, which totals 204.
Reasoning
Each square size contributes a perfect square number of positions, because the square's top-left corner has (9 minus k) valid choices in each of two independent directions.
Summing these squared counts across all 8 sizes is the classic sum-of-squares formula in disguise, the same pattern that shows up in nested-loop counting problems in programming.
3. How Many Rectangles on a Chessboard?
On the same 8 by 8 chessboard, a rectangle is any shape formed by choosing two horizontal grid lines and two vertical grid lines.
Rules
- Rectangles must align with grid lines
- Any width and height counts, including squares
- The board has 9 horizontal and 9 vertical lines
Your task — Find the total number of rectangles of any shape that can be found on the board.
Difficulty — Medium
Hint 1 — Rectangles come from line pairs.
Hint 2 — Choose 2 of 9 lines each way.
Hint 3 — Multiply the two choice counts.
Main idea — Every rectangle is uniquely set by picking any 2 of the 9 horizontal lines and any 2 of the 9 vertical lines, turning the whole problem into a simple combination count.
Solution
- There are 9 horizontal lines and 9 vertical lines on the board.
- The number of ways to choose 2 horizontal lines is "9 choose 2," which is 36, and the same is true for vertical lines.
- Multiplying these together, 36 times 36, gives 1296 total rectangles.
Reasoning
Choosing any 2 horizontal lines and any 2 vertical lines always defines exactly one rectangle, and every rectangle on the board can be described this way, with no overlap or omission.
This turns a seemingly geometric counting problem into a pure application of combinations, the same "choose" logic used throughout combinatorics and probability.
4. Number of Ways to Climb Stairs
A staircase has n steps, and at each move you can climb either 1 step or 2 steps at a time.
Rules
- Each move is 1 or 2 steps
- You must land exactly on step n
- Different move orders count separately
Your task — Find a rule for the number of distinct ways to reach the top of an n-step staircase.
Difficulty — Easy
Hint 1 — How do you reach the last step?
Hint 2 — Two ways to land there.
Hint 3 — Add the two smaller cases.
Main idea — Since the very last move is either a single step from step n minus 1 or a double step from step n minus 2, the total ways to reach step n is just the sum of the ways to reach those two earlier steps.
Solution
- Let f(n) be the number of ways to reach step n.
- The last move reaching step n comes from step n minus 1 or step n minus 2, so f(n) equals f(n minus 1) plus f(n minus 2).
- With f(1) equal to 1 and f(2) equal to 2 as starting points, this recurrence generates 1, 2, 3, 5, 8, 13, and onward.
Reasoning
Breaking the problem down by the very last move made is a classic technique for building a recurrence relation, and here it produces the same recurrence that defines the Fibonacci sequence.
This is a direct bridge to dynamic programming, where storing and reusing f(n minus 1) and f(n minus 2) turns an exponential brute-force search into a simple linear-time calculation.
5. Counting Diagonals in a Polygon
A convex polygon has n vertices.
Rules
- A diagonal connects 2 non-adjacent vertices
- Polygon sides don't count as diagonals
- Each diagonal is counted only once
Your task — Find a formula for the total number of diagonals in an n-sided polygon.
Difficulty — Easy
Hint 1 — Start from all possible connections.
Hint 2 — Subtract the polygon's own sides.
Hint 3 — Each side removes one connection.
Main idea — Counting every possible line between any two vertices and then removing the ones that are actually sides of the polygon leaves exactly the diagonals.
Solution
- The total number of segments connecting any 2 of the n vertices is "n choose 2," which equals n(n minus 1) divided by 2.
- Among these segments, exactly n of them are the sides of the polygon itself, not diagonals.
- Subtracting gives the diagonal count: n(n minus 1) divided by 2, minus n, which simplifies to n(n minus 3) divided by 2.
Reasoning
Since a polygon's vertices form a complete set of pairwise connections, subtracting only the segments that coincide with actual polygon edges isolates the diagonals precisely.
This overcount-then-subtract strategy, count everything then remove what doesn't belong, is a common combinatorial technique that also appears in inclusion-exclusion counting problems.
6. People Sitting Around a Circular Table
n people are to be seated around a circular table, where seatings that are rotations of each other are considered the same arrangement.
Rules
- Seats are arranged in a circle
- Rotated arrangements count as identical
- Reflections are treated as different
Your task — Find a formula for the number of distinct seating arrangements.
Difficulty — Medium
Hint 1 — Fix one person's seat.
Hint 2 — Arrange everyone else normally.
Hint 3 — That's (n minus 1) factorial.
Main idea — Fixing one person's position removes the rotational symmetry entirely, turning a circular arrangement problem into an ordinary problem of arranging the remaining people in a line.
Solution
- Fix one specific person in one seat, since rotations of the same arrangement should not be counted separately.
- Arrange the remaining n minus 1 people freely around the rest of the table.
- The number of ways to do this is (n minus 1) factorial.
Reasoning
Every rotation of a full circular arrangement is considered identical, and there are exactly n such rotations for any arrangement of n people, so dividing the usual n factorial linear arrangements by n leaves (n minus 1) factorial distinct circular arrangements.
Fixing one person's seat achieves the same result directly, without needing to divide afterward.
7. Maximum Pieces from N Straight Cuts
You want to cut a flat, round pizza using n straight-line cuts, where each cut is a full straight line across the pizza.
Rules
- Cuts are straight lines, not curves
- Cuts may cross but not overlap
- You want the maximum piece count
Your task — Find a formula for the maximum number of pieces achievable with n straight cuts.
Difficulty — Hard
Hint 1 — Each new cut crosses all before it.
Hint 2 — Every crossing adds one region.
Hint 3 — Add the cut number to the running total.
Main idea — To maximize pieces, each new cut should cross every previous cut at a different point, and every such crossing adds exactly one new region to the total.
Solution
- With 0 cuts, there is 1 piece.
- If the k-th cut crosses all k minus 1 earlier cuts at distinct points, it adds k new pieces.
- Adding up 1, then 1, 2, 3 up to n, gives the formula: 1 plus n(n plus 1) divided by 2.
Reasoning
A new straight line can add at most one new region for every previous line it crosses, since each crossing splits an existing region into two.
Maximizing crossings means every new cut should intersect all earlier cuts at distinct points, which leads directly to the well known plane-cutting formula, closely related to the triangular numbers used throughout combinatorics.
8. Arranging People with a Seating Restriction
5 people, including a specific couple, need to be seated in a row of 5 chairs, and the couple insists on sitting next to each other.
Rules
- All 5 people sit in a row
- The couple must sit adjacent
- Everyone else has no restriction
Your task — Find the number of distinct seating arrangements satisfying this restriction.
Difficulty — Medium
Hint 1 — Treat the couple as one unit.
Hint 2 — Arrange that unit with the rest.
Hint 3 — Then arrange the couple internally.
Main idea — Gluing the couple together into a single block turns the problem into arranging fewer, ordinary units, then separately accounting for the two ways the couple can be ordered inside that block.
Solution
- Treat the couple as a single combined unit, leaving 4 units total: the couple-block and the 3 other individuals.
- These 4 units can be arranged in 4 factorial ways, which is 24.
- Within the couple-block, the two people can switch places in 2 ways, so the total is 24 times 2, which is 48.
Reasoning
Bundling the constrained pair into a single unit removes the adjacency requirement from the counting process entirely, since arranging units automatically keeps the pair together.
Multiplying by the internal arrangements of the bundled unit accounts for every valid ordering, a standard technique for handling adjacency constraints in permutation counting.