Choosing a Divisibile Sum

A set of four distinct numbers are chosen from the set { 1 , 2 , 3 9 , 10 , 11 } \{1,2,3 \ldots 9, 10, 11\} . How many ways can this set of 4 4 numbers be chosen such that the sum is divisible by 3 3 ?

Details and assumptions

Choosing the numbers { 1 , 2 , 3 , 6 } \{ 1, 2, 3, 6 \} is the same as choosing the numbers { 6 , 3 , 2 , 1 } \{ 6, 3, 2, 1 \} .


The answer is 108.

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.

31 solutions

Daniel Chiu
Jul 28, 2013

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 ) 0\pmod 3 , and 4 each of 1 ( m o d 3 ) 1\pmod 3 and 2 ( m o d 3 ) 2\pmod 3 .

Case 1: None of the numbers are 0 ( m o d 3 ) 0\pmod 3

There is only one set modulo three that works: ( 1 , 1 , 2 , 2 ) (1,1,2,2) . The number of possibilities in this case is ( 4 2 ) ( 4 2 ) = 36 \dbinom{4}{2}\cdot\dbinom{4}{2}=36 .

Case 2: One of the numbers are 0 ( m o d 3 ) 0\pmod 3

There are two sets modulo three that work: ( 0 , 1 , 1 , 1 ) (0,1,1,1) and ( 0 , 2 , 2 , 2 ) (0,2,2,2) . The number of possibilities in each set is ( 3 1 ) ( 4 3 ) = 12 \dbinom{3}{1}\cdot\dbinom{4}{3}=12 , so there are 24 24 possibilities in this case.

Case 3: Two of the numbers are 0 ( m o d 3 ) 0\pmod 3

There is only one set modulo three that works: ( 0 , 0 , 1 , 2 ) (0,0,1,2) . The number of possibilities in this case is ( 3 2 ) ( 4 1 ) ( 4 1 ) = 48 \dbinom{3}{2}\cdot\dbinom{4}{1}\cdot\dbinom{4}{1}=48 .

Since there are no sets having all numbers divisible by 3, the answer is 36 + 24 + 48 = 108 36+24+48=\boxed{108} .

Simple and the best solution.

Piyal De - 7 years, 10 months ago
Joshua Cortez
Jul 30, 2013

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.

  1. Each number picked from B should have a corresponding number picked from C. (or vice versa)
  2. One should pick 3 numbers from B or pick 3 numbers from C.

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.

  1. Pick 3 from B and 1 from A
  2. Pick 3 from C and 1 from A
  3. Pick 2 from B and 2 from C
  4. Pick 1 from B, 1 from C, and 2 from A

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.

  1. (4 choose 3)(3) or 12 ways
  2. (4 choose 3)(3) or 12 ways
  3. (4 choose 2)(4 choose 2) or 36 ways
  4. (4)(4)(3 choose 2) or 48 ways

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?

Nadira Nanda Wij - 7 years, 10 months ago

Log in to reply

Thank you! :) Yeah, I felt more comfortable explaining it in a more organic way.

Joshua Cortez - 7 years, 10 months ago
Christopher Boo
Jul 28, 2013

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 , 10 } = 4 S_1=\{1,4,7,10\}=4

The second category is the numbers which left remainder 2 when divide by 3.

S 2 = { 2 , 5 , 8 , 11 } = 4 S_2=\{2,5,8,11\}=4

The third category is the numbers which is divisible by 3

S 3 = { 3 , 6 , 9 } = 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 S_1+S_1+S_1+S_3 .

The numbers of ways to do this are ( 4 3 ) × 3 = 12 {4\choose3}\times3=12

The second combination of the categories which sum is divisible by 3 is S 2 + S 2 + S 2 + S 3 S_2+S_2+S_2+S_3 .

The numbers of ways to do this are ( 4 3 ) × 3 = 12 {4\choose3}\times3=12

