A list of positive integers has a unique mode, which occurs exactly times. What is the least number of distinct values that can occur in the list?
- A)
- B)
- C)
- D)
- E)
Answer
D
Key insight
Every non-mode value appears at most 9 times, so the other 2008 entries need at least ceil(2008/9) = 224 values, plus the mode makes 225.
Solution
The mode occupies of the entries, leaving entries to be filled by other values. Because the mode is unique, every other value appears at most times.
To use as few distinct values as possible, make each of the other values appear as often as allowed, times. Then the number of other values must satisfy , so
This is achievable: take values appearing times each ( entries) and one more value appearing once.
Including the mode, the minimum number of distinct values is .
The answer is .
Why this works
Minimizing the number of distinct values means packing the non-mode entries as tightly as the "unique mode" rule permits, which caps every other frequency at . The bound is a ceiling, and the construction shows it is attained. Always finish by counting all the values asked for, here the mode included.
The trap
Forgetting to add the mode itself (answering 224), or dividing 2008 by 9 and rounding down to 223.
Common mistakes
- Forgetting to add the mode itself (answering 224), or dividing 2008 by 9 and rounding down to 223.
- Allowing other values to appear times as well, which would destroy the uniqueness of the mode and give .
Techniques
Bound the quantity above/below or estimate to pin it down · Consider the largest/smallest element or boundary case