AoPS Academy
be the number of spanning trees in a graph 
, where may have multiple edges and loops.
and 
of , let 
, 
, and 
denote the graphs obtained by contracting the edges , , and both and in 
, respectively.![\[
k(G/\{e,f\}) \cdot k(G) \geq k(G/e) \cdot k(G/f)
\]](http://latex.artofproblemsolving.com/3/e/0/3e0c3ddf02ba6a616aaa5cfea247975af6b2ae6d.png)
over the circle in some order so that among any 
successive numbers at least 
numbers are multiplies of 
or 
(or both and ) ?
where a and b are relatively prime integers, what is b − a?
.But then when does equality hold's.
and 
positive real numbers. Prove that
.But then when does equality hold's.
we get equality in the given inequality.
and positive real numbers.Prove that
for all 
; hence 
with the last inequality following from AM-GM. Equality occurs when 
.
![$ P\in R[X]$](http://latex.artofproblemsolving.com/d/6/7/d67db7e6fb626de909cab78c68abbc61b5bcb303.png)
with all positive coefficients.Prove that![\[\frac{1+P(x_{1})^2}{1+P(x_{1}t(x_{1}))}+\frac{1+P(x_{2})^2}{1+P(x_{2}t(x_{2}))}+\cdots+\frac{1+P(x_{n})^2}{1+P(x_{n}t(x_{n}))}\geq n.\]](http://latex.artofproblemsolving.com/2/a/f/2af55eb6915b326649d608cf876d5d90f3dd63fc.png)
,where 
is a permutation of nubers 
.
So the equation turns into
where the last inequality follows from AM-GM and we are done.
-variable inequalities for some reason)
, i.e.
where 
.
such that 
for all 
, we have the inequality
Summing this over all choices of over all choices of 
yields the expansion of the desired inequality, so we are done. 
![$$\sum_{i=1}^n \frac{1+x_i^2}{1+x_ix_{i+1}} \geq n \sqrt[n]{\frac{\prod_{i=1}^n (1+x_i)^2}{\prod_{i=1}^n (1+x_ix_{i+1})}}.$$](http://latex.artofproblemsolving.com/f/e/8/fe87b4ea35058a9a923e298abc2a6491d682f6ae.png)
But just multiply 
cyclically to get the result.
![\[\frac{1+x_{1}^2}{1+x_{1}x_{2}}+\frac{1+x_{2}^2}{1+x_{2}x_{3}}+\cdots+\frac{1+x_{n}^2}{1+x_{n}x_{1}} \ge n \sqrt[n]{\prod_{\text{cyc}} \frac{1+x_{1}^2}{1+x_{1}x_{2}}}\]](http://latex.artofproblemsolving.com/4/d/1/4d1e7ea77a75ded81b602a5e55013338431ce1a9.png)
![\[\prod_{\text{cyc}} \frac{1+x_{1}^2}{1+x_{1}x_{2}} \ge 1\]](http://latex.artofproblemsolving.com/9/b/9/9b98d5cc197d08e4d7f7c74d99b33b3c5bc77fe4.png)
![\[(1+x_i^2)(1+x_{i+1}^2) \ge (1+x_ix_{i+1})^2\]](http://latex.artofproblemsolving.com/4/8/9/489be11d4d3cbc6b5164afa1c391b6cc62809101.png)
which follows from multiplying the Cauchy Schwarz 
cyclically.
By AM-GM, we have that ![$$\text{LHS} \geq n \sqrt[n]{\prod_{i=1}^{n} \frac{1+x_1^2}{1+x_1x_2}},$$](http://latex.artofproblemsolving.com/4/7/5/475e925190e60bbeaa4d74e106d798074f22dc4a.png)
so it suffices to show that 
However, note that by Cauchy-Schwartz 
so multiplying all of these inequalities for 
and then taking the square root yields the desired result. QED
Squaring both sides, and matching, CS finishes.
the following equation :
positive real numbers. Prove that![\[\frac{1+x_{1}^2}{1+x_{1}x_{2}}+\frac{1+x_{2}^2}{1+x_{2}x_{3}}+\cdots+\frac{1+x_{n}^2}{1+x_{n}x_{1}}\geq n.\]](http://latex.artofproblemsolving.com/e/9/e/e9e73a14f4dfa6315e7562998a9394d371847139.png)
.![$$\frac{1+x_{1}^2}{1+x_{1}x_{2}}+\frac{1+x_{2}^2}{1+x_{2}x_{3}}+\cdots+\frac{1+x_{n}^2}{1+x_{n}x_{1}}\geq n\sqrt[n]{\frac{1+x_{1}^2x_2^2}{1+x_{1}x_{2}}\cdot\frac{1+x_{2}^2}{1+x_{2}x_{3}}\cdots\frac{1+x_{n}^2}{1+x_{n}x_{1}}}$$](http://latex.artofproblemsolving.com/c/d/c/cdc2bcd1410605a701c3d8ca3a64436709cd453d.png)
Now, by C-S, we have for all 
(indices are taken modulo 
.
whence we have our desired.
![$$\frac{1+x_{1}^2}{1+x_{1}x_{2}}+\frac{1+x_{2}^2}{1+x_{2}x_{3}}+...+\frac{1+x_{n}^2}{1+x_{n}x_{1}}\geq n\sqrt[n]{\frac{1+x_{1}^2}{1+x_{1}x_{2}}\cdot \frac{1+x_{2}^2}{1+x_{2}x_{3}}\cdots\frac{1+x_{n}^2}{1+x_{n}x_{1}}}\geq n$$](http://latex.artofproblemsolving.com/3/7/3/37383bea956e7f43ea802cc267718e0079d3202b.png)
and 
I think this task inspired Russia MO
![\[\sum\frac{1}{1+x_ix_{i+1}}+\sum\frac{x_i^2}{1+x_ix_{i+1}}\ge n\]](http://latex.artofproblemsolving.com/b/b/6/bb66cd3658b269490fecddef29413eac6e802b08.png)
now apply titu we get:![\[LH \ge \frac{n^2}{n+\sum x_ix_{i+1}}+\frac{\sum x_i^2}{n+\sum x_ix_{i+1}}\ge^? n\]](http://latex.artofproblemsolving.com/b/d/b/bdbf1aaf1b8443068e45662252df1177e4918600.png)
which is obviously true because:![\[\sum \frac{x_i}{2}+\frac{x_{i+1}}{2} \ge \sum x_ix_{i+1}\]](http://latex.artofproblemsolving.com/7/1/a/71ae417ffebfb77b4d741fdba7ca35b8b0a78a59.png)
and 
show that ![\[\sum_{k=1}^n\frac{1+x_k^2}{1+x_kx_{k+1}}\ge n.\]](http://latex.artofproblemsolving.com/9/a/4/9a4243d17e497dbbb0c14f9695ff78e6cb7a1fcd.png)
![\[\sum_{k=1}^n\frac{1+x_k^2}{1+x_kx_{k+1}}\ge\frac12\left(\sum_{k=1}^n\frac{1+x_k^2}{1+x_kx_{k+1}}+\sum_{k=1}^n\frac{1+x_kx_{k+1}}{1+x_{k+1}^2}\right)\ge n.\]](http://latex.artofproblemsolving.com/8/a/a/8aa682a2fd15332173fdfef0a3fb92f3dae1e2e2.png)
such that for any two positive real numbers 
we have: ![\[\frac{1+x^2}{1+xy} \geq \frac{f(x)}{f(y)}\]](http://latex.artofproblemsolving.com/d/3/6/d36acf65cb08e14d8288ea04a1c348c8b7cf8775.png)
Observe that if we suceed in finding such a function 
,![\[[f(y)-f(x)]+x \cdot [xf(y)-yf(x)] \geq 0\]](http://latex.artofproblemsolving.com/e/0/8/e0854ee73ccf6e214e192b2cf2121b976142d4e9.png)
for all positive 
with 
,
and take limits for 
.![\[-f'(y) + yf(y) - y^2f'(y) \geq 0\]](http://latex.artofproblemsolving.com/8/d/7/8d79bc0c0a28f9c7e398415774969cddc10207e9.png)
or that ![\[\frac{y}{1+y^2}\geq \frac{f'(y)}{f(y)}\]](http://latex.artofproblemsolving.com/e/e/5/ee5a0b96b9ad24982d495ac4981d5aa2b494d98e.png)
Assuming equality in the above bound and solving for 
.
for all positive real numbers 
works and we're done.
![\begin{align*}
\frac{1+x_{1}^2}{1+x_{1}x_{2}}+\frac{1+x_{2}^2}{1+x_{2}x_{3}}+\cdots+\frac{1+x_{n}^2}{1+x_{n}x_{1}} \geq n\sqrt[n]{\dfrac{\left(1+x_1^2\right)\left(1+x_2^2\right)\cdots \left(1+x_n^2\right)}{\left(1+x_1x_2\right)\left(1+x_2x_3\right)\cdots\left(1+x_nx_1\right)}}
\end{align*}](http://latex.artofproblemsolving.com/c/0/e/c0ebc3c6ea51d9627d8a8d1992cf5ad90b9408f9.png)
So, we want to show
Notice,
which is clearly true by AM-GM. Multiplying cyclically yields the desired result.
.