Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1984 USAMO Problems/Problem 5"
Line 11: Line 11:
  
 
== Solution ==
 
== Solution ==
 +
By Lagrange Interpolation Formula <math>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 )</math>
  
 +
and hence <math>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 )</math>
 +
 +
after some calculations we get <math>f(3n+1) =\left ( \binom{3n+1}{0}- \binom{3n+1}{3}+\binom{3n+1}{6}- ... \right )\left ( 2.(-1)^{3n}-1 \right )+1</math>
 +
 +
Given <math>f(3n+1)= 730</math> so we have to find <math>n</math> such that <math>\left ( \binom{3n+1}{0}- \binom{3n+1}{3}+\binom{3n+1}{6}- ... \right )\left ( 2.(-1)^{3n}-1 \right )= 729</math>
 +
 +
Lemma: If <math>p</math> is even  <math>\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}</math>
 +
 +
and if  <math>p</math> is odd  <math>\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}</math>
 +
 +
<math>i</math> is <math>\sqrt{-1}</math>
 +
Using above lemmas we do not get any solution when <math>n</math> is odd, but when <math>n</math> is even <math>3n+1=13 </math> satisfies the required condition, hence <math>n=4</math>
 
{{solution}}
 
{{solution}}
  

Revision as of 11:15, 22 April 2018

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$ This problem needs a solution. If you have a solution for it, please help us out by adding it.

See Also

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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1984_USAMO_Problems/Problem_5&oldid=94118"