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 "2016 AIME II Problems/Problem 15"

(Solution)
 
 
(6 intermediate revisions by 4 users not shown)
Line 1: Line 1:
−
For <math>1 \leq i \leq 215</math> let <math>a_i = \dfrac{1}{2^{i}}</math> and <math>a_216 = \dfrac{1}{2^{215}}</math>. Let <math>x_1, x_2, ..., x_215</math> be positive real numbers such that <math>\sum_{i=1}^{215} x_i=1</math> and <math>\sum_{i \leq i < j \leq 216 x_ix_j = \dfrac{107}{215} + \sum_{i=1}^{216} \dfrac{a_i x_i^{2}}{2(1-a_i)}. The maximum possible value of </math>x_2=\dfrac{m}{n}<math>, where </math>m<math> and </math>n<math> are relatively prime positive integers. Find </math>m+n<math>.
+
==Problem==
 +
For <math>1 \leq i \leq 215</math> let <math>a_i = \dfrac{1}{2^{i}}</math> and <math>a_{216} = \dfrac{1}{2^{215}}</math>. Let <math>x_1, x_2, ..., x_{216}</math> be positive real numbers such that <math>\sum_{i=1}^{216} x_i=1</math> and <math>\sum_{1 \leq i < j \leq 216} x_ix_j = \dfrac{107}{215} + \sum_{i=1}^{216} \dfrac{a_i x_i^{2}}{2(1-a_i)}</math>. The maximum possible value of <math>x_2=\dfrac{m}{n}</math>, where <math>m</math> and <math>n</math> are relatively prime positive integers. Find <math>m+n</math>.
  
 
==Solution==
 
==Solution==
−
Replace </math>\sum x_ix_j<math> with </math>\frac12\left(\left(\sum x_i\right)^2-\sum x_i^2\right)<math> and the second equation becomes </math>\sum\frac{x_i^2}{1-a_i}=\frac{1}{215}<math>. Conveniently, </math>\sum 1-a_i=215<math> so we get </math>\left(\sum 1-a_i\right)\left(\sum\frac{x_i^2}{1-a_i}\right)=1=\left(\sum x_i\right)^2<math>. This is the equality case of Cauchy so </math>x_i=c(1-a_i)<math> for some constant </math>c<math>. Using </math>\sum x_i=1<math>, we find </math>c=\frac{1}{215}<math> and thus </math>x_2=\frac{3}{860}$.
+
Note that
 +
<cmath>\begin{align*}\sum_{1 \leq i < j \leq 216} x_ix_j &= \frac12\left(\left(\sum_{i=1}^{216} x_i\right)^2-\sum_{i=1}^{216} x_i^2\right)\\&=\frac12\left(1-\sum x_i^2\right).\end{align*}</cmath>
 +
Substituting this into the second equation and collecting <math>x_i^2</math> terms, we find
 +
<cmath>\sum_{i=1}^{216}\frac{x_i^2}{1-a_i}=\frac{1}{215}.</cmath> Conveniently, <math>\sum_{i=1}^{216} 1-a_i=215</math> so we find
 +
<cmath>\left(\sum_{i=1}^{216} 1-a_i\right)\left(\sum_{i=1}^{216}\frac{x_i^2}{1-a_i}\right)=1=\left(\sum_{i=1}^{216} x_i\right)^2.</cmath> This is the equality case of the Cauchy-Schwarz Inequality, so <math>x_i=c(1-a_i)</math> for some constant <math>c</math>. Summing these equations and using the facts that <math>\sum_{i=1}^{216} x_i=1</math> and <math>\sum_{i=1}^{216} 1-a_i=215</math>, we find <math>c=\frac{1}{215}</math> and thus <math>x_2=c(1-a_2)=\frac{1}{215}\cdot \left(1-\frac{1}{4}\right)=\frac{3}{860}</math>. Hence the desired answer is <math>860+3=\boxed{863}</math>.
 +
 
 +
 
 +
==Video Solution==
 +
https://youtu.be/mjtM-Coav4k
 +
 
 +
~MathProblemSolvingSkills.com
 +
 
 +
 
 +
==See Also==
 +
{{AIME box|year=2016|n=II|num-b=14|after=Last Question}}
 +
{{MAA Notice}}

Latest revision as of 19:02, 19 April 2023

Problem

For $1 \leq i \leq 215$ let $a_i = \dfrac{1}{2^{i}}$ and $a_{216} = \dfrac{1}{2^{215}}$. Let $x_1, x_2, ..., x_{216}$ be positive real numbers such that $\sum_{i=1}^{216} x_i=1$ and $\sum_{1 \leq i < j \leq 216} x_ix_j = \dfrac{107}{215} + \sum_{i=1}^{216} \dfrac{a_i x_i^{2}}{2(1-a_i)}$. The maximum possible value of $x_2=\dfrac{m}{n}$, where $m$ and $n$ are relatively prime positive integers. Find $m+n$.

Solution

Note that \begin{align*}\sum_{1 \leq i < j \leq 216} x_ix_j &= \frac12\left(\left(\sum_{i=1}^{216} x_i\right)^2-\sum_{i=1}^{216} x_i^2\right)\\&=\frac12\left(1-\sum x_i^2\right).\end{align*} Substituting this into the second equation and collecting $x_i^2$ terms, we find \[\sum_{i=1}^{216}\frac{x_i^2}{1-a_i}=\frac{1}{215}.\] Conveniently, $\sum_{i=1}^{216} 1-a_i=215$ so we find \[\left(\sum_{i=1}^{216} 1-a_i\right)\left(\sum_{i=1}^{216}\frac{x_i^2}{1-a_i}\right)=1=\left(\sum_{i=1}^{216} x_i\right)^2.\] This is the equality case of the Cauchy-Schwarz Inequality, so $x_i=c(1-a_i)$ for some constant $c$. Summing these equations and using the facts that $\sum_{i=1}^{216} x_i=1$ and $\sum_{i=1}^{216} 1-a_i=215$, we find $c=\frac{1}{215}$ and thus $x_2=c(1-a_2)=\frac{1}{215}\cdot \left(1-\frac{1}{4}\right)=\frac{3}{860}$. Hence the desired answer is $860+3=\boxed{863}$.


Video Solution

https://youtu.be/mjtM-Coav4k

~MathProblemSolvingSkills.com


See Also

2016 AIME II (Problems • Answer Key • Resources)
Preceded by
Problem 14 		Followed by
Last Question
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME 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=2016_AIME_II_Problems/Problem_15&oldid=192325"