The third combination of the categories which sum is divisible by 3 is S 1 + S 1 + S 2 + S 2 S_1+S_1+S_2+S_2 .

The numbers of ways to do this are ( 4 2 ) × ( 4 2 ) = 36 {4\choose2}\times{4\choose2}=36

The forth combination of the categories which sum is divisible by 3 is S 1 + S 2 + S 3 + S 3 S_1+S_2+S_3+S_3 .

The numbers of ways to do this are 4 × 4 × ( 3 2 ) = 48 4\times4\times{3\choose2}=48

\therefore The total number of ways can the set of 4 numbers be chosen such that the sum is divisible by 3 is 12 + 12 + 36 + 48 = 108 12+12+36+48=108 .

Ahaan Rungta
Jul 28, 2013

We consider the set modulo 3 3 : { 1 , 2 , 0 , , 0 , 1 , 2 } . \{ 1, 2, 0, \cdots, 0, 1, 2 \}. Due to a sort of weird non-symmetry, it'll probably be best to consider cases mod 3 3 . We want the sum of the elements, mod 3 3 to be exactly 0 0 . We can several cases, in terms of what the elements can be, mod 3 3 . Ordering does not matter.

Case 1 : 0 , 0 , 0 , 0 0, 0, 0, 0

There are only three 0 0 s in the original set, so we cannot choose 4 4 of them. Thus, there are 0 0 ways we can satisfy this case.

Case 2 : 1 , 1 , 1 , 0 1, 1, 1, 0

We must choose three 1 1 s out of the 4 4 of them and one 0 0 out of the 3 3 of them. There are ( 4 3 ) ( 3 1 ) = 4 3 = 12 \dbinom {4}{3} \cdot \dbinom {3}{1} = 4 \cdot 3 = 12 ways to satisfy this case.

Case 3 : 2 , 2 , 2 , 0 2, 2, 2, 0

We must choose three 2 2 s out of the 4 4 of them and one 0 0 out of the 3 3 of them. Just as in Case 2, we have 12 12 ways to satisfy this case.

Case 4 : 1 , 1 , 2 , 2 1, 1, 2, 2

We must choose two 2 2 s out of the 4 4 of them and two 1 1 s out of the 4 4 of them. We have ( 4 2 ) ( 4 2 ) = 6 6 = 36 \dbinom {4}{2} \cdot \dbinom {4}{2} = 6 \cdot 6 = 36 ways to satisfy this case.

Case 5 : 0 , 0 , 1 , 2 0, 0, 1, 2

We must choose two 0 0 s out of the 3 3 of them, one 1 1 out of the 4 4 of them and one 2 2 out of the 4 4 of them. There are ( 3 2 ) ( 4 1 ) ( 4 1 ) = 3 4 4 = 48 \dbinom {3}{2} \cdot \dbinom {4}{1} \cdot \dbinom {4}{1} = 3 \cdot 4 \cdot 4 = 48 ways to satisfy this case.

Altogether : We have 0 + 12 + 12 + 36 + 48 = 108 0 + 12 + 12 + 36 + 48 = \boxed {108} ways in total.

\blacksquare

Leandre Noel Kiu
Jul 29, 2013

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 //

Matt Wang
Jul 28, 2013

