Pigeonhole principle

Let(xi,yi),i = 1,2,3,4,5, be a set of five distinct points with integer coordinates in the xy plane. Show that the midpoint of the line joining at least one pair of these points has integer coordinates.

The midpoint of the line joining the points (a,b) and (c,d) is ((a+c)/2,(b+d)/2). The coefficient for this midpoint will have integer coefficients if and only if both a and c, and b and d have the same parity. In other words, they are both odd, or both even. Notice that the sum of two odd […]

Show that if f is a function from S to T, where S and T are finite sets with |S| > |T |, then there are elements s1 and s2 in S such that f(s1)=f(s2), or in other words, f is not one-to-one

Let’s start this exercise with two definitions: the definition of function and the pigeonhole principle. Definition: “Let A and B be nonempty sets. A function f from A to B is an assignment of exactly one element of B to each element of A. We write f(a) = b if b is the unique element

Let d be a positive integer. Show that among any group of d + 1 (not necessarily consecutive) integers there are two with exactly the same remainder when they are divided by d

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.” Source: Discrete Mathematics and its Applications by Rosen. Let’s have d boxes numbered 0,

A bowl contains 10 red balls and 10 blue balls. A woman selects balls at random without looking at them

Let’s start with the following 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.” THE GENERALIZED PIGEONHOLE PRINCIPLE: “If N objects are placed into k boxes, then there

Let n be a positive integer. Show that in any set of n consecutive integers there is exactly one divisible by n.

To solve this exercise, we will use the fact of how many reminders of the division there can be when dividing by a certain number. If you divide by n, you can get n possible reminders. These are 0, 1, 2, …, n-1. If we have a certain set of n consecutive integers, we can

A drawer contains a dozen brown socks and a dozen black socks, all unmatched. A man takes socks out at random in the dark.

Let’s revisit the two principles that apply to this type of exercise. “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.” “THE GENERALIZED PIGEONHOLE PRINCIPLE If N objects are

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

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

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?

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

(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?

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

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

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,