Discrete Mathematics

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

Pigeonhole principle /

Let’s start with the following definition. THE PIGEONHOLE PRINCIPLE: “If k is a positive integer and k + 1 or more objects are placed into k boxes, then there is at least one box containing two or more of the objects.” Discrete Mathematics and its applications by Rosen. The number of available letters in the […]

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

What is the minimum number of students, each of whom comes from one of the 50 states, who must be enrolled in a university to guarantee that there are at least 100 who come from the same state? 

Pigeonhole principle /

Let’s start with definitions. THE PIGEONHOLE PRINCIPLE: “If k is a positive integer and k + 1 or more objects are placed into k boxes, then there is at least one box containing two or more of the objects.” Discrete Mathematics and its applications by Rosen. Like in previous exercises, let’s find the boxes and

What is the minimum number of students, each of whom comes from one of the 50 states, who must be enrolled in a university to guarantee that there are at least 100 who come from the same state?  Read More »

(a) Show that if five integers are selected from the first eight positive integers, there must be a pair of these integers with a sum equal to 9. Is the conclusion in part (a) true if four integers are selected rather than five?

Pigeonhole principle /

THE PIGEONHOLE PRINCIPLE: “If k is a positive integer and k + 1 or more objects are placed into k boxes, then there is at least one box containing two or more of the objects.” Discrete Mathematics and its applications by Rosen. Like in previous exercises, let’s follow the principle and define the boxes and

(a) Show that if five integers are selected from the first eight positive integers, there must be a pair of these integers with a sum equal to 9. Is the conclusion in part (a) true if four integers are selected rather than five? Read More »

Show that among any group of five (not necessarily consecutive) integers, there are two with the same remainder when divided by 4

Pigeonhole principle /

Let’s refresh the pigeonhole principle. THE PIGEONHOLE PRINCIPLE: “If k is a positive integer and k + 1 or more objects are placed into k boxes, then there is at least one box containing two or more of the objects.” Discrete Mathematics and its applications by Rosen. When you divide an integer number by 4,

Show that among any group of five (not necessarily consecutive) integers, there are two with the same remainder when divided by 4 Read More »

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

Pigeonhole principle /

For this particular exercise, let’s refresh the pigeonhole principle. THE PIGEONHOLE PRINCIPLE: “If k is a positive integer and k + 1 or more objects are placed into k boxes, then there is at least one box containing two or more of the objects.” Discrete Mathematics and its applications by Rosen. As in previous counting

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 Read More »