Proofs of Universal Statements: Mathematical Induction · Complete Induction

Lesson 6

Nikolai Chukhin · Alexander S. Kulikov

To conclude this section, we prove a famous and important theorem on distinct representatives. There are several student clubs, and each club has a list of members:

  1. Chess club: Alice, Bob
  2. Math club: Bob, Carol
  3. Robotics club: Carol, David
  4. Art club: Alice, David
We would like to choose one representative from each club, with the extra rule that no person represents more than one club. So we want a system of distinct representatives. One possible choice:
  1. Chess: Alice
  2. Math: Bob
  3. Robotics: Carol
  4. Art: David
Everyone is distinct, so this is a valid system of representatives.

Problem. Now, consider the following clubs.

  1. Chess: Alice, Bob
  2. Math: Alice, Carol
  3. Physics: Bob, Carol
  4. Art: David, Emma
  5. Music: Frank, Grace
  6. Robotics: Alice, Bob, Carol
Is it possible to select a distinct representative from each club?

5 points

  1. It is possible.

  2. It is impossible.