We can split up the set with mods, 1 , 4 , 7 , 10 1 ( mod 3 ) 1, 4, 7, 10 \equiv 1\ (\textrm{mod}\ 3) being one subset, 2 , 5 , 8 , 11 2 ( mod 3 ) 2, 5, 8, 11 \equiv 2\ (\textrm{mod}\ 3) being another, and 3 , 6 , 9 0 ( mod 3 ) 3, 6, 9 \equiv 0\ (\textrm{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 ) , (1, 1, 1, 0), (1, 1, 2, 2), (1, 2, 0, 0), and ( 2 , 2 , 2 , 0 ) (2, 2, 2, 0) . Notice that ( 0 , 0 , 0 , 0 ) (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 4C3 \times 3C1 ) cases for the ( 1 , 1 , 1 , 3 ) (1, 1, 1, 3) and ( 2 , 2 , 2 , 3 ) (2, 2, 2, 3) subsets, 36 ( 4 C 2 × 4 C 2 4C2 \times 4C2 ) cases for the ( 1 , 1 , 2 , 2 ) (1, 1, 2, 2) subset, and 48 ( 4 C 1 × 4 C 1 × 4 C 2 4C1 \times 4C1 \times 4C2 ) cases for the ( 1 , 2 , 3 , 3 ) (1, 2, 3, 3) subset. Thus, there are 12 + 12 + 36 + 48 = 108 12+12+36+48 = \boxed{108} ways.

Anindya Sharma
Aug 3, 2013

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! )

Dani Natanael
Aug 3, 2013

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;

  • 3 mod 0 = 3, 6, 9 ----- > become Group A
  • 3 mod 1 = 1,4,7,10 ----> become Group B
  • 3 mod 2 = 2,5,8,11 ----> become Group C

Then, we divide them in 4 cases;

Case 1 : Group 2 and Group 3

Then, the possible ways is ( 4 2 ) . ( 4 2 ) = 6.6 = 36 \binom{4}{2}.\binom{4}{2}=6.6=36

Case 2 : Group 2 and Group 1

Then, the possible ways is ( 4 3 ) . ( 3 1 ) = 4.3 = 12 \binom{4}{3}.\binom{3}{1}=4.3=12

Case 3 : Group 3 and Group 1

Then, the possible ways is ( 4 3 ) . ( 3 1 ) = 4.3 = 12 \binom{4}{3}.\binom{3}{1}=4.3=12

Case 4 : Group 1, Group 2, and Group 3

Then, the possible ways is ( 3 2 ) . ( 4 1 ) . ( 4 1 ) = 3.4.4 = 48 \binom{3}{2}.\binom{4}{1}.\binom{4}{1}=3.4.4=48

So, the total possible ways is 36 + 12 + 12 + 48 = 108 36+12+12+48=108

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 ) a_1+a_2+a_3+a_4\equiv 0\pmod{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 ) (a_1\,\mathrm{mod}\,3+a_2\,\mathrm{mod}\,3+a_3\,\mathrm{mod}\,3+a_4\,\mathrm{mod}\,3)\equiv 0\pmod{3} . That leaves us five possibilities:

a i m o d 3 = { 0 , 0 , 0 , 0 } a_i\,\mathrm{mod}\,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 } a_i\,\mathrm{mod}\,3=\{1,2,0,0\} gives us ( 4 1 ) + ( 4 1 ) + ( 3 2 ) \binom{4}{1}+\binom{4}{1}+\binom{3}{2} possibilities;

a i m o d 3 = { 1 , 1 , 1 , 0 } a_i\,\mathrm{mod}\,3=\{1,1,1,0\} gives us ( 4 3 ) + ( 3 1 ) \binom{4}{3}+\binom{3}{1} possibilities;

a i m o d 3 = { 2 , 2 , 2 , 0 } a_i\,\mathrm{mod}\,3=\{2,2,2,0\} gives us ( 4 3 ) + ( 3 1 ) \binom{4}{3}+\binom{3}{1} possibilities;

a i m o d 3 = { 2 , 2 , 1 , 1 } a_i\,\mathrm{mod}\,3=\{2,2,1,1\} gives us ( 4 2 ) + ( 4 2 ) \binom{4}{2}+\binom{4}{2} possibilities.

Adding up, we get that the total number of choices is 48 + 12 + 12 + 36 = 108 48+12+12+36=108 .

