Навчання / Бібліотека / Головоломки

Диски сейфів по колу

ГоловоломкиСкладне

$100$ сейфів із номерами від $1$ до $100$ мають диски, що показують $0$ , $1$ або $2$ , і всі диски спочатку стоять на $0$ . Для кожного $k$ від $1$ до $100$ охоронець повертає диск кожного сейфа, номер якого кратний $k$ , на один крок уперед: $0$ переходить в $1$ , $1$ у $2$ , а $2$ знову в $0$ . Скільки дисків показують $0$ наприкінці?

Для перевірки відповіді потрібен JavaScript. Підказка й розв’язок відкриваються і без нього.

Підказка

Диск повертається на $0$ , якщо кількість дільників кратна $3$ ; скористайтеся розкладом на прості множники.

Розв’язок

Диск сейфа $n$ наприкінці показує $0$ тоді й лише тоді, коли кількість дільників $n$ кратна $3$ .
Якщо $n = p^{a} \times q^{b} \times \dots$ , кількість дільників дорівнює $(a + 1) (b + 1) \dots$ , а вона кратна $3$ тоді й лише тоді, коли кратний якийсь множник $a + 1$ , тобто для чисел до $100$ коли якийсь показник дорівнює $2$ або $5$ .
До $100$ показник простого $2$ дорівнює рівно $2$ у $13$ чисел і рівно $5$ у $2$ чисел; показник дорівнює рівно $2$ для простих $3$ , $5$ і $7$ у $8$ , $4$ і $2$ чисел.
Це $13 + 2 + 8 + 4 + 2 = 29$ , але $36$ і $100$ враховано по $2$ рази.
Отже, $29 - 2 = 27$ дисків показують $0$ , і відповідь $27$ .

Відповідь: $27$

Наступна задача Назад до бібліотеки