HMMT 十一月 2019 · 冲刺赛 · 第 36 题
HMMT November 2019 — Guts Round — Problem 36
题目详情
- [20] Let N be the number of sequences of positive integers ( a , a , a , . . . , a ) for which the polynomials 1 2 3 15 2 x − a x + a i i +1 each have an integer root for every 1 ≤ i ≤ 15, setting a = a . Estimate N . 16 1 ⌊ ⌋ ( ) 2 N E An estimate of E will earn 20 min , points. E N
解析
- [20] Let N be the number of sequences of positive integers ( a , a , a , . . . , a ) for which the polynomials 1 2 3 15 2 x − a x + a i i +1 each have an integer root for every 1 ≤ i ≤ 15, setting a = a . Estimate N . 16 1 ⌊ ⌋ ( ) 2 N E An estimate of E will earn 20 min , points. E N Proposed by: Krit Boonsiriseth Answer: 1409 We note that a = x ( a − x ) for some positive integer x , so a ≥ a − 1. So, the only way a can i +1 i i +1 i i decrease is decreasing by 1. As it cannot decrease that quickly, we will make the assumption that if a ≥ 10, a = a − 1, as i i +1 i otherwise it will increase at least above 16 at which point it will take many moves to go back down below 10. Write that a → b if b is a possible value of a given a = a . We have i +1 i 5 → 6 , 6 → 5 , 8 , 9 , 7 → 6 , 8 → 7 , 9 → 8 , and in addition by going to 10 and above, 7 can go to 9 in 2 or 4 steps, 8 can in 4 , 7 , 8 steps, and 9 can in 6 , 10 , 12 steps. We see from this that the vast majority of sequences should pass through 8. By looking at cycles from 8, we can determine exactly when a sequence can start at 8 and return to 8 (there is one way in 3 steps, two in 4 steps, etc.), and from there we can generate a list of types of sequences by when 8s occur. By dividing by the number of 8s and multiplying by 15, we can get the number of sequences that include 8, which gives us an estimate of 1235, giving us 15 points. As we note that this is a lower estimate, we may round up slightly to get better results. To find the exact answer, we will first show that no element larger than 32 can occur in the sequence. Reorder the sequence to make a maximal; we have 1 a ≥ a − 1 = ⇒ a ≥ a − 14 . i +1 i 15 1 Also, since a > a , a ≥ 2 a − 4, giving 1 15 1 15 a + 4 1 a − 14 ≤ = ⇒ a ≤ 32 . 1 1 2 We then construct the following Python code: def p36(max_val,length): L=[[i] for i in range(1,max_val+1)] for j in range(length): newL=[] for k in L: poss=[x*(k[-1]-x) for x in range(1,k[-1]//2+1)] for t in poss: if 1<=t<=max_val: newL.append(k+[t]) L=newL return len(L) print(p36(32,15)) This gives the exact answer of 1409.