Learn / Library / Brainteasers

Divisibility claims

BrainteasersHard

$20$ contestants are numbered $1$ to $20$ . Each is honest (a truth-teller) or deceptive (a liar). Contestant $i$ says: "The number of honest contestants among the $20$ of us is a multiple of $i$ ." ( $0$ counts as a multiple of every number.) In how many different ways can the types be assigned so that all $20$ statements are consistent?

Checking an answer needs JavaScript. The hint and the solution open without it.

Hint

Let $T$ be the number of truth-tellers. The statements depend only on $T$ , so find which $T$ can be consistent with the set of people who are truthful.

Solution

Let $T$ be the number of truth-tellers. Person $i$ is truthful exactly when $i$ divides $T$ , so the truth-tellers are the people whose numbers divide $T$ , and there must be exactly $T$ of them.
If $T = 0$ every number divides $0$ , giving $20$ truth-tellers, which is a contradiction.
For $T \geq 3$ the divisors of $T$ other than $T$ itself are at most $\frac{T}{2}$ , so there are at most $1 + \frac{T}{2} < T$ truth-tellers, which is a contradiction.
For $T = 1$ the only divisor is $1$ , and for $T = 2$ the divisors are $1$ and $2$ , and both are consistent; each $T$ fixes the assignment, so the count is $2$ .

Answer: $2$

Next question Back to the library