In how many ways can $a, b, c$, and $d$ be chosen from the set $\{0,1,2, \ldots, 9\}$ so that $a<b<c<d$ and $a+b+c+d$ is a multiple of three?
(A) 54
(B) 64
(C) 63
(D) 90
(E) 72
Since we are looking at choosing four different numbers from the set $\{0,1,2, \ldots, 9\}$, then there is only one way to write them in increasing order. So we only need to look at the number of ways of choosing four numbers so that their sum is a multiple of 3 (that is, we do not need to worry about looking at the order of the choices).

If we take four numbers and add them up, then the fact that the sum is divisible by 3 (or not) is not affected when we subtract a multiple of 3 from any of the four numbers, since the difference between multiples of 3 is a multiple of 3 .

Next, we can use the fact that every number can be written as a multiple of 3 , or as one more or one less than a multiple of 3 , ie. every integer can be written in the form $3 n$, $3 n+1$ or $3 n-1$.

So combining these two facts, we can transform the set $\{0,1,2,3,4,5,6,7,8,9\}$ into to the collection $\{0,1,-1,0,1,-1,0,1,-1,0\}$, for example by subtracting 6 from 5 to get -1 . (A "set" cannot technically have more than one copy of the same element, whereas a “collection" can!)

So now we want to choose 4 numbers from the collection $\{0,1,-1,0,1,-1,0,1,-1,0\}$ whose sum is a multiple of 3 (including possibly 0 ).

How can we do this?

If we choose 4 zeros, then the sum is $0+0+0+0=0$, which is a multiple of 3 .

If we choose 3 zeros, then the remaining number chosen is a 1 or a -1 , so the sum is not a multiple of 3 .

If we choose 2 zeros, then we can choose two 1's, two -1 's, or 1 and -1 . Only the third choice gives a multiple of 3 .

If we choose 1 zero, then to get a multiple of 3 , we must choose three 1 's or three -1 's. (You might want to check that no other combination works!)

If we choose 0 zeros, then to get a multiple of 3 , we must choose two 1's and two -1 's (otherwise we choose three of one kind and one of the other, which will not give a multiple of 3).

So now we must count the number of choices for each case:

Case 1: 0, 0, 0, 0

Since there are only four zeros, there is only 1 way to choose them. (Recall that this corresponds to choosing $0,3,6$ and 9 , whose sum is indeed divisible by 3.)

Case 2: 0, 0, 1,-1

We must choose two zeros from four zeros, and one each of 1's and -1's from collections of three.

If we have 4 objects A, B, C, D then the number of ways of choosing 2 objects is $6(\mathrm{AB}, \mathrm{AC}, \mathrm{AD}, \mathrm{BC}, \mathrm{BD}, \mathrm{CD})$, and if we have 3 objects, then the number of ways of choosing 1 object is 3 . (This just means that there are 6 ways to choose 2 zeros from 4 possibilities.)

So the total number of choices here is $6 \times 3 \times 3=54$, since for each choice of two 0 's, we have 3 choices for the 1 , and 3 choices for the -1 .

Case 3: 0, 1, 1, 1

We must choose one 0 from four zeros, and three 1's from 3 . There are 4 ways to choose the zero and 1 way to choose the three 1 's. Thus there are a total of 4 ways of making this selection.

Case 4: $0,-1,-1,-1$

Similarly to Case 3 , there are 4 possibilities.

Case 5: 1, 1,-1,-1

We must choose two 1's from three, and two -1 's from three. There are 3 ways to make each of these choices, or $3 \times 3=9$ ways in total.

Therefore, there are $1+54+4+4+9=72$ ways in total of choosing the numbers.

ANSWER: (E)