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

Коридор ламп

ГоловоломкиЛегке

У коридорі $200$ ламп із номерами від $1$ до $200$ , усі вимкнені. Для кожного $k$ від $1$ до $200$ по черзі технік натискає вимикач кожної лампи, номер якої кратний $k$ ; кожне натискання вмикає вимкнену лампу й вимикає увімкнену. Скільки ламп горить наприкінці?

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

Підказка

Лампу натискають один раз для кожного дільника її номера.

Розв’язок

Лампу $n$ натискають один раз для кожного дільника $n$ , і вона горить наприкінці тоді й лише тоді, коли дільників непарна кількість.
Дільники розбиваються на пари $d$ і $\frac{n}{d}$ , тож їхня кількість непарна лише тоді, коли якийсь дільник утворює пару сам із собою, тобто коли $n$ є повним квадратом.
Квадрати до $200$ це від $1^{2}$ до $1 4^{2}$ , бо $1 4^{2} = 196$ , а $1 5^{2} = 225$ .
Отже, горить $14$ ламп.

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

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