Answer to Question #266119 in Discrete Mathematics for khan

Question

1. Show that in any set of six classes, each meeting regularly once a week on a particular day of the week, there must be two that meet on the same day, assuming that no classes are held on weekends.

2. Show that if there are 30 students in a class, then at least two have last names that begin with the same letter.

Answer 1

1. Let us show that in any set of six classes, each meeting regularly once a week on a particular day of the week, there must be two that meet on the same day, assuming that no classes are held on weekends.

Since there are 5 working days by a week and 6 classes, by Pigeonhole Principle there must be two that meet on the same day.

2. Let us show that if there are 30 students in a class, then at least two have last names that begin with the same letter.

Taking into account that there are 26 uppercase letter in english alphabet and 30 students in a class, by Pigeonhole Principle there must be at least two that have last names that begin with the same letter.