Question 1162751: Please use formal mathematical induction to prove that given any 37 positive integers, it’s possible to choose 7 whose sum is divisible by 7.
Answer by ikleyn(52852)   (Show Source):
You can put this solution on YOUR website! .
The method of Mathematical Induction is IRRELEVANT to this problem.
The proof is constructed based on other principles.
THE PROOF
Let an arbitrary set of 37 positive integer numbers is given.
I organize 7 boxes numbered from 0 to 6. So, the boxes are numbered 0, 1, 2, 3, 4, 5 and 6.
I distribute all these 37 numbers in these 7 boxes according their remainders modulo 7.
If some box has at least 7 numbers, then these 7 numbers provide the required sum.
If there is no a box with at least 7 numbers, it means that each box has no more than 6 numbers and all boxes have no more than 6 numbers.
If all boxes have at least one number, then their sum 0 + 1 + 2 + 3 + 4 + 5 + 6 = 21 (mod7) is divisible by 7.
If not all boxes have at least one number, it means that at least one box is empty.
In this case, we have 6 boxes with no more than 6 numbers in each, which gives 6*6 = 36 numbers.
But then the 37-th number breaks this scheme.
So, having 37 numbers in 7 boxes, we EITHER can find a box with at least 7 numbers in it
and then this box provides the required sum of 7 numbers,
OR, otherwise, all 7 boxes have at least one number each,
and then we can form the sum 0 + 1 + 2 + 3 + 4 + 5 + 6 = 21 (mod7)
of numbers from these boxes which is divisible by 7.
The proof is completed.
The key to the proof (and to the statement itself) is this equality 37 = 6*6 + 1.
Done.
|
|
|
