A set of four distinct numbers are chosen from the set { 1 , 2 , 3 … 9 , 1 0 , 1 1 } . How many ways can this set of 4 numbers be chosen such that the sum is divisible by 3 ?
Details and assumptions
Choosing the numbers { 1 , 2 , 3 , 6 } is the same as choosing the numbers { 6 , 3 , 2 , 1 } .
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Simple and the best solution.
We can group the 11 numbers in three sets based on how "far" they are from being a multiple of 3. The first set, say set A, consists of those that are already multiples of 3, so the numbers here are 3, 6, and 9. The second set, set B, consists of those who need 1 more in order to be a multiple of 3. So set B has 2,5,8, and 11. Lastly, set C consists of those that need 2 more in order to become a multiple of 3. So set C has 1,4,7, and 10.
Notice that if we want to pick numbers from either set B or C and have a sum divisible by 3, either one of the two should happen.
Picking any number from A won't cause problems because they're already multiples of 3.
So from there, we have 4 possible mutually exclusive scenarios for having a chosen set of 4 that is divisible by 3.
After this, all we have to do is to count the number of ways for each scenario and add them up. We can make use of the combination function here.
Thus, we have a total of 12 + 12 + 36 + 48 or 108 ways of choosing a set of 4 number such that the sum is divisible by 3.
I admire your way. Using logic, eh?
Log in to reply
Thank you! :) Yeah, I felt more comfortable explaining it in a more organic way.
First, we divide the numbers into three categories according to the remainder when divide by 3.
The first category is the numbers which left remainder 1 when divide by 3.
S 1 = { 1 , 4 , 7 , 1 0 } = 4
The second category is the numbers which left remainder 2 when divide by 3.
S 2 = { 2 , 5 , 8 , 1 1 } = 4
The third category is the numbers which is divisible by 3
S 3 = { 3 , 6 , 9 } = 3
Now, we can select the numbers according to their categories.
The first combination of the categories which sum is divisible by 3 is S 1 + S 1 + S 1 + S 3 .
The numbers of ways to do this are ( 3 4 ) × 3 = 1 2
The second combination of the categories which sum is divisible by 3 is S 2 + S 2 + S 2 + S 3 .
The numbers of ways to do this are ( 3 4 ) × 3 = 1 2
The third combination of the categories which sum is divisible by 3 is S 1 + S 1 + S 2 + S 2 .
The numbers of ways to do this are ( 2 4 ) × ( 2 4 ) = 3 6
The forth combination of the categories which sum is divisible by 3 is S 1 + S 2 + S 3 + S 3 .
The numbers of ways to do this are 4 × 4 × ( 2 3 ) = 4 8
∴ The total number of ways can the set of 4 numbers be chosen such that the sum is divisible by 3 is 1 2 + 1 2 + 3 6 + 4 8 = 1 0 8 .
We consider the set modulo 3 : { 1 , 2 , 0 , ⋯ , 0 , 1 , 2 } . Due to a sort of weird non-symmetry, it'll probably be best to consider cases mod 3 . We want the sum of the elements, mod 3 to be exactly 0 . We can several cases, in terms of what the elements can be, mod 3 . Ordering does not matter.
Case 1 : 0 , 0 , 0 , 0
There are only three 0 s in the original set, so we cannot choose 4 of them. Thus, there are 0 ways we can satisfy this case.
Case 2 : 1 , 1 , 1 , 0
We must choose three 1 s out of the 4 of them and one 0 out of the 3 of them. There are ( 3 4 ) ⋅ ( 1 3 ) = 4 ⋅ 3 = 1 2 ways to satisfy this case.
Case 3 : 2 , 2 , 2 , 0
We must choose three 2 s out of the 4 of them and one 0 out of the 3 of them. Just as in Case 2, we have 1 2 ways to satisfy this case.
Case 4 : 1 , 1 , 2 , 2
We must choose two 2 s out of the 4 of them and two 1 s out of the 4 of them. We have ( 2 4 ) ⋅ ( 2 4 ) = 6 ⋅ 6 = 3 6 ways to satisfy this case.
Case 5 : 0 , 0 , 1 , 2
We must choose two 0 s out of the 3 of them, one 1 out of the 4 of them and one 2 out of the 4 of them. There are ( 2 3 ) ⋅ ( 1 4 ) ⋅ ( 1 4 ) = 3 ⋅ 4 ⋅ 4 = 4 8 ways to satisfy this case.
Altogether : We have 0 + 1 2 + 1 2 + 3 6 + 4 8 = 1 0 8 ways in total.
■
We can further divide the given set into 3 different sets based on their remainder when divided by 3. Here are the three sets: {3,6,8} -> 0 (mod 3) {1,4,7,10}-> 1 (mod 3) {2,5,8,11}-> 2 (mod 3)
Listing down the possible combination of remainders to yield a 0 (mod 3): (0,0,1,2), (0,2,2,2), (0,1,1,1) and (1,1,2,2) Thus, we can compute for the possible ways by using the "choose" notation.
=(3C2)(4C1)(4C1)+(4C3)(3C1)+(4C3)(3C1)+(4C2)(4C2) =48+12+12+36 =108 possible ways //
We can split up the set with mods, 1 , 4 , 7 , 1 0 ≡ 1 ( mod 3 ) being one subset, 2 , 5 , 8 , 1 1 ≡ 2 ( mod 3 ) being another, and 3 , 6 , 9 ≡ 0 ( mod 3 ) . Then, we can do the problem with casework.
The combinations of mods that will give a sum divisible by 3 are ( 1 , 1 , 1 , 0 ) , ( 1 , 1 , 2 , 2 ) , ( 1 , 2 , 0 , 0 ) , and ( 2 , 2 , 2 , 0 ) . Notice that ( 0 , 0 , 0 , 0 ) is not included because there are only three numbers divisible by 3 in the original set.
By using casework, there are 12 ( 4 C 3 × 3 C 1 ) cases for the ( 1 , 1 , 1 , 3 ) and ( 2 , 2 , 2 , 3 ) subsets, 36 ( 4 C 2 × 4 C 2 ) cases for the ( 1 , 1 , 2 , 2 ) subset, and 48 ( 4 C 1 × 4 C 1 × 4 C 2 ) cases for the ( 1 , 2 , 3 , 3 ) subset. Thus, there are 1 2 + 1 2 + 3 6 + 4 8 = 1 0 8 ways.
When the number 1,2,3,...,9,10,11 are divided by 3, the remainders are {1,2,0,1,2,0,1,2,0,1,2}
We now have to pick four number from the above set whose sum is a multiple of 3. We cannot pick four zeros as there are only three available.
Case 1: Pick three zeros. Then we cannot pick only one number which makes the sum a multiple of three.
Case 2: Pick 2 zeros. Then we have to pick one 1 and one 2 to make the sum a multiple of three. Ways of doing this is 3C2 x 4C1 x 4C1 = 48 (A)
Case 3: Pick one zero. Then we can either pick three 1s or three 2s to make the sum a multiple of three. Ways of doing this= (3C1 x 4C3) + (3C1 x 4C3) = 24 (B)
Case 4: Pick 0 zeros. Then we have to pick two 1s and two 2s to make the sum a multiple of three. Ways of doing this= 3C0 x 4C2 x 4C2 = 36(C)
Total ways=Answer=A+B+C=48+24+36=108 :)
NOTE: nCr refers to ways of choosing r objects out of n objects where all n objects are distinct nCr = n! / ( (n-r)! x r! )
The numbers all is 1,2,3,4,5,6,7,8,9,10,11, which will chose four of them so that the sum of the chosen numbers are divisible by 3. So, the divide them into three groups, such as; the group of 3 mod 1, 3 mod 2, and 3 mod 0. So that;
Then, we divide them in 4 cases;
Case 1 : Group 2 and Group 3
Then, the possible ways is ( 2 4 ) . ( 2 4 ) = 6 . 6 = 3 6
Case 2 : Group 2 and Group 1
Then, the possible ways is ( 3 4 ) . ( 1 3 ) = 4 . 3 = 1 2
Case 3 : Group 3 and Group 1
Then, the possible ways is ( 3 4 ) . ( 1 3 ) = 4 . 3 = 1 2
Case 4 : Group 1, Group 2, and Group 3
Then, the possible ways is ( 2 3 ) . ( 1 4 ) . ( 1 4 ) = 3 . 4 . 4 = 4 8
So, the total possible ways is 3 6 + 1 2 + 1 2 + 4 8 = 1 0 8
case-1 when all are divisible by 3 (not possible case as only 3 zeroes are there)
case-2 first two are divisible by 3 are third leaves remainder 1 and second leave remaindr 2 i.e (0 0 1 2) case or C(3 2) C(4 1) C(4 1)=48 cases
case 3:- {1,1,1,0} so C(4 3) C(3 1)=12 cases case-4{2,2,2,0} so C(4 3) C(3 1)=12 cases case-5{1,1,2,2} C(4 2)*C(4 2)=36 cases so total cases are 48+12+12+36=108
The sum a 1 + a 2 + a 3 + a 4 ≡ 0 ( m o d 3 ) if ( a 1 m o d 3 + a 2 m o d 3 + a 3 m o d 3 + a 4 m o d 3 ) ≡ 0 ( m o d 3 ) . That leaves us five possibilities:
a i m o d 3 = { 0 , 0 , 0 , 0 } – irrelevant, as there are only three distinct numbers divisible by 3;
a i m o d 3 = { 1 , 2 , 0 , 0 } gives us ( 1 4 ) + ( 1 4 ) + ( 2 3 ) possibilities;
a i m o d 3 = { 1 , 1 , 1 , 0 } gives us ( 3 4 ) + ( 1 3 ) possibilities;
a i m o d 3 = { 2 , 2 , 2 , 0 } gives us ( 3 4 ) + ( 1 3 ) possibilities;
a i m o d 3 = { 2 , 2 , 1 , 1 } gives us ( 2 4 ) + ( 2 4 ) possibilities.
Adding up, we get that the total number of choices is 4 8 + 1 2 + 1 2 + 3 6 = 1 0 8 .
Working Modulo 3 the only possible quadruples are ( 0 , 0 , 0 , 0 ) , ( 0 , 0 , 1 , 2 ) , ( 0 , 1 , 1 , 1 ) , ( 0 , 2 , 2 , 2 ) , ( 1 , 1 , 2 , 2 ) .
Within our set of numbers we have three divisible by 3, four congruent to 1 modulo 3, and four congruent to 2 modulo 3. The number of possibilities is hence:
So we have to take the modulo 3 over the entire set the set is in form
1 , 2 , 0 , 1 , 2 , 0 , 1 , 2 , 0 , 1 , 2
now condition is that sum of four numbers divisible by
3
we can have following cases
case
:-
1
When all are divisible by
3
(
not possible case as only
3
zeroes are there
)
case
:-
2
First two are divisible by
3
are third leaves remainder
1
and second leave remainder
2
i.e
(
0
,
0
,
1
,
2
)
case
or
(
2
3
)
×
(
1
4
)
×
(
1
4
)
=
4
8
cases
case
-
3
:-
1
,
1
,
1
,
0
so
(
3
4
)
×
(
1
3
)
=
1
2
cases
case
:-
4
2
,
2
,
2
,
0
So
(
3
4
)
×
(
1
3
)
=
1
2
cases
case
:-
5
1
,
1
,
2
,
2
(
2
4
)
×
(
2
4
)
=
3
6
cases
So total cases are
4
8
+
1
2
+
1
2
+
3
6
=
1
0
8
[ANSWER]
Taking all the values mod 3, we have four residues of -1, four residues of 1, and three residues of 0.
To get a sum divisible by zero, we need the residue of the four values to yield zero.
There are three different cases:
Two -1 and two 1 residues. This is is just (4C2)(4C2) = 6 * 6 = 36
One -1, one 1, and two 0 residues. This is (4C1)(4C1)(3C2) = 4 * 4 * 3 = 48
Either three -1 or three 1 residues with one 0 residue. This is 2 * (4C3)(3C1) = 2 * 4 * 3 = 24
Adding the three cases together gives 36 + 48 + 24 = 108 .
The numbers can be split into 3 categories: 0 mod 3, 1 mod 3, and 2 mod 3.
There are 3 numbers in the (0 mod 3) group, 4 in (1 mod 3) group, and 4 in (2 mod 3) group. Since we are choosing 4 numbers that sums to a multiple of 3, the mods must add up to a multiple of 3.
Case Sum = 0 mod 3: 0+0+0+0 Which isn't possible since we only have 3 numbers in the 0 mod 3 group.
Case Sum = 3 mod 3
2+1+0+0 There are 4 * 4 * (3c2) = 48 solutions for this.
1+1+1+0 There are (4c3) * 3 = 12 solutions for this.
Case Sum = 6 mod 3
2+2+2+0 There are (4c3) * 4 = 12 solutions for this.
2+2+1+1 There are (4c2) * (4c2) = 36 solutions for this.
We are done since the max mod 3 we can have is 2*4 = 8, and 6 is the highest multiple of 3 below 8. So in total, we have 48+12+12+36 = 108 solutions.
So we have to take the modulo 3 over the entire set and the set is in the form {1,2,0,1,2,0,1,2,0,1,2}
Now the condition is that the sum of four numbers divisible by 3
We can have following cases
Case 1-When all are divisible by 3 (not possible case as only 3 zeroes are there)
Case 2-First two are divisible by 3 are third leaves remainder 1 and second leave remainder 2 i.e (0 0 1 2) case or C(3 2) C(4 1) C(4 1)=48 cases
Case 3- {1,1,1,0}
So C(4 3)*C(3 1)=12 cases
Case4-{2,2,2,0}
So C(4 3)*C(3 1)=12 cases
Case 5-{1,1,2,2}
C(4 2)*C(4 2)=36 cases
So total cases are 48+12+12+36=108
Group the numbers according to their remainder modulo 3 : 0 : { 3 , 6 , 9 } 1 : { 1 , 4 , 7 , 1 0 } 2 : { 2 , 5 , 8 , 1 1 }
There are four possible ways to get a set whose sum has remainder 0 ( m o d 3 ) :
add up 1 2 + 4 8 + 1 2 + 3 6 choices to get 1 0 8 total.
We only care about divisibility by 3, so we mod out by 3 to get the list { 1 , 2 , 0 , 1 , 2 , 0 , 1 , 2 , 0 , 1 , 2 } . That's three 0's, four 1's, and four 2's. In order to get four of these numbers summing to 0 mod 3, we must have two or fewer 0's since we cannot choose all 0's. We break into cases.
Case 1: No 0's: We must have 1 + 1 + 2 + 2 = 0 , so there are ( 2 4 ) ( 2 4 ) = 3 6 like this.
Case 2: One 0: We must have either 1 + 1 + 1 = 0 or 2 + 2 + 2 = 0 , so this contributes ( 1 3 ) ( ( 3 4 ) + ( 3 4 ) ) = 2 4 .
Case 3: Two 0's: We need 1 + 2 = 0 , and hence ( 2 3 ) ( 1 4 ) ( 1 4 ) = 4 8 .
Our grand total is 4 8 + 2 4 + 3 6 = 1 0 8 .
Anybody know how to do this with generating functions?
There are 3 numbers 3k, 4 numbers 3k+1 and 4 numbers 3k+1
There are 4 case for this problem
1) 2 numbers 3k,a number 3k+1 and a number 3k+2
there are 3x4x4=48 ways
2) a number 3k and 3 number 3k+1
there are 3x4=12 ways
3) a number 3k and 3 numbers 3k+2
there are 12 ways
4) 2 numbers 3k+1 and 2 number 3k+2
there 6x6=36
so the total is 108 ways
case-1 when all are divisible by 3 (not possible case as only 3 zeroes are there)
case-2 first two are divisible by 3 are third leaves remainder 1 and second leave remainder 2 i.e (0 0 1 2) case or C(3 2) C(4 1) C(4 1)=48 cases
case 3:- {1,1,1,0} so C(4 3)*C(3 1)=12 cases
case-4{2,2,2,0} so C(4 3)*C(3 1)=12 cases
case-5{1,1,2,2}
C(4 2)*C(4 2)=36 cases
so total cases are 48+12+12+36=108.
If we took this whole entire set ( m o d 3 ) , we would get { 1 , 2 , 0 , 1 , 2 , 0 , 1 , 2 , 0 , 1 , 2 } . We have to find the number of configurations of 1 's, 2 's, and 0 's such that they are divisible by 3 .
Case 1 : { 1 , 1 , 1 , 0 } There are ( 3 4 ) ∗ ( 1 3 ) = 1 2 ways to pick 4 numbers from this set
Case 2 : { 1 , 1 , 2 , 2 } There are ( 2 4 ) ∗ ( 2 4 ) = 3 6 ways to pick 4 numbers from this set
Case 3 : { 1 , 2 , 0 , 0 } There are ( 1 4 ) ∗ ( 1 4 ) ∗ ( 2 3 ) = 4 8 ways to choose 4 numbers from this set
Case 4 : { 2 , 2 , 2 , 0 } Lastly, there are ( 3 4 ) ∗ ( 1 3 ) = 1 2 ways to pick 4 numbers from this set.
These are all of our cases. Adding them up: 1 2 + 1 2 + 3 6 + 4 8 = 1 0 8 total ways.
Describe 3 sets A , B , C as A = { 3 , 6 , 9 } , B = { 1 , 4 , 7 , 1 0 } , C = { 2 , 5 , 8 , 1 1 } .
Let X be the set of 4 distinct elements taken from A , B , C such that the sum of the elements is divisible by 3 . We cannot all the numbers from set A . We can have the following cases:
Case 1:
2 elements are from A and the other 2 are from B and C .[ 1 each from B and C ]
We have ( 2 3 ) = 3 choices for the 2 elements from A and 4 choices for each of the other 2 from B and C .
So total sets in this case is 3 × 1 6 = 4 8 .
Case 2:
1 element is from A and either the rest 3 are from B or C . There are 3 choices for the element chosen from A .
We can choose 3 elements from from B or C in 2 × ( ( 3 4 ) )
Total sets are: 3 × 8 = 2 4
Case 3:
2 elements are from B and the other two from C . We can choose two elements from B in ( 2 4 ) = 6 . Also we can choose from C in ( 2 4 ) = 6 .
Total sets= 6 × 6 = 3 6
Therefore, total number of sets are: 1 0 8
*cannot have
Under mod 3, the set can be written as 1 , 2 , 3 , 1 , 2 , 3 , 1 , 2 , 3 , 1 , 2
Thus, the ways to get a sum that is divisible by 3 are as follows: 1122, 1113, 2223, 1233.
For 1122, there are (4 choose 2) x (4 choose 2) = 36 combinations. For 1113 and 2223, there are (4 choose 3) x (3 choose 1) = 12 combinations each. For 1233, there are (4 choose 1) x (4 choose 1) x (3 choose 2) = 48 combinations. Adding them together we have 108 combinations.
It is required to find four distinct numbers a , b , c , d ∈ [ 1 1 ] such that a + b + c + d ≡ 0 ( m o d 3 ) . Note that ( a + b + c + d ) ≡ a ( m o d 3 ) + b ( m o d 3 ) + c ( m o d 3 ) + d ( m o d 3 ) and that x ( m o d 3 ) is a number in 0 , 1 , 2 . Hence it is enough to find residue classes which will sum up to 0 ( m o d 3 ) . It is easy to verify the following are the only ones possible 0 + 0 + 0 + 0 = 0 1 + 1 + 1 + 0 = 0 2 + 1 + 0 + 0 = 0 2 + 2 + 2 + 0 = 0 2 + 2 + 1 + 1 = 0 2 + 2 + 1 + 1 = 0 In residue class 0 there are only 3 elements ( 3 , 6 , 9 ), hence it is impossible to choose 4 distinct numbers from this class thus rendering the case 0 + 0 + 0 + 0 impossible. The residue classes 2 and 1 have four members each. Hence it is easy to see that every other sum in the above list is possible with distinct numbers. Since we are choosing a set the ordering does not matter and hene it is not needed to consider both 2 + 2 + 2 + 0 and 0 + 2 + 2 + 2 . Hence the total number of possiblities are 0 + ( 3 4 ) ( 1 3 ) + ( 1 4 ) ( 1 4 ) ( 2 3 ) + ( 3 4 ) ( 1 3 ) + ( 2 4 ) ( 2 4 ) which is equal to 108.
Let us categorize all the numbers by 3n, 3n+1, 3n+2 . If the sum of four numbers have to be a multiple of 3, then the possible groupings are (3n, 3n, 3n, 3n), (3n, 3n, 3n+1, 3n+2), (3n+1, 3n+1, 3n+2, 3n+2), (3n+1, 3n+1, 3n+1, 3n) and (3n+2, 3n+2, 3n+2, 3n) .
Cleary, there's 3 numbers in the 3n category, 4 numbers each in the 3n+1 and 3n+2 category, in the set {1,2,3...9,10,11} .
Case 1 (3n, 3n, 3n, 3n) There's only 3 3n 's, so this case is impossible.
Case 2 (3n, 3n, 3n+1, 3n+2) There's 3C2 \times 4C1 \times 4C1 = 48 ways.
Case 3 (3n+1, 3n+1, 3n+2, 3n+2) There's 4C2 \times 4C2 = 36 ways.
Case 4 (3n+1, 3n+1, 3n+1, 3n) There's 4C3 \times 3C1 = 12 ways.
Case 5 (3n+2, 3n+2, 3n+2, 3n) There's 4C3 \times 3C1 = 12 ways.
Hence, it results 48 + 36 + 12 + 12 = 108 ways in total.
Notice that, modulo 3, the set contains 3 elements that are congruent to 0, 4 elements that are congruent to 1 and 4 elements that are congruent to 2.
We consider all possible ways in which four numbers modulo 3 can add up to 0. For each case, we multiply together the number of ways in which we can choose the requisite number of elements from each congruence class.
The total number of ways is thus 4 8 + 1 2 + 1 2 + 3 6 = 1 0 8
Any number can be expressed as:
3 n or 3 n + 1 or 3 n + 2 where n is any whole number.
From the given set, the numbers of type 3 n are 3 , 6 , 9
numbers of type 3 n + 1 are 1 , 4 , 7 , 1 0
and numbers of type 3 n + 2 are 2 , 5 , 8 , 1 1
Now there are 5 possible cases:
Case 1: all 4 selected numbers are of form 3 n .
This case is not possible as we have only 3 elements in type 1 .
Case 2: 2 numbers are of type 3 n ; 1 number is of type 3 n + 1 and 1 number is of type 3 n + 2
Therefore number of ways of selecting 4 numbers in this case are:
( 2 3 ) × ( 1 4 ) × ( 1 4 ) = 4 8
Case 3: 1 number of type 3 n and 3 if type 3 n + 1
Number of ways of selecting = ( 1 3 ) × ( 3 4 ) = 1 2
Case 4 : 1number of type 3 n and 3 of type 3 n + 2
Number of ways of selecting = ( 1 3 ) × ( 3 4 ) = 1 2
Case 5 : 2 numbers of kind 3 n + 1 and 2 numbers of kind 3 n + 2
Number of ways of selecting = ( 2 4 ) × ( 2 4 ) = 3 6
Therefore total number of ways of selection are: 4 8 + 1 2 + 1 2 + 3 6 = 1 0 8
Consider the modulo when the numbers are divided by 3:
3 numbers are divisible by 3
4 numbers leave remainder 1 when divided by 3
4 numbers leave remainder 2 when divided by 3
Now for the sum of 4 numbers to be divisible by 3, there are 5 cases:
Case 1: all are divisible by 3 - not possible here
Case 2: two are divisible by 3, one leaves remainder 1 and one leaves remainder 2: 3 C 2 × 4 C 1 × 4 C 1 = 4 8 cases
Case 3: one divisible by 3 and three leave remainder 1: 3 C 1 × 4 C 3 = 1 2 cases
Case 4: one divisible by 3 and three leave remainder 2: 3 C 1 × 4 C 1 = 1 2 cases
Case 5: two leave remainder 1 and two leave remainder 2: 4 C 2 × 4 C 2 = 3 6 cases
Total number = 48 + 12 + 12 + 36 = 108 cases
Consider the numbers modulo 3 . Arrange them as: 3 , 6 , 9 ≡ 0 ; 1 , 4 , 7 , 1 0 ≡ 1 & 2 , 5 , 8 , 1 1 ≡ 2 ( m o d 3 ) .
Combinations ( m o d 3 ) whose sums are divisible by 3, are { 1 , 1 , 1 , 0 }, { 2 , 1 , 0 , 0 }, { 2 , 2 , 2 , 0 } & { 2 , 2 , 1 , 1 } (irrespective of order). Now consider case-by-case & counting as per choices available, we have number of ways = ( 3 4 ) ∗ 3 + 4 ∗ 4 ∗ ( 2 3 ) + ( 3 4 ) ∗ 3 + ( 2 4 ) ∗ ( 2 4 ) = 108 .
We first count the number of 1 ≤ n ≤ 1 1 with the same remainders upon dividing by 3 . We have # { n : n ≡ 0 ( m o d 3 ) } = # { 3 , 6 , 9 } = 3 , # { n : n ≡ 1 ( m o d 3 ) } = # { 1 , 4 , 7 , 1 0 } = 3 , # { n : n ≡ 2 ( m o d 3 ) } = # { 2 , 5 , 8 , 1 1 } = 4 . All possible cases with the corresponding number of ways for each case to have the sum of 4 numbers divisible by 3 are as follows:
Case 1: 3 numbers have remainders equal to 1 and the other number has remainder equal to 0 . The number of ways is ( 3 4 ) ( 1 3 ) = 4 × 3 = 1 2 .
Case 2: 2 numbers have remainders equal to 1 and the other number has remainder equal to 2 . The number of ways is ( 2 4 ) ( 2 4 ) = 6 × 6 = 3 6 .
Case 3: 1 number has remainder equal to 1 , one number has remainder equal to 2 , and the other two numbers have remainders equal to 0 . The number of ways is ( 1 4 ) ( 1 4 ) ( 2 3 ) = 4 × 4 × 3 = 4 8 .
Case 4: 3 numbers have remainders equal to 2 and the other number has remainder equal to 0 . The number of ways is ( 3 4 ) ( 1 3 ) = 4 × 3 = 1 2 .
Hence, the required total number of ways is 1 2 + 3 6 + 4 8 + 1 2 = 1 0 8 .
There is a misprint of the cardinality of the set { n : n ≡ 1 ( m o d 3 ) } . It should be 4 instead of 3 .
First sort the set into three groups, those with remainder 0 , 1 , and 2 . Now, we have 3 numbers with remainder 0 , 4 with remainder 1 , and 4 with remainder 2 . Call any number belonging to each group 0 , 1 , 2 respectively.
Next, figure out the ways you can arrange these groups based on the fact that the remainders must add up to a multiple of 3 . There should be 4 cases:
Case 1:
Two remainders
1
and Two remainders
2
There are
6
ways to choose
2
numbers from the set of remainders
1
, and likewise there are
6
ways to choose
2
numbers from the set of remainders
2
. So, there are
3
6
ways with this combination.
Case 2: Two remainders 0 One remainder 1 One remainder 2
3 C 2 × 4 C 1 × 4 C 1 = 3 × 4 × 4 = 4 8
Case 3: Three remainders 2 One remainder 0
4 C 3 × 3 C 1 = 4 × 3 = 1 2
Case 4: Three remainder 1 One remainder 0
4 C 3 × 3 C 1 = 4 × 3 = 1 2
Adding these 4 cases up, we get 3 6 + 4 8 + 1 2 + 1 2 = 1 0 8
Consider ( m o d 3 ) . We have that 3 numbers are 0 ( m o d 3 ) , and 4 numbers are each 1 , 2 ( m o d 3 ) (so 4 numbers are 1 mod 3 and 4 numbers are 2 mod 3). There are 4 cases of having a sum of 0 ( m o d 3 ) with these restrictions: 1110, 2220, 2100, and 2121. We compute the number of ways for each case separately.
For 1110, there are ( 3 4 ) ⋅ ( 1 3 ) = 1 2 ways to choose the numbers.
For 2220, there are, similarly, ( 3 4 ) ⋅ ( 1 3 ) = 1 2 ways.
For 2100, there are ( 1 4 ) ⋅ ( 1 4 ) ⋅ ( 2 3 ) = 4 8 ways.
For 2121, there are ( 2 4 ) ⋅ ( 2 4 ) = 3 6 ways.
In total, there are 1 2 + 1 2 + 4 8 + 3 6 = 1 0 8 ways possible.
Problem Loading...
Note Loading...
Set Loading...
We can solve this by casework on the set of numbers modulo 3. Of the set, there are 3 that are 0 ( m o d 3 ) , and 4 each of 1 ( m o d 3 ) and 2 ( m o d 3 ) .
Case 1: None of the numbers are 0 ( m o d 3 )
There is only one set modulo three that works: ( 1 , 1 , 2 , 2 ) . The number of possibilities in this case is ( 2 4 ) ⋅ ( 2 4 ) = 3 6 .
Case 2: One of the numbers are 0 ( m o d 3 )
There are two sets modulo three that work: ( 0 , 1 , 1 , 1 ) and ( 0 , 2 , 2 , 2 ) . The number of possibilities in each set is ( 1 3 ) ⋅ ( 3 4 ) = 1 2 , so there are 2 4 possibilities in this case.
Case 3: Two of the numbers are 0 ( m o d 3 )
There is only one set modulo three that works: ( 0 , 0 , 1 , 2 ) . The number of possibilities in this case is ( 2 3 ) ⋅ ( 1 4 ) ⋅ ( 1 4 ) = 4 8 .
Since there are no sets having all numbers divisible by 3, the answer is 3 6 + 2 4 + 4 8 = 1 0 8 .