HMMT 二月 2014 · 团队赛 · 第 6 题

HMMT February 2014 — Team Round — Problem 6

[ 25 ] Let n be a positive integer. A sequence ( a , . . . , a ) of integers is acceptable if it satisfies the 0 n following conditions: (a) 0 = | a | < | a | < · · · < | a | < | a | . 0 1 n 1 n n 1 (b) The sets {| a a | , | a a | , . . . , | a a | , | a a |} and { 1 , 3 , 9 , . . . , 3 } are equal. 1 0 2 1 n 1 n 2 n n 1 Prove that the number of acceptable sequences of integers is ( n + 1)!.

解析

[ 25 ] Let n be a positive integer. A sequence ( a , . . . , a ) of integers is acceptable if it satisfies the 0 n following conditions: (a) 0 = | a | < | a | < · · · < | a | < | a | . 0 1 n − 1 n n − 1 (b) The sets {| a − a | , | a − a | , . . . , | a − a | , | a − a |} and { 1 , 3 , 9 , . . . , 3 } are equal. 1 0 2 1 n − 1 n − 2 n n − 1 Prove that the number of acceptable sequences of integers is ( n + 1)!. Answer: N/A We actually prove a more general result via strong induction on n. First, we state the more general result we wish to prove. For n > 0, define a great sequence to be a sequence of integers ( a , . . . , a ) such that 0 n