1984 USAMO Problems/Problem 5

Problem

$P(x)$ is a polynomial of degree $3n$ such that

$\begin{eqnarray*} P(0) = P(3) = \cdots &=& P(3n) = 2, \\ P(1) = P(4) = \cdots &=& P(3n-2) = 1, \\ P(2) = P(5) = \cdots &=& P(3n-1) = 0, \quad\text{ and }\\ && P(3n+1) = 730.\end{eqnarray*}$

Determine $n$ .

Solution

By Lagrange Interpolation Formula $f(x) = 2\sum_{p=0}^{n}\left ( \prod_{0\leq r\neq3p\leq 3n}^{{}}\frac{x-r}{3p-r} \right )+ \sum_{p=1}^{n}\left ( \prod_{0\leq r\neq3p-2\leq 3n}^{{}} \frac{x-r}{3p-2-r}\right )$

and hence $f(3n+1) = 2\sum_{p=0}^{n}\left ( \prod_{0\leq r\neq3p\leq 3n}^{{}}\frac{3n+1-r}{3p-r} \right )+ \sum_{p=1}^{n}\left ( \prod_{0\leq r\neq3p-2\leq 3n}^{{}} \frac{3n+1-r}{3p-2-r}\right )$

after some calculations we get $f(3n+1) =\left ( \binom{3n+1}{0}- \binom{3n+1}{3}+\binom{3n+1}{6}- ... \right )\left ( 2.(-1)^{3n}-1 \right )+1$

Given $f(3n+1)= 730$ so we have to find $n$ such that $\left ( \binom{3n+1}{0}- \binom{3n+1}{3}+\binom{3n+1}{6}- ... \right )\left ( 2.(-1)^{3n}-1 \right )= 729$

Lemma: If $p$ is even $\binom{p}{0}- \binom{p}{3}+ \binom{p}{6}- \cdots = \frac{2^{p+1}sin^{p}\left ( \frac{\pi}{3} \right )(i)^{p}\left ( cos\left ( \frac{p\pi}{3} \right ) \right )}{3}$

and if $p$ is odd $\binom{p}{0}- \binom{p}{3}+ \binom{p}{6}- \cdots = \frac{-2^{p+1}sin^{p}\left ( \frac{\pi}{3} \right )(i)^{p+1}\left ( sin\left ( \frac{p\pi}{3} \right ) \right )}{3}$

$i$ is $\sqrt{-1}$ Using above lemmas we do not get any solution when $n$ is odd, but when $n$ is even $3n+1=13$ satisfies the required condition, hence $n=4$

Solution

The (3n+1)th differences of the polynomial are zero. Call it p(x), so we have p(3n+1) - (3n+1)C1 p(3n) + (3n+1)C2 p(3n-1) - ... + (-1)3n+1 p(0) = 0, where rCs is the binomial coefficient. Hence p(3n+1) = 2( (3n+1)C1 - (3n+1)C4 + ... ) + ( (3n+1)C3 - (3n+1)C6 + ... ). Putting n = 1, we get: p(4) = 2( 4C1 - 4C4) + 4C3 = 6 + 4 = 10. So n is not 1. Putting n = 2, we get: p(7) = 2( 7C1 - 7C4 + 7C7) + ( 7C3 - 7C6) = 2( 7 - 35 + 1) + (35 - 7) = -26. So n is not 2. Putting n = 3, we get: p(10) = 2( 10C1 - 10C4 + 10C7 - 10C10) + ( 10C3 - 10C6 + 10C9) = 2(10 - 210 + 120 - 1) + (120 - 210 + 10) = -162 -100 = -262. So n is not 3. Putting n = 4, we get: p(13) = 2( 13C1 - 13C4 + 13C7 - 13C10 + 13C13) + ( 13C3 - 13C6 + 13C9 - 13C12) = 2(13 - 715 + 1716 - 286 + 1) + (286 - 1716 + 715 - 13) = 1458 - 728 = 730. So n = 3 works.

1984 USAMO (Problems • Resources)
Preceded by Problem 4	Followed by Last Question
1 • 2 • 3 • 4 • 5
All USAMO Problems and Solutions

Page

Toolbox

Search

1984 USAMO Problems/Problem 5

Contents

Problem

Solution

Solution

See Also