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 of B assigned by the function f to the element a of A. If f is a function from A to B, we write f:A→B.”
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.
From the definition of a function, we can see that every element of A must have assigned exactly one element of B.
The function f is a function from S to T. So, exactly one element of T must be assigned to each element of S.
Let the number of elements in T be the number of boxes, and the number of elements in S is the number of objects that we will place in each box. Notice that |S|>|T|, in other words, we have more objects than boxes.
By the pigeonhole principle, there is at least one box (one element of T) that has two objects (two elements of S).
It follows that there are two elements s1,s2∈S (the two elements that are in the same box), such that f(s1)=f(s2).
Related exercises:
- 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.
- 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
- A bowl contains 10 red balls and 10 blue balls. A woman selects balls at random without looking at them
- Let n be a positive integer. Show that in any set of n consecutive integers there is exactly one divisible by n.
- A drawer contains a dozen brown socks and a dozen black socks, all unmatched. A man takes socks out at random in the dark.