若某房间的灯有开有关,称其为好的,否则称为坏的.
显然,改变坏房间中一盏灯时房间必然变好,
而改变好房间的一盏灯时,当且仅当此灯与房间内剩下的所有灯都状态不同时房间才会变坏.
观察某状态下的某个坏房间,作以下操作:
选择该房间未操作过的一盏灯,改变它(从而使房间变好),观察此时改变的另一盏灯;
若其改变让其所在房间从好变成坏,那么对该坏房间也作这个操作.
在第一次观察到一个已经观察过的房间之前,每次将好房间变坏后,该房间至少还有两盏未操作过的灯,故该操作必然能继续进行.
房间数是有限的,故若操作永远不能结束,则若干步后必然会观察到一个已经观察过的房间.
如果此时最后一次操作是同时改变了当前房间中两盏灯,由于操作前该房间是坏的,而房间中至少有三盏灯,故操作后该房间必然是好的,此时操作就应该结束了.
否则,此次操作是将一个房间从坏变好,并改变了之前观察过的某房间里对应的一盏灯A.
该房间之前观察过故此操作前一定是好的,并且该房间的上一次改变是在上次观察时改变了一盏灯B使其从坏变成好;
那么此次操作前房间的状态应当是上次B和房间中剩下所有灯都不同,而此次操作改变了A,使得AB变成相同,但房间中至少还有第三盏灯,此时它与AB不同,于是此次操作后该房间应该仍然是好的.
综上,该操作必然能合法进行,且一定会结束.
显然任选一个坏房间进行该操作后,总能在有限次切换开关后,使其变好,且其它所有改变过的房间在最后依然是好的.
该操作能在任何有坏房间的状况下严格减少坏房间的总数量,不断重复后,任何初态都能变成全部都是好房间.
□
(这题难度远达不到imo吧,如果真是shortlist也难怪选不上.. |
