HMMT 十一月 2014 · 冲刺赛 · 第 26 题
HMMT November 2014 — Guts Round — Problem 26
题目详情
英文原题
- [ 13 ] Consider a permutation ( a , a , a , a , a ) of { 1 , 2 , 3 , 4 , 5 } . We say the tuple ( a , a , a , a , a ) is
1 2 3 4 5 1 2 3 4 5
flawless if for all 1 ≤ i < j < k ≤ 5, the sequence ( a , a , a ) is not an arithmetic progression (in thati j korder). Find the number of flawless 5-tuples.
解析
英文解析
- [ 13 ] Consider a permutation ( a , a , a , a , a ) of { 1 , 2 , 3 , 4 , 5 } . We say the tuple ( a , a , a , a , a ) is
1 2 3 4 5 1 2 3 4 5
flawless if for all 1 ≤ i < j < k ≤ 5, the sequence ( a , a , a ) is not an arithmetic progression (in thati j korder). Find the number of flawless 5-tuples.
Answer: 20 We do casework on the position of 3.
• If a = 3, then the condition is that 4 must appear after 5 and 2 must appear after 1. It is easyto check there are six ways to do this.1
• If a = 3, then there are no solutions; since there must be an index i ≥ 3 with a = 6 − a .
2 i 1
• If a = 3, then 3 we must have {{ a , a } , { a , a }} = {{ 1 , 5 } , { 2 , 4 }} . It’s easy to see there are
3 1 2 4 5
2 = 8 such assignments.3
• The case a = 3 is the same as a = 3, for zero solutions.
4 2
• The case a = 3 is the same as a = 3, for six solutions.
5 1
Hence, the total is 6 + 8 + 6 = 20.