开灯问题

2015年10月25日

一、问题描述

有n盏灯和n个人,一开始所有灯都是灭的,第一个人按开关 1 , 2 , 3 , 4… ,第二个人按开关 2 , 4 , 6… , 第三个人按开关 3 , 6 , 9… ,以此类推,最后剩那几盏灯是亮的。

二、解决方法

最后还亮着的灯具有特性:该灯被按了奇数次,所以这个问题可以转换为那些k具有奇数个因子(k <= n)。 k的因式分解可表示如下: num(k)表示关于k有几个因子的函数,由排列组合易得: 由此,如果最后第k盏灯亮着,必须有为偶数,即 由上易得,若第K盏灯最后亮着,则K必为完全平方数。