86.9k views
3 votes
If n + 1 integers are chosen from the set {1, 2, 3, 2n}, where n is a positive integer, must at least one of them be even?

1 Answer

3 votes

Final answer:

Yes, if n + 1 integers are chosen from the set {1, 2, 3, ..., 2n}, at least one of them must be even due to the pigeonhole principle.

Step-by-step explanation:

The student has asked whether, if n + 1 integers are chosen from the set \{1, 2, 3, ..., 2n\}, where n is a positive integer, at least one of them must be even. The answer is yes, and here's why:

Consider the set \{1, 2, 3, ..., 2n\}. This set contains n even numbers (2, 4, 6, ..., 2n) and n odd numbers (1, 3, 5, ..., 2n-1). If we are choosing n + 1 integers from this set, then even if we tried to pick only odd numbers, we can pick at most n odd numbers since that's all there are. Since we are picking one more than the total number of odd numbers available, we must end up picking at least one even number.

Therefore, it is guaranteed that in selecting n + 1 integers from this set, at least one of the integers will be even, simply due to the pigeonhole principle.

User Jdahern
by
7.4k points

No related questions found