Counting I Perhaps the relevance of this abstract mathematical statement to selecting footwear under poor lighting conditions is not obvious. However, let A be the set of socks you pick out, let B be the set of colors available, and let f map each sock to its color. The Pigeonhole Principle says that if A>b=3, then at least two elements of A(that is,at least two socks)must be mapped to the same element of B(that is, the same color). For example, one possible mapping of four socks to three colors is shown below. f 3rd sock blue 4th sock Therefore, four socks are enough to ensure a matched pair Not surprisingly, the pigeonhole principle is often described in terms of pigeons: if more than n pigeons fly into n pigeonholes, then at least two pigeons must fly into some hole. In this case, the pigeons form set A, the pigeonholes are set B, and f describes the assignment of pigeons to pigeonhole Mathematicians have come up with many ingenious applications for the pigeonhole principle. If there were a cookbook procedure for generating such arguments, wed give it to you. Unfortunately, there isnt one. One helpful tip, though: when you try to solve a problem with the pigeonhole principle, the key is to clearly identify three things 1. The set A(the pigeons) 2. The set B(the pigeonholes 3. The function f( the rule for assigning pigeons to pigeonholes Hail There are a number of generalizations of the pigeonhole principle. For example maps at least k +1 different elements of x to the same element ofr. every functionf: X-y Rule 6( Generalized Pigeonhole Principle). Ifx > k. r ther 3 For example, if you pick two people at random, surely they are extremely unlikely to ave exactly the same number of hairs on their heads. However, in the remarkable city of Boston, Massachusetts there are actually three people who have exactly the same number of hairs! Of course, there are many bald people in Boston, and they all have zero hairs But I'm talking about non-bald peopleCounting I 11 Perhaps the relevance of this abstract mathematical statement to selecting footwear under poor lighting conditions is not obvious. However, let A be the set of socks you pick out, let B be the set of colors available, and let f map each sock to its color. The Pigeonhole Principle says that if |A > B | | | = 3, then at least two elements of A (that is, at least two socks) must be mapped to the same element of B (that is, the same color). For example, one possible mapping of four socks to three colors is shown below. A f B 1st sock - red 2nd sock - green 3 3rd sock  - blue  4th sock  Therefore, four socks are enough to ensure a matched pair. Not surprisingly, the pigeonhole principle is often described in terms of pigeons: if more than n pigeons fly into n pigeonholes, then at least two pigeons must fly into some hole. In this case, the pigeons form set A, the pigeonholes are set B, and f describes the assignment of pigeons to pigeonholes. Mathematicians have come up with many ingenious applications for the pigeonhole principle. If there were a cookbook procedure for generating such arguments, we’d give it to you. Unfortunately, there isn’t one. One helpful tip, though: when you try to solve a problem with the pigeonhole principle, the key is to clearly identify three things: 1. The set A (the pigeons). 2. The set B (the pigeonholes). 3. The function f (the rule for assigning pigeons to pigeonholes). Hairs on Heads There are a number of generalizations of the pigeonhole principle. For example: Rule 6 (Generalized Pigeonhole Principle). If |X > k | · | | Y , then every function f : X Y maps at least k + 1 different elements of X to the same element of Y . → For example, if you pick two people at random, surely they are extremely unlikely to have exactly the same number of hairs on their heads. However, in the remarkable city of Boston, Massachusetts there are actually three people who have exactly the same number of hairs! Of course, there are many bald people in Boston, and they all have zero hairs. But I’m talking about non­bald people