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 nfollowing conditions:
(a) 0 = | a | < | a | < · · · < | a | < | a | .
0 1 n 1 nn 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 nfollowing conditions:
(a) 0 = | a | < | a | < · · · < | a | < | a | .
0 1 n − 1 nn − 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