PUMaC 2009 · 组合（B 组） · 第 7 题
PUMaC 2009 — Combinatorics (Division B) — Problem 7
题目详情
- We have a 6 × 6 square, partitioned into 36 unit squares. We select some of these unit squares and draw some of their diagonals, subject to the condition that no two diagonals we draw have any common points. What is the maximal number of diagonals that we can draw?
解析
- We have a 6 × 6 square, partitioned into 36 unit squares. We select some of these unit squares and draw some of their diagonals, subject to the condition that no two diagonals we draw have any common points. What is the maximal number of diagonals that we can draw? Solution. 21. It is possible to draw 21 diagonals, as shown in the figure below. This is also the maximum: The vertices of the small squares form a 7 by 7 grid. Each diagonal has an endpoint in the second, fourth or sixth row of this grid. However, there are only 3 × 7 = 21 points on these 3 rows, so there can be at most 21 diagonals.