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

- Apr 13th 2008, 10:51 AMfafafaCombinatorics HELP
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!!! - Apr 13th 2008, 10:54 AMJhevon
Have you ever heard of the Pigeon Hole principle? You can use that here.

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 - Apr 13th 2008, 10:56 AMfafafa
i have no idea what to do..is it possible you can show me the answer step by step plz...

- Apr 13th 2008, 11:08 AMMoo
Hello,

Here are the possibilities :

0-0-0 -> ok

0-0-1 -> not ok

What are the conditions upon those integers ? Consecutive ? - Apr 13th 2008, 11:32 AMangel.white
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.