# Suppose that n+1 integers are chosen from the set {1 , 2, ..., 2n}.

• Aug 1st 2010, 07:25 PM
Privoxy
Suppose that n+1 integers are chosen from the set {1 , 2, ..., 2n}.
Suppose that n+1 integers are chosen from the set {1 , 2, ..., 2n}. Show that at least
one is even. [HINT: Think about how many odd numbers there are in this set]

I was taking a look at this problem.... and think im doing it wrong because the answer seems too obvious.

My reasoning is that for any n in N, one of the numbers will always be even, and prove this by

n(0) n+1 = 1 = 1,2
n(1) n+1 = 2 = 1,2,3
n(2) n+1 = 3 = 1,2,3,4

Cheers
• Aug 1st 2010, 08:40 PM
undefined
Quote:

Originally Posted by Privoxy
Suppose that n+1 integers are chosen from the set {1 , 2, ..., 2n}. Show that at least
one is even. [HINT: Think about how many odd numbers there are in this set]

I was taking a look at this problem.... and think im doing it wrong because the answer seems too obvious.

My reasoning is that for any n in N, one of the numbers will always be even, and prove this by

n(0) n+1 = 1 = 1,2
n(1) n+1 = 2 = 1,2,3
n(2) n+1 = 3 = 1,2,3,4

Cheers

The set {1 , 2, ..., 2n} contains n even and n odd numbers. Pidgeonhole principle...