Try a short problem first. Then use the topic map to plan what to learn next.
Jump to the full topic map · Continue the four-subject practice plan
Worked example: six choices force a consecutive pair
Choose six distinct integers from 1 through 10. Prove that two chosen integers differ by 1. Split the ten integers into five boxes: {1,2}, {3,4}, {5,6}, {7,8}, {9,10}. If each box contained at most one chosen integer, there would be at most five choices. Since there are six, some box contains both its integers. Those two differ by 1.
The choice of boxes does the work. Six arbitrary groups would not give the same contradiction.
Change the boxes
- Choose six distinct integers from 1 through 10. Show that two sum to 11.
- Can five integers be chosen from 1 through 10 with no consecutive pair?
Solutions
1. Use {1,10}, {2,9}, {3,8}, {4,7}, {5,6}. Six choices force a full box, whose two numbers sum to 11.
2. Yes: {1,3,5,7,9}. This example shows why six, rather than five, is necessary for the first claim. A construction is a complete answer to an existence question when its properties are checked.
These are teaching examples written for this guide, not past-paper questions or an official marking scheme.
Topic map and learning goals
| Unit | Core content | Advanced or extension content |
|---|---|---|
| Counting | Sum/product rules, factorials, permutations, combinations | Counting with restrictions, circular arrangements and symmetry |
| Counting structures | Bijections, complementary counting, inclusion–exclusion | Double counting of incidences and weighted counting |
| Pigeonhole principle | Basic and generalised forms | Constructing the right boxes; geometric and number-theoretic applications |
| Invariants | Parity, colouring, quantities preserved by a move | Monovariants and termination arguments |
| Extremal principle | Choose a largest, smallest or otherwise extreme object | Minimal counterexamples and improving a supposedly optimal arrangement |
| Recursion | Build cases from smaller cases; simple recurrence relations | State-based recurrences and constructive induction |
| Graph theory | Vertices, edges, degrees, paths, cycles, trees | Connectivity, bipartite graphs, matching and extremal graph arguments |
| Games and algorithms | Winning/losing positions, strategy stealing in suitable settings | Proving an algorithm works and that a game strategy covers all replies |
| Arrangements and tilings | Chessboards, dominoes, partitions, subsets | Colourings, transformations and constructive existence proofs |
| Probability | Finite sample spaces, basic probability and expectation | Probabilistic existence arguments as an optional advanced technique |
| Generating functions | Optional enrichment after recurrences and algebra | Encoding counting sequences and extracting coefficients |
Learning outcomes: count without omissions or duplicates; prove a construction works; establish both an upper bound and an example attaining it when finding a maximum. Writing down small cases should lead to a general argument.