Putnam 2003 A2

Art of Problem Solving

AoPS Online

College Math Topics in undergraduate and graduate studies

Topics in undergraduate and graduate studies

3 M G

BBookmark VNew Topic kLocked

College Math Topics in undergraduate and graduate studies

Topics in undergraduate and graduate studies

3 M G

BBookmark VNew Topic kLocked

w

1 user

TOPICS

No tags match your search

M

No tags match your search

M

Putnam 2003 A2

G H J

Reveal topic tags

college contests

Putnam inequalities

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

439 posts

#1 h Jun 22, 2011, 11:55 PM • 1 Y

Y by Adventure10

Let $a_1, a_2, \cdots , a_n$ and $b_1, b_2,\cdots, b_n$ be nonnegative real numbers. Show that $(a_1a_2 \cdots a_n)^{1/n}+ (b_1b_2 \cdots b_n)^{1/n} \le ((a_1 + b_1)(a_2 + b_2) \cdots (a_n + b_n))^{1/n}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Kent Merryfield

18574 posts

Kent Merryfield

#2 h Jun 23, 2011, 12:30 AM • 5 Y

Y by mathman523, vsamc, GoodPerson, Adventure10, Sagnik123Biswas

More from my old document:

To start with, if any of these numbers is zero, one of the quantities on the left hand side is zero and the right hand side is clearly larger than the other side. So assume that all of the $a$ ’s and $b$ ’s are positive. For each $i, 1 \le i \le n,$ let $s_i = a_i + b_i.$ Let $\alpha_i = \frac{a_i}{s_i}$ and $\beta_i = \frac{b_i}{s_i} .$ Note that $\alpha_i + \beta_i = 1$ for all $i.$ Divide both sides of the inequality by $(s_1s_2\cdots s_n)^{1/n}.$ The result is that our inequality is equivalent to $(\alpha_1\alpha_2\cdots\alpha_n)^{1/n} + (\beta_1\beta_2\cdots\beta_n)^{1/n} \le 1.$ The arithmetic mean-geometric mean inequality (AM-GM inequality) now shows that $(\alpha_1\alpha_2\cdots\alpha_n)^{1/n} \le \frac{\alpha_1 + \alpha_2 + \cdots + \alpha_n}n$ and that $(\beta_1\beta_2\cdots\beta_n)^{1/n} \le\frac{\beta_1 + \beta_2 + \cdots + \beta_n}n .$ So,
$(\alpha_1\alpha_2\cdots\alpha_n)^{1/n} + (\beta_1\beta_2\cdots\beta_n)^{1/n} \le \frac{\alpha_1 + \beta_1 + \alpha_2 + \beta_2 + \cdots + \alpha_n + \beta_n}n$ $= \frac{n}{n} = 1$ and we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

109 posts

#3 h Jul 28, 2011, 5:51 PM • 2 Y

Y by Adventure10, Mango247

It seems trivial using Holder's extended inequality

see http://www.artofproblemsolving.com/Resources/Papers/MildorfInequalities.pdf

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

803 posts

#4 h Aug 1, 2013, 6:22 PM • 1 Y

Y by Adventure10

