Question 1208373: Prove that given any set of $17$ integers, not all odd, there exist nine of them whose sum is divisible by $2.$
Found 2 solutions by Edwin McCravy, ikleyn:
Answer by Edwin McCravy(20054)   (Show Source):
You can put this solution on YOUR website!
The sum of any number of evens is even.
The sum of any even number of odds is even.
Case 1:
If there are 9 or more evens, then the sum of 9 evens will be even.
Case 2:
If there are only 8 or fewer evens (but at least 1 even), then there are 9 or
more odds.
Take 8 of those odds and 1 even, and the sum of those 9 will be even.
PROVED.
Edwin
Answer by ikleyn(52778)  (Show Source):
You can put this solution on YOUR website! .
Prove that given any set of 17 integers, not all odd, there exist nine of them whose sum is divisible by 2.
~~~~~~~~~~~~~~~~~~~~~~~
Let m be the number of odd integers in our sets of 17 integer numbers, and
let n be the number of even integers in our sets of 17 integer numbers.
We have m + n = 17.
It implies that EITHER m >= 9 OR n >= 9.
In other words, one of the two integer numbers, m or n, must be at least 9.
Indeed, otherwise the sum m+n would not be more than 8 + 8 = 16; but m+n = 17.
If n >= 9, then we can take 9 even integer numbers from our set.
Their sum will be divisible by 2, so in this case these 9 integer numbers are the seeking set.
If m >= 9, then there are two sub-cases:
- (a) all integer numbers in our set are odd.
It contradict to the imposed condition, so this case can not happen.
- (b) there is at least one even number in our set of 17 integer numbers.
In this case, we form the set of 9 numbers, taking 8 odd numbers and this even number.
The sum of these 9 integer numbers is even number.
So, we proved that in any case, it is possible to find a subset of 9 integers with even sum.
The proof is complete and the problem is solved.
|
|
|
