HMMT 十一月 2023 · 冲刺赛 · 第 22 题

HMMT November 2023 — Guts Round — Problem 22

[12] There is a 6 × 6 grid of lights. There is a switch at the top of each column and on the left of each row. A light will only turn on if the switches corresponding to both its column and its row are in the “on” position. Compute the number of different configurations of lights. 1 1

解析

[12] There is a 6 × 6 grid of lights. There is a switch at the top of each column and on the left of each row. A light will only turn on if the switches corresponding to both its column and its row are in the “on” position. Compute the number of different configurations of lights. Proposed by: Jacob Paltrowitz Answer: 3970 Solution: Take any configuration of switches such that there exists at least one row and one column 6 2 which are switched on. There are (2 − 1) = 3969 such configurations. We prove that any two such configurations A and B lead to a different set of lights. Without loss of generality assume A has row r switched on and B doesn’t have row r switched on. Thus, configuration A will contain at least one light turned on in row r (since there exists at least one column switch which is turned on), while configuration B contains zero such lights turned on. Thus configuration A and B lead to different sets of lights. All configurations where all columns or all rows are turned off lead to all lights being turned off. We add 1 extra option to account for this case, getting 3969 + 1 = 3970 total possibilities. 1 1