Library / /12 of 62

, 2020

Combinatorics Difficulty 4.5 AIME Find the answer United States

Problem:
A small village has $n$ people. During their yearly elections, groups of three people come up to a stage and vote for someone in the village to be the new leader. After every possible group of three people has voted for someone, the person with the most votes wins.
This year, it turned out that everyone in the village had the exact same number of votes! If $10 \leq n \leq 100$ , what is the number of possible values of $n$ ?
Proposed by: Vincent Bian

Your answer

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Solution:
The problem asks for the number of $n$ that divide $\binom{n}{3}$ , which happens exactly when $\frac{(n-1)(n-2)}{2 \cdot 3}$ is an integer. Regardless of the parity of $n$ , $(n-1)(n-2)$ is always divisible by $2$ . Also, $(n-1)(n-2)$ is divisible by $3$ if and only if $n$ is not a multiple of $3$ . Of the $91$ values from $10$ to $100$ , $30$ are divisible by $3$ , so our answer is $61$ .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.