Please prove the following statement:
In every set of 5 integers one can always select 3 members such that their sum is divisible by 3.
Source: Crux Mathematicorum
REM: The original puzzle specifies positive integers. Considering this word as redundant I have erased it.
Do you agree?
We know that each element of the 5 member set is congruent to:
0, 1, or 2 (mod 3).Accordinly, regardless of what form the set of 5 integers may assume, we can always choose the 3-element integer subset in the following manner:
CASE 1: Every element of the 3 member subset is congruent to 0 (mod 3)
It trivially follows that since each of the members is divisible by 3, their sum must be divisible by 3.
CASE 2: Every element of the 3 member subset is congruent to 1(mod 3)
The sum of the three members is congruent to:
1+1+1(mod 3)
== 3 (mod 3)
== 0 (mod 3)
Accordingly, the sum of the three members of the subset add up to a multiple of 3
CASE 3: Every element of the 3 member subset is congruent to
2(mod 3)
Then, the sum of these members is congruent to:
2+2+2 (mod 3)
== 6 (mod 3)
== 0 (mod 3)
Accordingly, the sum of the three members of the subset sum to a multiple of 3.
CASE 4: of the three members- one is congruent to 0(mod 3), another is congruent to 1(mod 3) and the remaining one is congruent to 2(mod 3)
The sum of the three members is then congruent to:
0+1+2 (mod 3)
== 3 (mod 3)
== 0 (mod 3)
Accordingly, the sum of the elements of the subset sum to a multiple of 3.
Consequently, whatever be the constitution of 5 member set, one can always select a 3 member subset , such that the sum of the elements of the subset is divisible by 3.
*** I perfectly agree that the stipulation of positive integers is not required as the above-mentioned proof covers all integers.
Edited on July 15, 2022, 10:20 pm
Puzzle Solution
