Maths Olympiad Prep

Library / /14 of 30

Number theory Difficulty 5.8 AIME, harder Find the answer Italy

Problem:

Let p(x)p(x) be a polynomial with integer coefficients such that p(0)=6p(0)=6. It is known that among the integers mm between 1 and 60 exactly 40 are such that p(m)p(m) is a multiple of 3; moreover, it is known that among the integers mm between 1 and 60 exactly 30 are such that p(m)p(m) is a multiple of 4. How many integers mm between 1 and 60 are there such that p(m)p(m) is a multiple of 6? Note: all intervals appearing in this problem are to be considered with endpoints included.

Pick one

Solution

Solution:

The answer is (E)\mathbf{(E)}. To prove it, we want to show that p(m)p(m) is even for every integer mm, and that consequently p(m)p(m) is a multiple of 6 if and only if it is a multiple of 3. At this point we can use the hypothesis that the integers mm for which p(m)p(m) is a multiple of 3 are precisely 40 to obtain the answer.

Let us first observe that the parity of p(m)p(m) depends only on the parity of mm: indeed the parity of a monomial amka \cdot m^{k} depends only on the parities of mm and of aa, and the parity of the value of p(m)p(m), which is a sum of monomials in mm, depends only on the parity of each addend. It is therefore sufficient to show that p(m)p(m) is even for at least one even value and for at least one odd value of mm. By hypothesis p(0)=6p(0)=6, so it remains to show the existence of an odd value of mm for which p(m)p(m) is even. We can write p(x)=xq(x)+6p(x)=x \cdot q(x)+6, where q(x)q(x) is a polynomial with integer coefficients. If mm is a multiple of 4, say m=4km=4k, then p(m)=4kq(4k)+6p(m)=4k \cdot q(4k)+6 is not a multiple of 4 (it gives remainder 2 upon division by 4). By hypothesis, there are 30 integers between 1 and 60 such that p(m)p(m) is a multiple of 4; since the mm that are multiples of 4 do not have this property, and the mm that are even but not multiples of 4 are only 15, there must exist odd integers such that p(m)p(m) is even.

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: MathNet, licensed CC-BY-4.0. Statement translated into English from it; metadata (topic, difficulty) added by this project.