Problem:
A choir director must select a group of singers from among his 6 tenors and 8 basses. The only requirements are that the difference between the number of tenors and basses must be a multiple of 4 , and the group must have at least one singer. Let N be the number of groups that can be selected. What is the remainder when N is divided by 100 ?
Answer Choices:
A. 47
B. 48
C. 83
D. 95
E. 96
Solution:
Suppose the number of tenors selected is t and the number of basses selected is b. Then the conditions require that tβ‘b(mod4), and (t,b)ξ =(0,0). Instead, consider having the director select the tenors who will sing and the basses who will not sing. Then the director will be selecting t tenors and bβ²=8βb basses, where tβ‘b(mod4), so t+bβ²=t+8βb=8β‘0(mod4). Thus the director selects k singers from the 14 singers, where kβ‘0(mod4). The number of ways this can be done with at least one singer is
N=(144β)+(148β)+(1412β)=(144β)+(146β)+(142β)=4β
3β
2β
114β
13β
12β
11β+6β
5β
4β
3β
2β
114β
13β
12β
11β
10β
9β+2β
114β
13β=7β
13β
11+7β
13β
11β
3+7β
13=91β
(11+33+1)=91β
45=4095.β
The requested remainder is 95β .
OR
The calculation above can be done without messy arithmetic by using the properties of Pascal's Triangle:
N=(140β)+(144β)+(148β)+(1412β)β(140β)=21βk=0β7β(142kβ)β1β
=21βk=1β7β(142kβ1β)β1=41βk=0β14β(14kβ)β1=41ββ
214β1=212β1=4095.β
OR
Let t be the number of tenors selected and b the number of basses selected. Then there are 15 choices for (t,b) : (0,4),(0,8),(1,1),(1,5),(2,2),(2,6),(3,3),(3,7),(4,0),(4,4),(4,8),(5,1),(5,5),(6,2), and (6,6). The number of ways to select the singers is therefore the sum of the following products of binomial coefficients:
(60β)β
(84β)=1β
70=70(60β)β
(88β)=1β
1=1(61β)β
(81β)=6β
8=48(61β)β
(85β)=6β
56=336(62β)β
(82β)=15β
28=420(62β)β
(86β)=15β
28=420(63β)β
(83β)=20β
56=1120(63β)β
(87β)=20β
8=160(64β)β
(80β)=15β
1=15(64β)β
(84β)=15β
70=1050(64β)β
(88β)=15β
1=15(65β)β
(81β)=6β
8=48(65β)β
(85β)=6β
56=336(66β)β
(82β)=1β
28=28(66β)β
(86β)=1β
28=28(86β)=15=15=15=β
The sum of the numbers calculated above is 4095 , and the requested remainder is 95β .
The problems on this page are the property of the MAA's American Mathematics Competitions