MATC44H3 Chap.1 Combinatorial Questions and Proof by Contradiction
Combinatorial Questions and Proof by Contradiction
Four kinds of question
The first lecture of the course sorts combinatorics problems into four kinds. Existence problems ask whether an object with some property can be found at all. Construction problems ask for an explicit object that a reader can check. Enumeration problems ask for an exact count.
Optimization problems ask for the best possible value of some quantity, which needs both an example achieving it and an argument that nothing better exists.
The syllabus learning outcomes use the same four words, so naming the kind of question is the first step of every solution.
A checklist before a technique
The lecture also offers a list of problem-solving habits: test small cases, substitute numbers, hunt for a pattern, sketch the situation, give names to the quantities, check parity and symmetry, split into cases, and change the problem by shrinking or generalising it.
Next to those habits it names the techniques the term develops, among them the pigeonhole principle, contradiction, induction and strong induction, the extremal principle, invariance and counting in two ways.
Contradiction as the first technique
A proof by contradiction assumes that the claim is false and reasons until it reaches something impossible.
The course uses it immediately to prove the pigeonhole principle, and it returns in tiling, invariance and counting arguments. Well-ordering, the fact about the natural numbers that guarantees a least element in any non-empty set, is the hidden engine of many such proofs, because it lets you choose a smallest counterexample and then show that it cannot exist.
What this chapter covers
- 01
Existence, construction, enumeration and optimization
- 02
Problem-solving habits from the opening lecture
- 03
Negating statements with every and some
- 04
Proof by contradiction in three moves
- 05
Well-ordering and smallest counterexamples
- 06
What full justification means on an assignment
Worked example · free
No largest prime number
- 1Assume a largest prime exists, so the primes are p1, p2, up to pk, a finite list.
- 1Let N = p1 · p2 ⋯ pk + 1. Dividing N by any listed prime leaves remainder 1.
- 1N is greater than 1, so it has a prime factor, and that factor is not on the list.
- 1This contradicts the assumption that the list held every prime, so no largest prime exists.
Key terms
- Existence Question
- An existence question asks whether at least one object with a given property can be found.
- Enumeration Question
- An enumeration question asks for the exact number of objects with a given property.
- Optimization Question
- An optimization question asks for the best possible value, needing an example and a proof that nothing better exists.
- Well-Ordering Property
- The well-ordering property says every non-empty set of natural numbers has a least element.
Combinatorial Questions and Proof by Contradiction FAQ
How do I negate a statement that starts with every?
Replace every with some and negate the property. The negation of every group of 25 students has three sharing a birth month is that some group of 25 students has no month shared by three of them. A contradiction proof assumes exactly this negated sentence.
Why does an optimization question need two arguments?
Claiming that a value is the smallest that works makes two assertions: the value works, and every smaller value fails. The first needs a proof such as a pigeonhole argument, and the second needs a concrete example that fails. Course solutions give both, and an answer with only one half is incomplete.
Is proof by contradiction the same as proving the contrapositive?
They are related but different. The contrapositive proves if not Q then not P directly. A contradiction proof assumes P and not Q together and derives any impossibility. Both are valid, and either can be used when a direct argument is awkward.
What counts as a complete justification in this course?
The assignment instructions ask for a proof, a logical argument or a counter-example behind every answer. In practice that means stating the method, showing each step that a reader could check, and, for any claim that a value is best possible, giving the example that shows a smaller value fails.
Exam move
Write the four question types on a card with one example of your own for each. Then take three problems from the practice set and label each before solving it. Finally, write two short contradiction proofs from memory, checking that each states its assumption, reaches a named impossibility and closes with a conclusion.
Working through Combinatorial Questions and Proof by Contradiction in MATC44H3? Sia is AskSia’s AI Mathematics tutor — ask any MATC44H3 Combinatorial Questions and Proof by Contradiction question and get a clear, step-by-step explanation grounded in how MATC44H3 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
