Maths Olympiad Prep

Track / Stage 3 / 190 of 260 #190 of 1964

Problem 190

AMC 10/12, early questions
Combinatorics Difficulty 3.5 Find the answer

A choir director must select a group of singers from among his 66 tenors and 88 basses. The only requirements are that the difference between the number of tenors and basses must be a multiple of 44, and the group must have at least one singer. Let NN be the number of different groups that could be selected. What is the remainder when NN is divided by 100100?

Pick one

Official solution

Suppose that tt tenors and bb basses are selected. The requirements are tb(mod4)t\equiv b\pmod{4} and (t,b)(0,0).(t,b)\neq(0,0).
It follows that b=8bb'=8-b basses are not selected. Since the ordered pairs (t,b)(t,b) and the ordered pairs (t,b)(t,b') have one-to-one correspondence, we consider the ordered pairs (t,b)(t,b') instead. The requirements become t8b(mod4)t\equiv8-b'\pmod{4} and (t,8b)(0,0),(t,8-b')\neq(0,0), which simplify to t+b0(mod4)t+b'\equiv0\pmod{4} and (t,b)(0,8),(t,b')\neq(0,8), respectively.
As t+b{0,4,8,12},t+b'\in\{0,4,8,12\}, the total number of such groups is
\begin{align*} N&=\binom{14}{0}+\binom{14}{4}+\left[\binom{14}{8}-1\right]+\binom{14}{12} \\ &=\binom{14}{0}+\binom{14}{4}+\left[\binom{14}{6}-1\right]+\binom{14}{2} \\ &=1+1001+[3003-1]+91 \\ &=4095, \end{align*}
from which N(D) 95(mod100).N\equiv\boxed{\textbf{(D) } 95}\pmod{100}.
~MRENTHUSIASM

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.