HMMT 二月 2004 · COMB 赛 · 第 9 题
HMMT February 2004 — COMB Round — Problem 9
题目详情
英文原题
- A classroom consists of a 5 × 5 array of desks, to be filled by anywhere from 0 to 25
students, inclusive. No student will sit at a desk unless either all other desks in its rowor all others in its column are filled (or both). Considering only the set of desks that areoccupied (and not which student sits at each desk), how many possible arrangementsare there? 1
解析
英文解析
- A classroom consists of a 5 × 5 array of desks, to be filled by anywhere from 0 to 25
students, inclusive. No student will sit at a desk unless either all other desks in its rowor all others in its column are filled (or both). Considering only the set of desks that areoccupied (and not which student sits at each desk), how many possible arrangementsare there?
Solution: 962
The set of empty desks must be of the form (non-full rows) × (non-full columns): eachempty desk is in a non-full column and a non-full row, and the given condition impliesthat each desk in such a position is empty. So if there are fewer than 25 students, thenboth of these sets are nonempty; we have 2 − 1 = 31 possible sets of non-full rows, and 53
31 sets of non-full columns, for 961 possible arrangements. Alternatively, there may be
25 students, and then only 1 arrangement is possible. Thus there are 962 possibilitiesaltogether.