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 row or all others in its column are filled (or both). Considering only the set of desks that are occupied (and not which student sits at each desk), how many possible arrangements are 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 row or all others in its column are filled (or both). Considering only the set of desks that are occupied (and not which student sits at each desk), how many possible arrangements are there? Solution: 962 The set of empty desks must be of the form (non-full rows) × (non-full columns): each empty desk is in a non-full column and a non-full row, and the given condition implies that each desk in such a position is empty. So if there are fewer than 25 students, then 3 5 both of these sets are nonempty; we have 2 − 1 = 31 possible sets of non-full rows, and 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 possibilities altogether.