David Vaccaro
Jul 31, 2013

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 ) (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:

  • C 4 3 + C 2 3 C 1 4 C 1 4 + 2 C 3 4 C 1 3 + C 2 4 C 2 4 = 108 C_{4}^{3}+C_{2}^{3}C_{1}^{4}C_{1}^{4}+2C_{3}^{4}C_{1}^{3}+C_{2}^{4}C_{2}^{4}=108
Debjit Mandal
Jul 31, 2013

So we have to take the modulo 3 3 over the entire set the set is in form

1 , 2 , 0 , 1 , 2 , 0 , 1 , 2 , 0 , 1 , 2 {1,2,0,1,2,0,1,2,0,1,2}

now condition is that sum of four numbers divisible by 3 3
we can have following cases
case :- 1 1
When all are divisible by 3 3 ( not possible case as only 3 3 zeroes are there )


case :- 2 2
First two are divisible by 3 3 are third leaves remainder 1 1 and second leave remainder 2 2 i.e ( 0 , 0 , 1 , 2 ) (0, 0, 1, 2) case or ( 3 2 ) {3 \choose 2} × \times ( 4 1 ) {4 \choose 1} × \times ( 4 1 ) {4 \choose 1} = = 48 48 cases

case - 3 3 :-
1 , 1 , 1 , 0 {1,1,1,0}
so ( 4 3 ) {4 \choose 3} × \times ( 3 1 ) {3 \choose 1} = = 12 12 cases
case :- 4 4
2 , 2 , 2 , 0 {2,2,2,0}
So ( 4 3 ) {4 \choose 3} × \times ( 3 1 ) {3 \choose 1} = = 12 12 cases
case :- 5 5
1 , 1 , 2 , 2 {1,1,2,2}






( 4 2 ) {4 \choose 2} × \times ( 4 2 ) {4 \choose 2} = = 36 36 cases
So total cases are 48 + 12 + 12 + 36 = 108 48+12+12+36=108 [ANSWER]

Albert Ho
Jul 30, 2013

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:

  1. Two -1 and two 1 residues. This is is just (4C2)(4C2) = 6 * 6 = 36

  2. One -1, one 1, and two 0 residues. This is (4C1)(4C1)(3C2) = 4 * 4 * 3 = 48

  3. 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 .

Jiaqi Wang
Jul 30, 2013

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.

Evan Chien
Jul 30, 2013

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 3 : 0 : { 3 , 6 , 9 } 1 : { 1 , 4 , 7 , 10 } 2 : { 2 , 5 , 8 , 11 } 0:\{3,6,9\}\\ 1:\{1,4,7,10\}\\ 2:\{2,5,8,11\}

There are four possible ways to get a set whose sum has remainder 0 ( m o d 3 ) 0 \pmod 3 :

  1. take 1 from "0", three from "1" (that is, take 1 "0" and 3 "1's")
  2. 2 "0"s, 1 "1", 1 "2"
  3. 1 "0", 3 "2"s
  4. 2 "1"s, 2 "2"s.

add up 12 + 48 + 12 + 36 12 + 48 + 12 + 36 choices to get 108 108 total.

Eric Edwards
Jul 30, 2013

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 } \{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 1+1+2+2 = 0 , so there are ( 4 2 ) ( 4 2 ) = 36 \binom{4}{2}\binom{4}{2} = 36 like this.

Case 2: One 0: We must have either 1 + 1 + 1 = 0 1+1+1=0 or 2 + 2 + 2 = 0 2+2+2=0 , so this contributes ( 3 1 ) ( ( 4 3 ) + ( 4 3 ) ) = 24 \binom{3}{1}(\binom{4}{3} + \binom{4}{3}) = 24 .

Case 3: Two 0's: We need 1 + 2 = 0 1+2=0 , and hence ( 3 2 ) ( 4 1 ) ( 4 1 ) = 48 \binom{3}{2}\binom{4}{1}\binom{4}{1} = 48 .

Our grand total is 48 + 24 + 36 = 108 48+24+36 = 108 .

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

Vikash Kumar
Jul 30, 2013

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.

Harrison Lian
Jul 30, 2013

If we took this whole entire set ( m o d 3 ) \pmod 3 , we would get { 1 , 2 , 0 , 1 , 2 , 0 , 1 , 2 , 0 , 1 , 2 } \{1,2,0,1,2,0,1,2,0,1,2\} . We have to find the number of configurations of 1 1 's, 2 2 's, and 0 0 's such that they are divisible by 3 3 .

Case 1 : { 1 , 1 , 1 , 0 } \{1,1,1,0\} There are ( 4 3 ) ( 3 1 ) = 12 \binom{4}{3}*\binom{3}{1}=12 ways to pick 4 numbers from this set

Case 2 : { 1 , 1 , 2 , 2 } \{1,1,2,2\} There are ( 4 2 ) ( 4 2 ) = 36 \binom{4}{2}*\binom{4}{2}=36 ways to pick 4 numbers from this set

Case 3 : { 1 , 2 , 0 , 0 } \{1,2,0,0\} There are ( 4 1 ) ( 4 1 ) ( 3 2 ) = 48 \binom{4}{1}*\binom{4}{1}*\binom{3}{2}=48 ways to choose 4 numbers from this set

Case 4 : { 2 , 2 , 2 , 0 } \{2,2,2,0\} Lastly, there are ( 4 3 ) ( 3 1 ) = 12 \binom{4}{3}*\binom{3}{1}=12 ways to pick 4 numbers from this set.

These are all of our cases. Adding them up: 12 + 12 + 36 + 48 = 108 12+12+36+48=\boxed{108} total ways.

Aditya Parson
Jul 30, 2013

Describe 3 sets A , B , C A,B,C as A = { 3 , 6 , 9 } , B = { 1 , 4 , 7 , 10 } , C = { 2 , 5 , 8 , 11 } A= \{ 3,6,9 \} , B= \{ 1,4,7,10 \} , C= \{ 2,5,8,11 \} .

Let X X be the set of 4 4 distinct elements taken from A , B , C A,B,C such that the sum of the elements is divisible by 3 3 . We cannot all the numbers from set A A . We can have the following cases:

Case 1:

2 2 elements are from A A and the other 2 2 are from B B and C C .[ 1 1 each from B B and C C ]

We have ( 3 2 ) = 3 {{3}\choose{2}}=3 choices for the 2 elements from A A and 4 4 choices for each of the other 2 2 from B B and C C .

So total sets in this case is 3 × 16 = 48 3 \times 16=48 .

Case 2:

1 1 element is from A A and either the rest 3 3 are from B B or C C . There are 3 3 choices for the element chosen from A A .

We can choose 3 3 elements from from B B or C C in 2 × ( ( 4 3 ) ) 2 \times ({{4}\choose{3}})

Total sets are: 3 × 8 = 24 3 \times 8 = 24

Case 3:

2 2 elements are from B B and the other two from C C . We can choose two elements from B B in ( 4 2 ) = 6 {{4}\choose{2}}=6 . Also we can choose from C C in ( 4 2 ) = 6 {{4}\choose{2}}=6 .

Total sets= 6 × 6 = 36 6 \times 6=36

Therefore, total number of sets are: 108 \boxed{108}

*cannot have

Aditya Parson - 7 years, 10 months ago
Michael Tong
Jul 30, 2013

Under mod 3, the set can be written as 1 , 2 , 3 , 1 , 2 , 3 , 1 , 2 , 3 , 1 , 2 {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.

Sajin Koroth
Jul 29, 2013

It is required to find four distinct numbers a , b , c , d [ 11 ] a,b,c,d \in [11] such that a + b + c + d 0 ( m o d 3 ) a+b+c+d \equiv 0 \pmod 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 ) (a+b+c+d) \equiv a \pmod 3 + b \pmod 3 + c \pmod 3 + d \pmod 3 and that x ( m o d 3 ) x \pmod 3 is a number in 0 , 1 , 2 0,1,2 . Hence it is enough to find residue classes which will sum up to 0 ( m o d 3 ) 0 \pmod 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 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 0 there are only 3 elements ( 3 , 6 , 9 3,6,9 ), hence it is impossible to choose 4 4 distinct numbers from this class thus rendering the case 0 + 0 + 0 + 0 0+0+0+0 impossible. The residue classes 2 2 and 1 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 2+2+2+0 and 0 + 2 + 2 + 2 0+2+2+2 . Hence the total number of possiblities are 0 + ( 4 3 ) ( 3 1 ) + ( 4 1 ) ( 4 1 ) ( 3 2 ) + ( 4 3 ) ( 3 1 ) + ( 4 2 ) ( 4 2 ) 0 + \binom{4}{3}\binom{3}{1}+ \binom{4}{1}\binom{4}{1}\binom{3}{2}+ \binom{4}{3}\binom{3}{1}+ \binom{4}{2}\binom{4}{2} which is equal to 108.

Tan Yee Jian
Jul 29, 2013

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.

Thomas Beuman
Jul 29, 2013

Notice that, modulo 3, the set contains 3 3 elements that are congruent to 0, 4 4 elements that are congruent to 1 and 4 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.

  • 0 = 4 0 + 0 1 + 0 2 N = 0 0 = 4\cdot0 + 0\cdot1 + 0\cdot2 \qquad N = 0 (we have only three zeros)
  • 0 = 2 0 + 1 1 + 1 2 N = ( 3 2 ) ( 4 1 ) ( 4 1 ) = 48 0 = 2\cdot0 + 1\cdot1 + 1\cdot2 \qquad N = \binom32 \cdot \binom41 \cdot \binom41 = 48
  • 0 = 1 0 + 3 1 + 0 2 N = ( 3 1 ) ( 4 3 ) ( 4 0 ) = 12 0 = 1\cdot0 + 3\cdot1 + 0\cdot2 \qquad N = \binom31 \cdot \binom43 \cdot \binom40 = 12
  • 0 = 1 0 + 0 1 + 3 2 N = ( 3 1 ) ( 4 0 ) ( 4 3 ) = 12 0 = 1\cdot0 + 0\cdot1 + 3\cdot2 \qquad N = \binom31 \cdot \binom40 \cdot \binom43 = 12
  • 0 = 0 0 + 2 1 + 2 2 N = ( 3 0 ) ( 4 2 ) ( 4 2 ) = 36 0 = 0\cdot0 + 2\cdot1 + 2\cdot2 \qquad N = \binom30 \cdot \binom42 \cdot \binom42 = 36

The total number of ways is thus 48 + 12 + 12 + 36 = 108 48+12+12+36 = \boxed{108}

Chinmmayya Hajare
Jul 29, 2013

Any number can be expressed as:

3 n 3n or 3 n + 1 3n+1 or 3 n + 2 3n+2 where n n is any whole number.

From the given set, the numbers of type 3 n 3n are 3 , 6 , 9 {3,6,9}

numbers of type 3 n + 1 3n+1 are 1 , 4 , 7 , 10 1,4,7,10

and numbers of type 3 n + 2 3n+2 are 2 , 5 , 8 , 11 2,5,8,11

Now there are 5 5 possible cases:

Case 1: all 4 selected numbers are of form 3 n 3n .

This case is not possible as we have only 3 elements in type 1 .

Case 2: 2 numbers are of type 3 n 3n ; 1 number is of type 3 n + 1 3n+1 and 1 number is of type 3 n + 2 3n+2

Therefore number of ways of selecting 4 numbers in this case are:

( 3 2 ) × ( 4 1 ) × ( 4 1 ) = 48 \binom{3}{2} \times \binom{4}{1} \times \binom{4}{1} = 48

Case 3: 1 number of type 3 n 3n and 3 if type 3 n + 1 3n+1

Number of ways of selecting = ( 3 1 ) × ( 4 3 ) = 12 \binom{3}{1} \times \binom{4}{3} = 12

Case 4 : 1number of type 3 n 3n and 3 of type 3 n + 2 3n+2

Number of ways of selecting = ( 3 1 ) × ( 4 3 ) = 12 \binom{3}{1} \times \binom{4}{3} = 12

Case 5 : 2 numbers of kind 3 n + 1 3n+1 and 2 numbers of kind 3 n + 2 3n+2

Number of ways of selecting = ( 4 2 ) × ( 4 2 ) = 36 \binom{4}{2} \times \binom{4}{2} = 36

Therefore total number of ways of selection are: 48 + 12 + 12 + 36 = 108 48 + 12 + 12 + 36 = 108

Nhat Le
Jul 29, 2013

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 = 48 3C2 \times 4C1 \times 4C1 = 48 cases

Case 3: one divisible by 3 and three leave remainder 1: 3 C 1 × 4 C 3 = 12 3C1 \times 4C3 = 12 cases

Case 4: one divisible by 3 and three leave remainder 2: 3 C 1 × 4 C 1 = 12 3C1 \times 4C1 = 12 cases

Case 5: two leave remainder 1 and two leave remainder 2: 4 C 2 × 4 C 2 = 36 4C2 \times 4C2 = 36 cases

Total number = 48 + 12 + 12 + 36 = 108 cases

Consider the numbers modulo 3 3 . Arrange them as: 3 , 6 , 9 0 3,6,9 \equiv 0 ; 1 , 4 , 7 , 10 1 1,4,7,10 \equiv 1 & 2 , 5 , 8 , 11 2 ( m o d 3 ) 2,5,8,11 \equiv 2 \pmod{3} .

Combinations ( m o d 3 ) \pmod{3} whose sums are divisible by 3, are { 1 , 1 , 1 , 0 1,1,1,0 }, { 2 , 1 , 0 , 0 2,1,0,0 }, { 2 , 2 , 2 , 0 2,2,2,0 } & { 2 , 2 , 1 , 1 2,2,1,1 } (irrespective of order). Now consider case-by-case & counting as per choices available, we have number of ways = ( 4 3 ) 3 + 4 4 ( 3 2 ) + ( 4 3 ) 3 + ( 4 2 ) ( 4 2 ) = = {4 \choose 3}*3 + 4*4*{3 \choose 2} + {4 \choose 3}*3 + {4 \choose 2}*{4 \choose 2} = 108 .

We first count the number of 1 n 11 1\le n\le 11 with the same remainders upon dividing by 3 3 . We have # { n : n 0 ( m o d 3 ) } = # { 3 , 6 , 9 } = 3 , \#\{n: n\equiv 0 \pmod 3\} = \#\{3,6,9\}=3, # { n : n 1 ( m o d 3 ) } = # { 1 , 4 , 7 , 10 } = 3 , \#\{n: n\equiv 1 \pmod 3\} = \#\{1,4,7,10\}=3, # { n : n 2 ( m o d 3 ) } = # { 2 , 5 , 8 , 11 } = 4. \#\{n: n\equiv 2 \pmod 3\} = \#\{2,5,8,11\}=4. All possible cases with the corresponding number of ways for each case to have the sum of 4 4 numbers divisible by 3 3 are as follows:

Case 1: \textbf{Case 1:} 3 3 numbers have remainders equal to 1 1 and the other number has remainder equal to 0. 0. The number of ways is ( 4 3 ) ( 3 1 ) = 4 × 3 = 12. {4 \choose 3}{3 \choose 1} = 4 \times 3 = 12.

Case 2: \textbf{Case 2:} 2 2 numbers have remainders equal to 1 1 and the other number has remainder equal to 2. 2. The number of ways is ( 4 2 ) ( 4 2 ) = 6 × 6 = 36. {4 \choose 2}{4 \choose 2} = 6 \times 6 = 36.

Case 3: \textbf{Case 3:} 1 1 number has remainder equal to 1 , 1, one number has remainder equal to 2 , 2, and the other two numbers have remainders equal to 0. 0. The number of ways is ( 4 1 ) ( 4 1 ) ( 3 2 ) = 4 × 4 × 3 = 48. {4 \choose 1}{4 \choose 1}{3 \choose 2} = 4 \times 4 \times 3 = 48.

Case 4: \textbf{Case 4:} 3 3 numbers have remainders equal to 2 2 and the other number has remainder equal to 0 0 . The number of ways is ( 4 3 ) ( 3 1 ) = 4 × 3 = 12. {4 \choose 3}{3 \choose 1} = 4 \times 3 = 12.

Hence, the required total number of ways is 12 + 36 + 48 + 12 = 108 . 12 + 36 + 48 + 12 = \boxed{108}.

There is a misprint of the cardinality of the set { n : n 1 ( m o d 3 ) } . \{n : n \equiv 1 \pmod 3\}. It should be 4 4 instead of 3 3 .

Aram Tangboonduangjit - 7 years, 10 months ago
Benson Li
Jul 28, 2013

First sort the set into three groups, those with remainder 0 0 , 1 1 , and 2 2 . Now, we have 3 3 numbers with remainder 0 0 , 4 4 with remainder 1 1 , and 4 4 with remainder 2 2 . Call any number belonging to each group 0 , 1 , 2 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 3 . There should be 4 cases:

Case 1: Two remainders 1 1 and Two remainders 2 2
There are 6 6 ways to choose 2 2 numbers from the set of remainders 1 1 , and likewise there are 6 6 ways to choose 2 2 numbers from the set of remainders 2 2 . So, there are 36 36 ways with this combination.

Case 2: Two remainders 0 0 One remainder 1 1 One remainder 2 2

3 C 2 × 4 C 1 × 4 C 1 = 3 × 4 × 4 = 48 3C2 \times 4C1 \times 4C1=3 \times 4 \times 4= 48

Case 3: Three remainders 2 2 One remainder 0 0

4 C 3 × 3 C 1 = 4 × 3 = 12 4C3 \times 3C1= 4 \times 3= 12

Case 4: Three remainder 1 1 One remainder 0 0

4 C 3 × 3 C 1 = 4 × 3 = 12 4C3 \times 3C1=4 \times 3=12

Adding these 4 cases up, we get 36 + 48 + 12 + 12 = 108 36+48+12+12=108

Daniel Liu
Jul 28, 2013

Consider ( m o d 3 ) \pmod{3} . We have that 3 3 numbers are 0 ( m o d 3 ) 0\pmod{3} , and 4 4 numbers are each 1 , 2 ( m o d 3 ) 1,2\pmod{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 ) 0\pmod{3} with these restrictions: 1110, 2220, 2100, and 2121. We compute the number of ways for each case separately.

For 1110, there are ( 4 3 ) ( 3 1 ) = 12 \binom{4}{3}\cdot\binom{3}{1}=12 ways to choose the numbers.

For 2220, there are, similarly, ( 4 3 ) ( 3 1 ) = 12 \binom{4}{3}\cdot\binom{3}{1}=12 ways.

For 2100, there are ( 4 1 ) ( 4 1 ) ( 3 2 ) = 48 \binom{4}{1}\cdot\binom{4}{1}\cdot\binom{3}{2}=48 ways.

For 2121, there are ( 4 2 ) ( 4 2 ) = 36 \binom{4}{2}\cdot\binom{4}{2}=36 ways.

In total, there are 12 + 12 + 48 + 36 = 108 12+12+48+36=\boxed{108} ways possible.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...