Maths Olympiad Prep

Library / /334 of 348

Algebra Difficulty 5.2 AIME, harder Find the answer

Let NN be the number of sequences of positive integers (a1,a2,a3,,a15)\left(a_{1}, a_{2}, a_{3}, \ldots, a_{15}\right) for which the polynomials x2aix+ai+1x^{2}-a_{i} x+a_{i+1} each have an integer root for every 1i151 \leq i \leq 15, setting a16=a1a_{16}=a_{1}. Estimate NN. An estimate of EE will earn 20min(NE,EN)2\left\lfloor 20 \min \left(\frac{N}{E}, \frac{E}{N}\right)^{2}\right\rfloor points.

A number or a short expression. Spacing and $ signs are ignored.

Solution

We note that ai+1=x(aix)a_{i+1}=x\left(a_{i}-x\right) for some positive integer xx, so ai+1ai1a_{i+1} \geq a_{i}-1. So, the only way aia_{i} can decrease is decreasing by 1. As it cannot decrease that quickly, we will make the assumption that if ai10,ai+1=ai1a_{i} \geq 10, a_{i+1}=a_{i}-1, as otherwise it will increase at least above 16 at which point it will take many moves to go back down below 10. Write that aba \rightarrow b if bb is a possible value of ai+1a_{i+1} given a=aia=a_{i}. We have 56,65,8,9,76,87,985 \rightarrow 6,6 \rightarrow 5,8,9,7 \rightarrow 6,8 \rightarrow 7,9 \rightarrow 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,84,7,8 steps, and 9 can in 6,10,126,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 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 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 a1a_{1} maximal; we have ai+1ai1a15a114a_{i+1} \geq a_{i}-1 \Longrightarrow a_{15} \geq a_{1}-14 Also, since a1>a15,a12a154a_{1}>a_{15}, a_{1} \geq 2 a_{15}-4, giving a114a1+42a132a_{1}-14 \leq \frac{a_{1}+4}{2} \Longrightarrow a_{1} \leq 32 We then construct the following Python code: This gives the exact answer of 1409.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.