M04-29

Official Solution:

John has 12 clients, and he wants to use color coding to identify each of them. He can use either a single color or a pair of two different colors to represent a client code. Assuming that switching the order of colors within a pair does not create a different code, what is the minimum number of colors needed for this coding scheme?

A. 24
B. 12
C. 7
D. 6
E. 5


Combination approach:

Let the number of colors needed be \(n\). Then, ensuring that the total number of unique color codes (single color codes + two-color codes) is sufficient for all 12 clients, the inequality \(n + C^2_n \ge 12\) must hold.

\(n+\frac{n(n-1)}{2} \ge 12\);

\(2n+n(n-1) \ge 24\);

\(n(n+1) \ge 24\). As \(n\) is an integer (it represents the number of colors), then \(n \ge 5\), so \(n_{\text{min}}=5\).

Trial and error approach:

If the minimum number of colors needed is 4, then there are 4 single color codes possible PLUS \(C^2_4=6\) two-color codes. Total: \(4+6=10 < 12\). Not enough for 12 codes;

If the minimum number of colors needed is 5, then there are 5 single color codes possible PLUS \(C^2_5=10\) two-color codes. Total: \(5+10=15 > 12\). More than enough for 12 codes.

As the least answer choice is 5, if you tried it first, you would arrive at the correct answer immediately.


Answer: E