PUMaC 2020 · 团队赛 · 第 12 题
PUMaC 2020 — Team Round — Problem 12
题目详情
- Given a sequence a , a , a , . . . , a , let its arithmetic approximant be the arithmetic sequence 0 1 2 n n ∑ 2 b , b , . . . , b that minimizes the quantity ( b − a ) , and denote this quantity the sequence’s 0 1 n i i i =0 anti-arithmeticity . Denote the number of integer sequences whose arithmetic approximant is the sequence 4 , 8 , 12 , 16 and whose anti-arithmeticity is at most 20 .
解析
- Given a sequence a , a , a , . . . , a , let its arithmetic approximant be the arithmetic sequence 0 1 2 n n ∑ 2 b , b , . . . , b that minimizes the quantity ( b − a ) , and denote this quantity the sequence’s 0 1 n i i i =0 anti-arithmeticity . Denote the number of integer sequences whose arithmetic approximant is the sequence 4 , 8 , 12 , 16 and whose anti-arithmeticity is at most 20 . Proposed by: Frank Lu Answer: 15 First, we find a formula for the anti-arithmeticity for a sequence a , a , a , a , as well to find 0 1 2 3 what the arithmetic sequence should be. Suppose we have arithmetic sequence a − 3 d, a − 3 ∑ 2 d, a + d, a + 3 d. Then, we see that the value of ( a + (2 i − 3) d − a ) can be evaluated to i i =0 2 2 equal 4 a + 20 d − 2( a + a + a + a ) a − 0 1 2 3 a + a + a + a 2 2 2 2 2 0 1 2 3 (6 a +2 a − 2 a − 6 a ) d + a + a + a + a . We can re-write this as equal to 4( a − ) + 3 2 1 0 0 1 2 3 4 a + a + a + a 3 a + a − a − 3 a 3 a + a − a − 3 a 2 2 2 2 2 2 2 0 1 2 3 3 2 1 0 3 2 1 0 a + a + a + a − 4( ) − 20( d − ) − 20( ) . We 0 1 2 3 4 20 20 a + a + a + a 2 2 2 2 2 0 1 2 3 see then that the minimal value of this is equal to a + a + a + a − 4( ) − 0 1 2 3 4 3 a + a − a − 3 a 2 3 2 1 0 20( ) . 20 There are two ways to continue. Either through algebraic manipulation or via linear algebra arguments with orthogonal vectors (1 , − 1 , − 1 , 1) and (1 , − 3 , 3 , − 1) , we see that this is equal 2 2 to ( a − a − a + a ) / 4 + ( a − 3 a + 3 a − a ) / 20 . 3 2 1 0 3 2 1 0 Now, note that we are given that a + a + a + a = 40 , 3 a + a − a − 3 a = 40 . But we 0 1 2 3 3 2 1 0 see that that the anti-arithmeticity needs to be an integer. But let a − 3 a + 3 a − a = s, 3 2 1 0 and let a − a − a + a = t. We can then see that a + a = 20 + t/ 2 , a − a = 12 + s/ 10 , 3 2 1 0 0 3 3 0 and similarly we see that a + a = 20 − t/ 2 , a − a = 4 − 3 s/ 10 , which requires us to have 1 2 2 1 s divisible by 10 , and t divisible by 2 , and s/ 10 , t/ 2 to have the same parity. We make the 2 2 substitution s/ 10 = a, t/ 2 = b to get that our anti-arithmeticity value is just a + 5 b , with a, b having the same parity. For the values to be at most 20 , we can just enumerate: (0 , 0) , (0 , ± 2) , ( ± 1 , ± 1) , ( ± 2 , 0) , ( ± 3 , ± 1) , ( ± 4 , 0) . The total number of pairs: 1 + 2 + 4 + 2 + 4 + 2 = 15 .