Combinatorics path · C04

Before this lesson: Basic counting principles, Functions, inverses and composition

Your goal: Prove a map is both one-to-one and onto.

Start with the idea and one example. Take a break before the written task if you need it. The questions are original teaching exercises, not official past-paper questions.

Names you may know: bijective proof; one-to-one correspondence.

Counting with bijections: the key idea

A bijection is a reversible correspondence between two sets. To count a difficult set, map its objects to an easier set and prove both that the map is well-defined and that an inverse recovers every object uniquely. An encoding that loses information only gives an inequality or a wrong count. Binary strings correspond to subsets by recording membership; lattice paths correspond to position choices for their steps.

A worked example

Count paths from (0,0) to (4,3) using only right and up unit steps.

Each path is a seven-letter string with four R and three U symbols. Choosing the three positions of U uniquely determines the path, and every choice is valid. Thus the count is C(7,3)=35.

Your turn: change one thing

How many subsets does a five-element set have?

Try this on paper before opening the explanation.

Compare your reasoning

Encode each subset by a length-five binary string, with 1 for inclusion. This is a bijection, and each of five positions has two choices, giving 2⁵=32.

Pause and check

A trap to avoid: Showing a plausible map without an inverse or full coverage.

Practise and adjust the level

Foundation checks the language; Core applies the method; Stretch asks you to choose or justify an idea. These are levels within this lesson. A session selects six of the nine questions; unused questions allow the level to change. Advanced theory still needs written practice.

Interactive practice loads here. You can also use the complete question set below.

Write a complete argument

Prove that the numbers of even-sized and odd-sized subsets of a nonempty finite set are equal.

Planning hint

List the assumptions and the exact conclusion. Identify the definition or theorem in this lesson that connects them. Explain why its conditions hold before using it.

Read the full solution after your attempt

Fix one element e. Toggle its membership: remove it if present and add it if absent. This changes subset size by 1 and therefore reverses parity. Applying the operation twice returns the original subset, so it is a bijection between the two classes.

My proof notebook

Write on paper, or keep a draft here. Compare your reasoning with the solution only after a real attempt. The checklist is your own review, not an automatic mark.

All nine practice questions

Prefer paper or have JavaScript switched off? The complete question set, hints and solutions are here. Interactive practice uses these same questions in an order chosen from your answers.

1. What makes a counting correspondence a bijection?

Foundation

  1. It preserves colour
  2. It is only injective
  3. Every object has exactly one matching object in both directions
  4. It sends everything to one object
Hint

An inverse must recover the original.

Answer and reasoning

Every object has exactly one matching object in both directions. A bijection is both one-to-one and onto.

2. A subset of an n-element set can be encoded by what?

Foundation

  1. One decimal digit always
  2. A permutation only
  3. An unordered pair always
  4. A length-n binary string
Hint

Record inclusion separately for each element.

Answer and reasoning

A length-n binary string. Each bit states whether the corresponding element belongs to the subset.

3. How many subsets does a five-element set have?

Core

  1. 32
  2. 25
  3. 10
  4. 120
Hint

There are two choices per element.

Answer and reasoning

32. 2⁵=32.

4. How many right/up paths from (0,0) to (4,3)?

Core

  1. 35
  2. 12
  3. 21
  4. 42
Hint

Choose three up-step positions among seven.

Answer and reasoning

35. C(7,3)=35.

5. Toggling one fixed element of a subset changes what?

Stretch

  1. Nothing
  2. The parity of its size
  3. Its universe
  4. Its size by two
Hint

Exactly one membership bit flips.

Answer and reasoning

The parity of its size. Adding or removing one element reverses even/odd size.

6. Why must an encoding have an inverse?

Stretch

  1. To make every count factorial
  2. To avoid defining the domain
  3. To force the count to be even
  4. To exclude collisions and missing encoded objects
Hint

Equal counts need a one-to-one correspondence.

Answer and reasoning

To exclude collisions and missing encoded objects. The inverse verifies that every encoded object corresponds to exactly one original object.

7. A map with two inputs sharing one output fails which property?

Foundation

  1. Surjectivity necessarily
  2. Being a function necessarily
  3. Having a codomain
  4. Injectivity
Hint

A collision violates one-to-one correspondence.

Answer and reasoning

Injectivity. Injectivity forbids equal outputs from distinct inputs.

8. Right/up paths from (0,0) to (2,2): count?

Core

  1. 4
  2. 8
  3. 16
  4. 6
Hint

Choose two up positions among four.

Answer and reasoning

6. C(4,2)=6.

9. Why is toggling a fixed element its own inverse?

Stretch

  1. It changes two elements
  2. It always produces the empty set
  3. It sorts the subset
  4. Toggling twice restores its original membership
Hint

Add then remove, or remove then add.

Answer and reasoning

Toggling twice restores its original membership. Both possible initial membership states return after two toggles.

Choose your next step

Continue to Combinations with repetition. If this felt difficult, return to a prerequisite above. Every lesson stays open.

Open my revision list →

Original teaching material · IMOolympiad.com. Send a specific correction through our contact page. Learning progress is optional and stays in this browser.