# Math Help - Pigeonhole Theorem

1. ## Pigeonhole Theorem

A form of the pigeonhole theorem is stated as "If f is a function from a finite set X to a finite set Y with |X| > |Y| then $f(x_1) = f(x_2)$ for some $x_1, x_2 \in X$, $x_1 \neq x_2$

Now a question says: An inventory consists of a list of 89 items, each marked "available" or "unavailable". There are 45 available items, show that there are at least two available items in the list exactly 9 items apart.

Now I just don't know how to apply the pigeonhole theorem to this question, what is set X and Y in this case? And what is the function?

Many thanks!

2. Please check the wording of this problem.
I think the it must be 80 items and not 89.

PS. That is a typo. Otherwise I think there is a counterexample.

3. Can someone please translate this question to Hebrew(especially the last part...)?

4. Thanks guys, I have rechecked the question, that is exactly what it says :S

5. if it is 80 here is a hint

split all the numbers into to 9 buckets (using modulo 9)

how many maximum numbers can you select from each bucket?

Note: I have been thinking about how to explicitly express this in terms of the statement of the pigeon-hole principle - but couldn't make much progress. Maybe someone on this froum can help

6. Thanks again, actually the question also said (For example items at position 13 and 22 satisfy the condition) and I assume by 89 items they are listed in position from 1-89.

Does this help?

7. Originally Posted by usagi_killer
Thanks again, actually the question also said (For example items at position 13 and 22 satisfy the condition) and I assume by 89 items they are listed in position from 1-89.

Does this help?
So the source really says 89? Counterexample

{1, 2, 3, 4, 5, 6, 7, 8, 9, 19, 20, 21, 22, 23, 24, 25, 26, 27, 37, 38, 39, 40, 41, 42, 43, 44, 45, 55, 56, 57, 58, 59, 60, 61, 62, 63, 73, 74, 75, 76, 77, 78, 79, 80, 81}

8. Yeah I got that counter example too, the solutions do it like this: (It makes sense so I don't know where the fallacy is)

Let $a_i$ denote the position of the $i$th available item. We must show that $a_i-a_j = 9$ for some i and j. Consider the numbers:

$a_1, a_2, \cdots, a_{45}$ ...[1]

and

$a_1+9, a_2+9, \cdots. a_{45}+9$ ...[2]

The 90 numbers from [1] and [2] have possible values from 1-89. So by the form of the pigeonhole theorem I stated in the OP, two numbers must coincide. We cannot have two of [1] or two of [2] identical, thus some number in [1] is equal to some number in [2]. Therefore $a_i = a_j+9 \implies a_i-a_j = 9$ for some i and j.

Now I understand their working but obviously there exists a counterexample, so where is the fallacy in their working?

Many thanks again!

9. Originally Posted by usagi_killer
Yeah I got that counter example too, the solutions do it like this: (It makes sense so I don't know where the fallacy is)

Let $a_i$ denote the position of the $i$th available item. We must show that $a_i-a_j = 9$ for some i and j. Consider the numbers:

$a_1, a_2, \cdots, a_{45}$ ...[1]

and

$a_1+9, a_2+9, \cdots. a_{45}+9$ ...[2]

The 90 numbers from [1] and [2] have possible values from 1-89. So by the form of the pigeonhole theorem I stated in the OP, two numbers must coincide. We cannot have two of [1] or two of [2] identical, thus some number in [1] is equal to some number in [2]. Therefore $a_i = a_j+9 \implies a_i-a_j = 9$ for some i and j.

Now I understand their working but obviously there exists a counterexample, so where is the fallacy in their working?

Many thanks again!
That wording could be better, but anyway here's an obvious flaw: the numbers in [1] must be in {1, ..., 89} and the numbers in [2] must be in {10, ... , 98}. So, a function from a set with cardinality 90 to a set with cardinality 98 need not have a duplicate.

That makes me realize how to apply pidgeonhole to the real problem when we have 80 items in our inventory. You do the same steps but you get that you're trying to fit 90 elements into a set with cardinality 89.

10. Oh right, that makes sense!

Thanks very much!!

11. Originally Posted by undefined
That wording could be better, but anyway here's an obvious flaw: the numbers in [1] must be in {1, ..., 89} and the numbers in [2] must be in {10, ... , 98}. So, a function from a set with cardinality 90 to a set with cardinality 98 need not have a duplicate.

That makes me realize how to apply pidgeonhole to the real problem when we have 80 items in our inventory. You do the same steps but you get that you're trying to fit 90 elements into a set with cardinality 89.
@undefined - sorry but can you elaborate the proof for "That makes me realize how to apply pidgeonhole to the real problem when we have 80 items in our inventory. You do the same steps but you get that you're trying to fit 90 elements into a set with cardinality 89". I haven't been able to follow it please.

12. I knew that I had seen this question before.
It is worked out as as example on page 250 of the fourth edition of Discrete Mathematics by Johnsonbaugh.
And it is 80 items and not 89.

13. Originally Posted by aman_cc
@undefined - sorry but can you elaborate the proof for "That makes me realize how to apply pidgeonhole to the real problem when we have 80 items in our inventory. You do the same steps but you get that you're trying to fit 90 elements into a set with cardinality 89". I haven't been able to follow it please.
Sure. So this is just post #8 rewritten slightly.

Label the items {1, 2, ... , 80}. Let $\displaystyle A = \{a_1, a_2,\,\dots\,,a_{45}\}$ be the set of available items. The elements of A are distinct and in the range {1, 2, ... , 80}. Let $B = \displaystyle \{a_1+9, a_2+9,\,\dots\,,a_{45}+9\}$. Likewise the elements of B are distinct and in the range {10, 11, ... , 89}. Let $\displaystyle X = A \cup B$. So X is composed of elements in the range {1, 2, ... , 89}. But we started with 90 elements (45 from A and 45 from B), so by the pidgeonhole principle, at least two of those 90 elements are identical. Since the elements of A and B are distinct, we must have some $\displaystyle a_i \in A$ that is identical to some $\displaystyle a_j + 9 \in B$. QED.

14. Originally Posted by Plato
I knew that I had seen this question before.
It is worked out as as example on page 250 of the fourth edition of Discrete Mathematics by Johnsonbaugh.
And it is 80 items and not 89.
Yeah I have the 7th international edition, says 89 for some reason haha