if any of $a_1,...,a_n,b_1,....b_n$ is zero , then the inequality is trivial.so , consider the case that all of them are positive.
let $a_i=x_i^n$ , $b_i=y_i^n$ .math=inline]$x_1,...,x_n ,y_1,...,y_n$[/math] are all [math=inline]$>0$[/math
then the inequality is equivalent to showing that,
$\prod{[x_i^n+y_i^n]} \ge (x_1x_2...x_n+y_1y_2....y_n)^n$
now , we use the following lemma--
Lemma-- $(p_1^n+1)......(p_n^n+1) \ge (p_1p_2....p_n+1)^n$ where all $p_i$ 's are positive.
proof of the lemma--
let $p_1p_2...p_n+1=t$ .
then by weighted AM-GM ,
we get $p_i^n+1=\frac{p_i^n}{t-1}.(t-1)+1 \ge t[\frac{p_i^{n(t-1)}}{(t-1)^{t-1}}]^{1/t}$
and the rest is trivial.

end of proof of lemma

now putting $p_i=\frac{x_i}{y_i}$ for all $i=1,2,..,n$ and we get the desired inequality

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

42527 posts

sqing

#5 h Aug 13, 2019, 9:10 AM • 1 Y

Y by Adventure10

btilm305 wrote:

Let $a_1, a_2, \cdots , a_n$ and $b_1, b_2,\cdots, b_n$ be nonnegative real numbers. Show that $(a_1a_2 \cdots a_n)^{1/n}+ (b_1b_2 \cdots b_n)^{1/n} \le ((a_1 + b_1)(a_2 + b_2) \cdots (a_n + b_n))^{1/n}$

2019 CGMO P6:
Let $0\leq x_1\leq x_2\leq \cdots \leq x_n\leq 1$ $(n\geq 2).$ Prove that $\sqrt[n]{x_1x_2 \cdots x_n}+ \sqrt[n]{(1-x_1)(1-x_2)\cdots (1-x_n)}\leq \sqrt[n]{1-(x_1- x_n)^2}.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

7938 posts

#6 h Feb 13, 2023, 5:45 PM

Y by

An interesting fact about this problem: this is a special case of the Brunn-Minkowski Inequality.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

248 posts

#7 h Jan 15, 2024, 4:06 AM

Y by

If any of $a_i=0,$ the inequality trivially holds. Similarly for $b_i.$

Hence considering $a_i,b_i>0,$ we will employ $\text{AM-GM}.$ inequality,

Clearly $\frac{\frac{a_1}{a_1+b_1}+\frac{a_2}{a_2+b_2}+\cdots+\frac{a_n}{a_n+b_n}}{n}\le\left(\frac{a_1}{a_1+b_1}\cdot\frac{a_2}{a_2+b_2}\cdots\frac{a_n}{a_n+b_n}\right)^{1/n}$

and, $\frac{\frac{b_1}{a_1+b_1}+\frac{b_2}{a_2+b_2}+\cdots+\frac{b_n}{a_n+b_n}}{n}\le\left(\frac{b_1}{a_1+b_1}\cdot\frac{b_2}{a_2+b_2}\cdots\frac{b_n}{a_n+b_n}\right)^{1/n}.$

Adding both of them we get $1\le\left(\frac{(a_1a_2 \cdots a_n)^{1/n}+ (b_1b_2 \cdots b_n)^{1/n}}{(a_1 + b_1)(a_2 + b_2) \cdots (a_n + b_n))^{1/n}}\right).$

And hence this along with the trivial case gives us the desired inequality. $\quad\blacksquare$

This post has been edited 1 time. Last edited by twbnrftw, Jan 15, 2024, 4:07 AM
Reason: typo

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Sagnik123Biswas

421 posts

Sagnik123Biswas

#8 h Jan 23, 2024, 1:33 PM

Y by

It suffices to execute a set of reversible steps. First let us raise both sides to the $n^{th}$ power. We obtain the following: $\sum_{k=0}^{n}\binom{n}{k}(a_1a_2a_3 \dots a_n)^{\frac{k}{n}}(b_1b_2b_3 \dots b_n)^{\frac{n-k}{n}} \leq (a_1 + b_1)(a_2+b_2)(a_3+b_3) \dots (a_n + b_n)$ .

Now let us define $S_k$ to be the part of the expansion of $(a_1 + b_1)(a_2+b_2)(a_3+b_3) \dots (a_n + b_n)$ which contains $k$ terms of the form " $a_i$ " and $n-k$ terms of the form " $b_i$ ". It then follows that $(a_1 + b_1)(a_2+b_2)(a_3+b_3) \dots (a_n + b_n) = \sum_{k=0}^{n}S_k$ . So it suffices to show that $S_k \geq \binom{n}{k}(a_1a_2a_3 \dots a_n)^{\frac{k}{n}}(b_1b_2b_3 \dots b_n)^{\frac{n-k}{n}}$ .

Next, we define $P_k$ to be the product of all terms in the expansion of $(a_1 + b_1)(a_2+b_2)(a_3+b_3) \dots (a_n + b_n)$ which contain $k$ terms of the form " $a_i$ " and $n-k$ terms of the form " $b_i$ ". By the $AM-GM$ inequality, we know that $S_k \geq \binom{n}{k}(P_k)^{\frac{1}{\binom{n}{k}}}$ .

If we are able to show that $\binom{n}{k}(P_k)^{\frac{1}{\binom{n}{k}}} = \binom{n}{k}(a_1a_2a_3 \dots a_n)^{\frac{k}{n}}(b_1b_2b_3 \dots b_n)^{\frac{n-k}{n}}$ , then we should be done. Observe that $(P_k)^{\frac{1}{\binom{n}{k}}} = (a_1a_2a_3 \dots a_n) ^ { \frac{\binom{n-1}{k-1}}{\binom{n}{k}}} (b_1b_2b_3 \dots b_n) ^ { \frac{\binom{n-1}{k}}{\binom{n}{k}}}$ . The reason this holds is that each $a_i$ appears in $\binom{n-1}{k-1}$ different terms of the expansion and likewise each $b_i$ appears in $\binom{n-1}{k}$ terms of the expansion.

