HMMT 二月 2007 · COMB 赛 · 第 5 题

HMMT February 2007 — COMB Round — Problem 5

[ 5 ] Determine the number of ways to select a positive number of squares on an 8 × 8 chessboard such that no two lie in the same row or the same column and no chosen square lies to the left of and below another chosen square.

解析

[ 5 ] Determine the number of ways to select a positive number of squares on an 8 × 8 chessboard such that no two lie in the same row or the same column and no chosen square lies to the left of and below another chosen square. 1 ( ) ( ) 16 8 Answer: 12869 = − 1 . If k is the number of squares chosen, then there are ways to choose k 8 k ( ) 8 columns, and ways to choose k rows, and this would uniquely determine the set of squares selected. k Thus the answer is ( )( ) ( )( ) ( ) 8 8 ∑ ∑ 8 8 8 8 16 = − 1 + = − 1 + = 12869 k k k k 8 k =1 k =0