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 that i j k order). 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 that i j k order). 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 easy 1 to check there are six ways to do this. • 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 3 2 = 8 such assignments. • 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.