HMMT 二月 2010 · TEAM2 赛 · 第 1 题

HMMT February 2010 — TEAM2 Round — Problem 1

[ 10 ] How many ways are there to place pawns on an 8 × 8 chessboard, so that there is at most 1 pawn e e 1 2 in each horizontal row? Express your answer in the form p · p · · · , where the p are distinct primes i 1 2 and the e are positive integers. i

解析

What is the longest distance between any two points in the figure? √ 1+ 13 Answer: Inspection shows that one point must be on the semicircle and the other must 2 be on the side of the hexagon directly opposite the edge with the semicircle, the bottom edge of the hexagon in the above diagram. Let O be the center of the semicircle and let M be the midpoint of the bottom edge. We will determine the longest distance between points in the figure by comparing the lengths of all the segments with one endpoint on the bottom edge and the other endpoint on the semicircle. Fix a point A on the bottom edge of the hexagon. Suppose that B is chosen on the semicircle such that AB is as long as possible. Let C be the circle centered at A with radius AB . If C is not tangent to the ′ semicircle, then part of the semicircle is outside C , so we could pick a B on the semicircle such that ′ AB is longer than AB . So C must be tangent to the semicircle, and AB must pass through O . 1 Then OB is always , no matter which A we choose on the bottom edge. All that remains is maximizing 2 AO . This length is the hypotenuse of a right triangle with the fixed height M O , so it is maximized √ 3 when AM is as large as possible - when A is an endpoint of the bottom edge. Note that M O = 2 · , 2 √ 1 13 and that AM can be at most , so AO can be at most . So the maximum distance between two 2 2 √ 1+ 13 points in the diagram is AO + OB = . 2 n n − 1