返回题库

HMMT 十一月 2019 · 冲刺赛 · 第 36 题

HMMT November 2019 — Guts Round — Problem 36

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  1. [20] Let N be the number of sequences of positive integers ( a , a , a , . . . , a ) for which the polynomials
    1 2 3 15
    x − a x + a 2
    i i +1
    each have an integer root for every 1 ≤ i ≤ 15, setting a = a . Estimate N .
    16 1
    ⌊ ⌋
    ( )
    N E2
    An estimate of E will earn 20 min , points.
    E N
解析

英文解析

  1. [20] Let N be the number of sequences of positive integers ( a , a , a , . . . , a ) for which the polynomials
    1 2 3 15
    x − a x + a 2
    i i +1
    each have an integer root for every 1 ≤ i ≤ 15, setting a = a . Estimate N .
    16 1
    ⌊ ⌋
    ( )
    N E2
    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 cani +1 i i +1 i idecrease is decreasing by 1.
    As it cannot decrease that quickly, we will make the assumption that if a ≥ 10, a = a − 1, asi i +1 iotherwise it will increase at least above 16 at which point it will take many moves to go back downbelow 10. Write that a → b if b is a possible value of a given a = a . We havei +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 ofsequences by when 8 s occur. By dividing by the number of 8 s 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 wenote 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 a ≥ a − 1 = ⇒ a ≥ a − 14 .1
    i +1 i 15 1
    Also, since a > a , a ≥ 2 a − 4, giving
    1 15 1 15
    a + 4
    a − 14 ≤ = ⇒ a ≤ 32 .1
    1 1
    We then construct the following Python code:2
    def p 36(max_val,length):
    L=[[i] for i in range(1,max_val+1)]
    for j in range(length):
    new l=[]
    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:
    new l.append(k+[t])
    L=new lreturn len(L)
    print(p 36(32,15))
    This gives the exact answer of 1409.