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"
 
(2 intermediate revisions by 2 users not shown)
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>
  
−
{{solution}}
+
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==
 +
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.
  
 
== See Also ==
 
== See Also ==

Latest revision as of 20:54, 22 November 2023

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.

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=205281"