PUMaC 2023 · 组合（B 组） · 第 1 题

PUMaC 2023 — Combinatorics (Division B) — Problem 1

I have a 2 by 4 grid of squares; how many ways can I shade at least one of the squares so that no two shaded squares share an edge?

解析

I have a 2 by 4 grid of squares; how many ways can I shade at least one of the squares so that no two shaded squares share an edge? Proposed by Austen Mazenko Answer: 40 We proceed with casework on the number of shaded squares. Case 1 (one shaded square): evidently, there are 2 · 4 = 8 different squares that can be chosen as the shaded one. 8 Case 2 (two shaded squares): we complementary count. There are = 28 ways to choose 2 two squares to shade. Now, there are 6 pairs with a shared vertical edge, and 4 pairs with a shared horizontal edge, so subtracting off these cases gives 28 − 10 = 18 options. Case 3 (three shaded squares): the shaded squares evidently must all be in different columns. If they are in three consecutive columns, which can happen 2 ways, then evidently a checkerboard pattern is the only way that two of them aren’t adjacent, giving 2 · 2 options. Similarly, if one of the two middle columns lacks a shaded square, which happens 2 ways, then the two shaded squares in adjacent columns must be in different rows; this can happen 2 ways, and the other shaded square also has two choices for row. Thus this case contributes 4 + 2 · 2 · 2 = 12 in total. Case 4 (four shaded squares): they all must be in a checkerboard pattern, of which there are 2, each determined by the location of the shaded square in the leftmost column. In sum, there are 8 + 18 + 12 + 2 = 40 ways to shade.