Let a1, a2, a3, a4 ,a5, be any distinct positive integers. Show that there exists at least one subset of three integers whose sum is divisible by 3.
what is the answer to this...plzz HELPP!!!
Printable View
Let a1, a2, a3, a4 ,a5, be any distinct positive integers. Show that there exists at least one subset of three integers whose sum is divisible by 3.
what is the answer to this...plzz HELPP!!!
Have you ever heard of the Pigeon Hole principle? You can use that here.Quote:
Originally Posted by fafafa
Note that any positive integer is either congruent to 0 mod 3 or 1 mod 3 or 2 mod 3. we have more than three integers here, so we know all congruences are accounted for. Further more, at least one congruence repeats. Try doing this by cases. (There may be an easier way, I'm not a Number Theorist)
Any questions? Do you have an idea of how to proceed?
EDIT: Ah, nevermind, I just realized this post makes no sense! Nothing is stopping us from choosing all the numbers of one congruence class
i have no idea what to do..is it possible you can show me the answer step by step plz...
Hello,
Here are the possibilities :
0-0-0 -> ok
0-0-1 -> not ok
What are the conditions upon those integers ? Consecutive ?
You have 5 integers.
Each integer must be congruent to either 0, 1, or 2 (mod 3).
if any 3 are congruent (mod 3), then 3 divides their sum
ie 5 + 5 + 5 = 3+2 + 3+2 + 3+2 = 3(3+2)
and if all 3 mods are represented, then 3 divides their sum
ie 5 + 6 + 7 = 3+2 + 3+3 + 3+4 = 3+(3-1) + 3+(3+0) + 3+(3+1) = 3*3 + (3*3 -1+0+1) = 3*3 + 3*3 = 3(3+3)
*note, those examples are for your understanding, I wouldn't put them in your proof, if you need to show this, show it in a more abstract way that can be applied to any given situation*
So worst case, two are congruent to 0, or 1, or 2 (mod 3) and two more are congruent to 0, or 1, or 2 (mod 3), but these two sets of numbers are not congruent to eachother (mod 3). Then if the 5th term is congruent to either of these sets, 3 will divide their sum. The only alternative is that it is not congruent to any of the other numbers (mod 3) in which case, all three mods are represented, and so any combination of a 0, 1, and 2 (mod 3) will sum to a number divisible by 3.