Simplifying $P_k$ , we see that $\frac{\binom{n-1}{k-1}}{\binom{n}{k}} = \frac{(n-1)!}{(n-k)!(k-1)!} \times \frac{k!(n-k)!}{n!} = \frac{k}{n}$ . By Pascal's Identity, it must follow that $\frac{\binom{n-1}{k}}{\binom{n}{k}} = \frac{\binom{n}{k} - \binom{n-1}{k-1}}{\binom{n}{k}} = \frac{n-k}{n}$ . Thus, it is indeed true that $\binom{n}{k}(P_k)^{\frac{1}{\binom{n}{k}}} = \binom{n}{k}(a_1a_2a_3 \dots a_n)^{\frac{k}{n}}(b_1b_2b_3 \dots b_n)^{\frac{n-k}{n}}$ , thereby completing the proof.

This post has been edited 1 time. Last edited by Sagnik123Biswas, Jan 23, 2024, 1:34 PM
Reason: Typo

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

947 posts

#9 h Apr 12, 2024, 3:40 PM • 1 Y

Y by mqoi_KOLA

Easy but cute problem :love:

:love:

By AM GM Inequality,
$\frac{1}{n} \sum_{k=1}^n \frac{a_k}{a_k+b_k} \geq \left( \prod_{k=1}^n \frac{a_k}{a_k+b_k}\right)^{1/n}$ $\frac{1}{n} \sum_{k=1}^n \frac{b_k}{a_k+b_k} \geq \left( \prod_{k=1}^n \frac{b_k}{a_k+b_k}\right)^{1/n}$ Now adding these two inequalities, we have
$1=\frac{1}{n} \sum_{k=1}^n 1 \geq \left( \prod_{k=1}^n \frac{a_k}{a_k+b_k}\right)^{1/n}+\left( \prod_{k=1}^n \frac{b_k}{a_k+b_k}\right)^{1/n}$ This implies the statement to be proved. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

161 posts

KAME06

#10 h Apr 16, 2025, 9:50 PM

Y by

WLOG, if $a_1=0$ , then we must prove $(b_1b_2...b_n)^{1/n} \le ((a_1 + b_1)(a_2 + b_2) \cdots (a_n + b_n))^{1/n} \Leftrightarrow b_1b_2...b_n \le (a_1 + b_1)(a_2 + b_2) \cdots (a_n + b_n)$ , but $LHS$ is $RHS$ 's addend, so the inequality is true
If they are positive reals:
Let $A_k$ the set of all possible products, with $n$ factors, made by $k$ distinct elements from $\{a_1, a_2, ..., a_n \}$ and $n-k$ distinct elements from $\{b_1, b_2, ..., b_n \}$ such there aren't $a, b$ with the same index. There are $\binom{n}{k}$ ways to select $k$ distinct elements from $\{a_1, a_2, ..., a_n \}$ . We can't select same indeces and the product has $n$ factors, so there is $1$ way to select $n-k$ distinct elements from $\{b_1, b_2, ..., b_n \}$ . All of that implies $|A_k|=\binom{n}{k}$ .
Then using MA-MG: $\sum_{x \in A_k} x \ge \binom{n}{k} \sqrt[n]{\left (\prod_{i=1}^{n}a_i \right)^k \left(\prod_{i=1}^{n}b_i \right )^{n-k}}$
$\forall k=1, 2, ..., n$
Now, consider the product $(a_1+b_1)(a_2+b_2)...(a_n+b_n)$ notice that each addend is made by $k$ distinct $a$ 's and $n-k$ distinct $b$ 's, $\forall k=1, 2, ..., n$ . Also, each element of $A_k$ is an addend of $(a_1+b_1)(a_2+b_2)...(a_n+b_n)$ . That implies that $(a_1+b_1)(a_2+b_2)...(a_n+b_n)=\sum_{k=0}^n \sum_{x \in A_k}x$ .
We conclude that, adding all the inequalities we obtained using MA-MG, for $k=0, 1, 2, ..., n$ :
$\sum_{k=0}^n \binom{n}{k} \sqrt[n]{\left (\prod_{i=1}^{n}a_i \right)^k \left(\prod_{i=1}^{n}b_i \right )^{n-k}} \le \sum_{k=0}^n \sum_{x \in A_k}x$ $\Leftrightarrow \sum_{k=0}^n \binom{n}{k} \left (\sqrt[n]{\prod_{i=1}^{n}a_i} \right )^k \left (\sqrt[n]{\prod_{i=1}^{n}b_i}\right )^{n-k} \le (a_1+b_1)(a_2+b_2)...(a_n+b_n)$ $\Leftrightarrow \left (\sqrt[n]{\prod_{i=1}^{n}a_i}+\sqrt[n]{\prod_{i=1}^{n}b_i} \right)^n \le (a_1+b_1)(a_2+b_2)...(a_n+b_n)$ $\Leftrightarrow \left (a_1a_2...a_n \right)^{\frac{1}{n}}+\left(b_1b_2...b_n \right)^{\frac{1}{n}}\le ((a_1+b_1)(a_2+b_2)...(a_n+b_n))^{\frac{1}{n}}$

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a