Lesson 6

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?