У спортзалі 100 шафок із номерами від 1 до 100, усі зачинені. Повз них проходять лише учні з непарними номерами, k = 1, 3, 5, …, 99, і учень k змінює стан кожної шафки, номер якої кратний k: відчиняє зачинену й зачиняє відчинену. Скільки шафок відчинено наприкінці?

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

Лише непарні учні

ГоловоломкиСереднє

У спортзалі $100$ шафок із номерами від $1$ до $100$ , усі зачинені. Повз них проходять лише учні з непарними номерами, $k = 1, 3, 5, \dots, 99$ , і учень $k$ змінює стан кожної шафки, номер якої кратний $k$ : відчиняє зачинену й зачиняє відчинену. Скільки шафок відчинено наприкінці?

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

Підказка

Шафку $n$ чіпають один раз для кожного непарного дільника $n$ .

Розв’язок

Запишемо $n = 2^{a} \times m$ , де $m$ непарне; шафку $n$ чіпають один раз на кожен дільник $m$ .
Ця кількість непарна тоді й лише тоді, коли $m$ повний квадрат, тож $n$ є квадратом або квадратом, помноженим на $2$ .
До $100$ є $10$ квадратів і $7$ чисел виду $2 j^{2}$ : $2$ , $8$ , $18$ , $32$ , $50$ , $72$ і $98$ .
Отже, відчинено $10 + 7 = 17$ шафок.

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

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