HMMT 二月 2011 · COMBGEO 赛 · 第 12 题
HMMT February 2011 — COMBGEO Round — Problem 12
题目详情
- The ordered pairs (2011 , 2) , (2010 , 3) , (2009 , 4) , . . . , (1008 , 1005), (1007 , 1006) are written from left to right on a blackboard. Every minute, Elizabeth selects a pair of adjacent pairs ( x , y ) and ( x , y ), with i i j j ( ) x y x x y y i i j i i j ( x , y ) left of ( x , y ), erases them, and writes , in their place. Elizabeth continues i i j j y x j j this process until only one ordered pair remains. How many possible ordered pairs ( x, y ) could appear on the blackboard after the process has come to a conclusion?
解析
- The ordered pairs (2011 , 2) , (2010 , 3) , (2009 , 4) , . . . , (1008 , 1005), (1007 , 1006) are written from left to right on a blackboard. Every minute, Elizabeth selects a pair of adjacent pairs ( x , y ) and ( x , y ), with i i j j ( ) x y x x y y i i j i i j ( x , y ) left of ( x , y ), erases them, and writes , in their place. Elizabeth continues i i j j y x j j this process until only one ordered pair remains. How many possible ordered pairs ( x, y ) could appear on the blackboard after the process has come to a conclusion? Answer: 504510 First, note that none of the numbers will ever be 0. Let ? denote the replacement operation. For each pair on the board ( x , y ) define its primary form to be ( x , y ) and its secondary i i i i x i form to be [ x y , ]. Note that the primary form determines the secondary form uniquely and vice i i y i versa. In secondary form, ( √ ) ( √ ) ( ) √ √ a a a 1 2 1 2 2 [ a , b ] ? [ a , b ] = a b , ? a b , = a b , = [ a , b ] . 1 1 2 2 1 1 2 2 1 2 1 2 b b b 1 2 2 Thus we may replace all pairs on the board by their secondary form and use the above rule for ? instead. From the above rule, we see that if the leftmost number on the board is x , then after one 2 minute it will be x or x depending on whether it was erased in the intervening step, and similarly for the rightmost number. Let k be the number of times the leftmost pair is erased and n be the number of times the rightmost pair is erased. Then the final pair is [ ] n ( ) 2 k 1007 2 4022 , . (2) 1006 Any step except the last cannot involve both the leftmost and rightmost pair, so k + n ≤ 1005. Since every pair must be erased at least once, k, n ≥ 1. Every pair of integers satisfying the above can occur, for example, by making 1005 − k − n moves involving only the pairs in the middle, then making k − 1 moves involving the leftmost pair, and finally n moves involving the rightmost pair. In light of (2), the answer is the number of possible pairs ( k, n ), which is 1004 1005 − k 1004 1004 ∑ ∑ ∑ ∑ 1004 · 1005 1 = 1005 − k = k = = 504510 . 2 k =1 n =1 k =1 k =1 Combinatorics & Geometry Individual Test