Maths Olympiad Prep

Library / /345 of 348

Algebra Difficulty 5.3 AIME, harder Find the answer

Determine the largest integer nn such that there exist monic quadratic polynomials p1(x),p2(x),p3(x)p_{1}(x), p_{2}(x), p_{3}(x) with integer coefficients so that for all integers i[1,n]i \in[1, n] there exists some j[1,3]j \in[1,3] and mZm \in \mathbb{Z} such that pj(m)=ip_{j}(m)=i.

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

Solution

The construction for n=9n=9 can be achieved with the polynomials x2+x+1,x2+x+2x^{2}+x+1, x^{2}+x+2, and x2+5x^{2}+5. First we consider what kinds of polynomials we can have. Let p(x)=(x+h)2+kp(x)=(x+h)^{2}+k. hh is either an integer or half an integer. Let k=0k=0. If hh is an integer then p(x)p(x) hits the perfect squares 0,1,4,90,1,4,9, etc. If hh is half an integer, then let k=1/4k=1 / 4. Then p(x)p(x) hits the product of two consecutive integers, i.e. 0, 2,6,122,6,12, etc. Assume there is a construction for n=10n=10. In both of the cases above, the most a polynomial can hit out of 10 is 4, in the 0,1,4,90,1,4,9 case. Thus p1p_{1} must hit 1,2,5,101,2,5,10, and p2p_{2} and p3p_{3} hit 3 integers each, out of 3,4,6,7,8,93,4,6,7,8,9. The only ways we can hit 3 out of 7 consecutive integers is with the sequences 0,2,60,2,6 or 0,1,40,1,4. The only way a 0,2,60,2,6 works is if it hits 3,5, and 9, which doesn't work since 5 was hit by p2p_{2}. Otherwise, p2p_{2} is 0,1,40,1,4, which doesn't work as p2p_{2} hits 3,4, and 7, and p3p_{3} must hit 6,8, and 9, which is impossible. Thus no construction for n=10n=10 exists.

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.