HMMT 十一月 2020 · THM 赛 · 第 6 题
HMMT November 2020 — THM Round — Problem 6
题目详情
- The elevator buttons in Harvard’s Science Center form a 3 × 2 grid of identical buttons, and each button lights up when pressed. One day, a student is in the elevator when all the other lights in the elevator malfunction, so that only the buttons which are lit can be seen, but one cannot see which floors they correspond to. Given that at least one of the buttons is lit, how many distinct arrangements can the student observe? (For example, if only one button is lit, then the student will observe the same arrangement regardless of which button it is.)
解析
- The elevator buttons in Harvard’s Science Center form a 3 × 2 grid of identical buttons, and each button lights up when pressed. One day, a student is in the elevator when all the other lights in the elevator malfunction, so that only the buttons which are lit can be seen, but one cannot see which floors they correspond to. Given that at least one of the buttons is lit, how many distinct arrangements can the student observe? (For example, if only one button is lit, then the student will observe the same arrangement regardless of which button it is.) Proposed by: Sheldon Kieren Tan Answer: 44 6 Solution 1: We first note that there are 2 − 1 = 63 possibilities for lights in total. We now count the number of duplicates we need to subtract by casework on the number of buttons lit. To do this, we do casework on the size of the minimal “bounding box” of the lights: • If the bounding box is 1 × 1, the only arrangement up to translation is a solitary light, which can be translated 6 ways. This means we must subtract 5. • If the bounding box is 2 × 1, there is 1 arrangement and 4 translations, so we must subtract 3. • If the bounding box is 1 × 2, there is 1 arrangement and 3 translations, so we must subtract 2. • If the bounding box is 3 × 1, there are 2 arrangements and 2 translations, so we must subtract 2. • If the bounding box is 2 × 2, there are 2 arrangements with 2 lights, 4 with 3 lights, and 1 with 4 lights—7 in total. Since there are two translations, we must subtract 7. The final answer is 63 − 5 − 3 − 2 − 2 − 7 = 44. Solution 2: We may also count duplicates by doing casework on buttons lit: • 1 buttons lit: There are 6 arrangements but all are the same, so we need to subtract 5 duplicates in this case. • 2 buttons lit: There are 4 indistinguishable ways for the buttons to be vertically adjacent, 3 to be horizontally adjacent, 2 ways for the buttons to be diagonally adjacent for each of 2 directions of diagonals, and 2 for when the lights are in the same vertical line but not adjacent. Since we need to count each of these cases only once, the number of duplicates we need to subtract is 3 (2 vertically adjacent), 2 (2 horizontally adjacent), 2 × 1 (2 diagonally adjacent), and 1 (2 in same vertical line but not adjacent) for a total of 8 duplicates. • 3 buttons lit: There are 2 indistinguishable ways for all the buttons in a column to be lit and 2 ways for the buttons to be lit in the shape of an L, given the rotation of the L. Thus, the number of duplicates we need to subtract is 1 (1 column), 1 × 4 (rotations of L), for a total of 5 duplicates. • 4 buttons lit: There are 2 indistinguishable ways for the lights to be arranged in a square (and no other duplicates), so we need to subtract 1 duplicate in this case. • When there are 5 or 6 buttons lit, all of the arrangements of lights are distinct, so we do not subtract any duplicates for these cases. Thus, the total number of arrangements is 64 − (1 + 5 + 8 + 5 + 1) = 44.