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.
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 for some ,
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!
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
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 denote the position of the th available item. We must show that for some i and j. Consider the numbers:
...[1]
and
...[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 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.
@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 be the set of available items. The elements of A are distinct and in the range {1, 2, ... , 80}. Let . Likewise the elements of B are distinct and in the range {10, 11, ... , 89}. Let . 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 that is identical to some . QED.