Learn / Library / Brainteasers

Safe dials on a cycle

BrainteasersHard

$100$ safes numbered $1$ to $100$ each have a dial showing $0$ , $1$ or $2$ , and all dials start at $0$ . For each $k$ from $1$ to $100$ , a guard turns the dial of every safe whose number is a multiple of $k$ one step forward, so $0$ goes to $1$ , $1$ to $2$ and $2$ back to $0$ . How many dials show $0$ at the end?

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

Hint

A dial ends at $0$ when the number of divisors is a multiple of $3$ ; use the prime factorisation.

Solution

The dial of safe $n$ ends at $0$ exactly when the number of divisors of $n$ is a multiple of $3$ .
If $n = p^{a} \times q^{b} \times \dots$ , the number of divisors is $(a + 1) (b + 1) \dots$ , which is a multiple of $3$ exactly when some factor $a + 1$ is, that is, for numbers up to $100$ , when some exponent equals $2$ or $5$ .
Up to $100$ , the exponent of the prime $2$ is exactly $2$ for $13$ numbers and exactly $5$ for $2$ numbers; the exponent is exactly $2$ for the primes $3$ , $5$ and $7$ in $8$ , $4$ and $2$ numbers.
That is $13 + 2 + 8 + 4 + 2 = 29$ , but $36$ and $100$ were counted $2$ times each.
So $29 - 2 = 27$ dials show $0$ , and the answer is $27$ .

Answer: $27$

Next question Back to the library