点灯しているあかりはいくつ？ （by kidryoheiさん）

（正解）

１５個

（解き方）

最初はすべての数が点灯していて、その数が秒数の倍数になるごとに点灯状態が変わるということは、言い換えれば、個々のあかりにとっては、そのあかりを表す数の「約数」が秒数になるたびに、点灯状態が変わるということです。
すると、
１番目の約数（どんな数でも常に「１」）→点灯
２番目の約数→消灯
３番目の約数→点灯
４番目の約数→消灯
…
となるので、約数の個数が奇数であれば点灯で終わり、約数の個数が偶数であれば消灯で終わることがわかります。
つまり、この問題は、「約数の個数が奇数である数が、２５０以下にいくつあるか」を求める問題と言えます。
そこで次はある数のすべての約数がいくつあるかの求め方ですが、その数を素因数分解（素数の累乗の積の形で表す）して、各素因数ごとに（指数＋１）を掛け合わせて求めることができます。
たとえば、２５０を素因数分解すると、
２５０＝２ｘ５ｘ５ｘ５＝（２＾１）×（５＾３）
（注： ^ は、テキストでは通常の累乗（Exponentiation）表記で用いる右肩の小さい数字での指数（Exponent）が表現できないために代用している記号です。）
となりますので、素因数２の指数は１、５の指数は３ですから、約数の個数は、
（１＋１）×（３＋１）＝８個　となります。
このようになる理由ですが、そもそも「割り切れる」というのは、ある数を素因数分解したときの素因数の一部のみを掛け算して除数を作った時にのみ成り立つことだからで、したがって、ある数の約数の個数を求めたいと思ったら、素因数の異なる掛け算の組み合わせを数え上げればいいからです。この２５０の場合だと、
２＾０×５＾０＝１
２＾０×５＾１＝５
２＾０×５＾２＝２５
２＾０×５＾３＝１２５
２＾１×５＾０＝２
２＾１×５＾１＝１０
２＾１×５＾２＝５０
２＾１×５＾３＝２５０
ですべて書き出すことができます。これを見ればわかるとおり、漏れのない組み合わせの作り方は、それぞれの素因数ごとに、０から指数の最大値までを順次組み合わせることなので、（１＋１）×（３＋１）＝８個がすべての約数となります。
次に、「約数の個数が奇数」となるためには、「個数を求めるために掛け合わせたすべての数が奇数である」必要があります。偶数にはなにを掛けても偶数になるので、掛け合わせた数の中に１つでも偶数があると、約数の個数は偶数になってしまうからです。
約数の個数は、各素因数の指数に１を足したものを掛け合わせていったものですから、これが奇数になるためには、すべての指数が偶数になる必要があります。そして、指数が偶数であるということは、それは必ず整数の２乗の形で表すことができるということです。（たとえば素因数３を偶数である指数４で累乗した 3^4 = 81 は、(3^2)^2 = 9×9 と整数の２乗の形に必ずできる）
これは、「約数の個数が奇数である数」は、必ず「完全平方数」（整数の２乗として表すことのできる数）であることを意味し、逆に完全平方数は、すべての素因数の指数が偶数になるので、必ず約数の個数は奇数になります。
とするとあとは、２５０以下の数に、完全平方数がいくつあるかという問題です。
１５＾２＝２２５で２５０以下、１６＾２＝２５６で２５０を超えるので、１５＾２＝２２５が２５０以下の完全平方数の最大値。最低はもちろん１＾２＝１なので、結局１の２乗から１５の２乗までの１５個ということになります。