HMMT 十一月 2016 · 团队赛 · 第 8 题

英文解析

8. [ 6 ] Alex has an 20 × 16 grid of lightbulbs, initially all off. He has 36 switches, one for each row andcolumn. Flipping the switch for the i th row will toggle the state of each lightbulb in the i th row (sothat if it were on before, it would be off, and vice versa). Similarly, the switch for the j th column willtoggle the state of each bulb in the j th column. Alex makes some (possibly empty) sequence of switchflips, resulting in some configuration of the lightbulbs and their states. How many distinct possibleconfigurations of lightbulbs can Alex achieve with such a sequence? Two configurations are distinct ifthere exists a lightbulb that is on in one configuration and off in another.
   Proposed by: Christopher Shao
   Answer: 235
   The switch flip operations are commutative, so for any given sequence of switch flips S , we get the sameconfiguration regardless of the order we do them in. We can arrange the switch flips so that all of theflips of the same switch happen consecutively. Furthermore, two consecutive flips of the same switch
   ′
   leave the configuration unchanged, so we can remove them, resulting in a sequence of switch flips Sthat involves flipping a switch for a row or column at most once that achieves the same configuration
   ′ ′
   as S . The order of the flips in S also doesn’t matter, so we can treat S as a set of switches that areflipped to produce the same configuration as S .
   The desired number is then equal to the number of distinct configurations that can be obtained by
   ′
   flipping exactly the switches in some subset S of the set of all of the switches. We claim that if Sand S are distinct sets of switches that result in the same configuration of lights, then S and S1
   2 1 2
   are complements. Indeed, without loss of generality, suppose that the first row’s switch is in S andthat it isn’t in S . In order to have the same configuration of lights in the first row, we must have 1
   that every column switch is in S if and only if it isn’t in S . Applying the same argument to the 2
   1 2
   first column yields that every row switch is in S if and only if it isn’t in S , and the claim follows.
   1 2
   Thus, for every set of switches, there is exactly one other set that attains the same configuration as it,
   m + nnamely its complement. There are 2 sets of switches possible, and so the total number of possiblem + n m + n − 1
   configurations is 2 / 2 = 2 .