HMMT 二月 2001 · ADV 赛 · 第 4 题

英文解析

4. Boris was given a Connect Four game set for his birthday, but his color-blindness makesit hard to play the game. Still, he enjoys the shapes he can make by dropping checkers intothe set. If the number of shapes possible modulo (horizontal) flips about the vertical axis ofsymmetry is expressed as 9(1 + 2 + · · · + n ), find n . (Note: the board is a vertical grid withseven columns and eight rows. A checker is placed into the grid by dropping it from the topof a column, and it falls until it hits either the bottom of the grid or another checker alreadyin that column. Also, 9(1 + 2 + · · · + n ) is the number of shapes possible, with two shapesthat are horizontal flips of each other counted as one. In other words, the shape that consistssolely of 3 checkers in the rightmost row and the shape that consists solely of 3 checkers inthe leftmost row are to be considered the same shape.)
   Solution: There are 9 total shapes possible, since each of the 7 columns can contain 7
   anywhere from 0 to 8 checkers. The number of shapes symmetric with respect to a horizontalflip is the number of shapes of the leftmost four columns, since the configuration of thesefour columns uniquely determines the configuration of the remaining columns if it is known
   4 7 4
   the shape is symmetric: 9 . Now we know there are 9 − 9 non-symmetric shapes, so there
   7 4
   9 − 9
   are non-symmetric shapes modulo flips. Thus the total number of shapes modulo flips
   ( ) ( )2
   8 6 6 6
   7 4 3 3
   3 (3 − 1) 3 (3 +1)
   9 − 9 9 − 1 9 +1
   4 4 4 6
   is 9 + = 9 1 + = 9 = ( = 9 = 9(1 + 2 + · · · + 3 ), so
   2 2 2 2 2
   n = 3 = 729 .6