%%%&latex
\documentclass{article}
\usepackage[T2A]{fontenc}
\usepackage[cp1251]{inputenc}
\usepackage[russian,english]{babel}

\usepackage{amsthm,amsmath,amsfonts,amssymb,epic,eepic, epsf, eucal}
\usepackage[text={17.7cm,10.2in}]{geometry}
\usepackage{mathdots}

\let\le\leqslant
\let\leq\leqslant
\let\ge\geqslant
\let\geq\geqslant
\def\answer{A\,n\,s\,w\,e\,r}
\def\chtd{{\slshape пїЅ\kern-.04em\raise.48ex\hbox{пїЅ}\kern-.23em пїЅ}}
\let\ds\displaystyle

\newcounter{problem}[subsection]
\newcounter{solution}[subsection]
\renewcommand{\thesection}{}
\renewcommand{\thesubsection}{\arabic{subsection}}
\renewcommand{\thesubsubsection}{\arabic{subsection}-\arabic{subsubsection}}
\renewcommand{\theproblem}{\thesubsection.\arabic{problem}}
\renewcommand{\thesolution}{\thesubsection.\arabic{solution}}
\newenvironment{problem}{\refstepcounter{problem}\smallskip\noindent%
{\bf\arabic{subsection}.\arabic{problem}.}}{}
\newenvironment{solution}{\refstepcounter{solution}\medskip\noindent%
{\bf\arabic{subsection}.\arabic{solution}.}}{}

\setlength\multlinegap{0pt}

%%%%%%%%
%
\makeatletter
\long\def\@makecaption#1#2{%
  \vskip 10\p@
  \setbox\@tempboxa\hbox{#1. #2}%
  \ifdim \wd\@tempboxa >\hsize
      \unhbox\@tempboxa\par
    \else
      \centerline{\box\@tempboxa}\fi}
\long\def\@caption#1[#2]#3{\par\addcontentsline{\csname
  ext@#1\endcsname}{#1}{\protect\numberline{\csname
  the#1\endcsname.}{\ignorespaces #2}}\begingroup
    \@parboxrestore
    \footnotesize%\normalsize
    \@makecaption{\csname fnum@#1\endcsname}{\ignorespaces #3}\par
  \endgroup}
%
%
\renewcommand{\subsection}{\@startsection{subsection}{2}{0mm}%
{2\baselineskip}{\baselineskip}{\bfseries\large\itshape}}
\makeatother
%%%%%%%%%

\def\Summa{\sum\limits_{k=1}^n}
\def\summa{\sum\limits_{k=0}^{n-1}}
\def\summal{\sum\limits_{\ell=0}^{n-1}}
\def\summaik{\sum\limits_{i < k}}
\def\eps{\varepsilon}
\def\chtd{{\slshape пїЅ\kern-.04em\raise.48ex\hbox{пїЅ}\kern-.23em пїЅ}}

\def\kratno{\mathchoice{\mathrel{\smash{\lower.5ex\hbox{$\vdots$}}}}%
{\mathrel{\smash{\lower.5ex\hbox{$\vdots$}}}}%
{{\scriptstyle\mathrel{\smash{\lower.5ex\hbox{$\scriptstyle\vdots$}}}}}%
{{\scriptscriptstyle\mathrel{\smash{\lower.5ex\hbox{$\scriptscriptstyle\vdots$}}}}}}

\def\nekratno{\mathchoice{\kern-.03ex\mathrel{\hbox{$\not{\kern.03ex\kratno}$}}}%
{\kern-.03ex\mathrel{\hbox{$\not{\kern.03ex\kratno}$}}}%
{{\scriptstyle\kern-.5ex\mathrel{\hbox{$\scriptstyle\not{\kern.5ex\kratno}$}}}}%
{{\scriptscriptstyle\kern-.35ex\mathrel{\hbox{$\scriptscriptstyle\not{\kern.35ex\kratno}$}}}}}


\begin{document}

\title{Shapiro's inequality}
\author{A. Khrabrov}
\date{The problem was presented by
I.Bogdanov, V.Bugaenko,  G.Chelnokov,
K.Kuyumzhiyan, K.Kokhas, A.Skopenkov}


%\author{}
\date{}

\maketitle

\kern-25pt


\subsection{Shapiro's inequality}


{\small
In October, 1954 the American Mathematical Monthly published the following problem of
Harold Shapiro
\smallbreak
{\it
Prove the following inequality for positive numbers
$x_1$, $x_2$, \dots, $x_n$:
\begin{equation}
\label{shapiro}
\frac{x_1}{x_2+x_3} + \frac{x_2}{x_3+x_4} + \ldots + \frac{x_{n-1}}{x_n+x_1}
+ \frac{x_n}{x_1+x_2} \geq \frac{n}{2} \,,
\end{equation}
the equality holds only if all the denominators are equal.
}

In contrast to, say, ``Kvant'' magazine, it was allowed to publish problems in the Monthly,
which were not solved by the proposer, and the readers had not been informed about this nuance.
This time the situation was exactly like that. The author had a solution
for partial cases $n=3$ and $4$ only.

In the following problems we can replace the condition that all the $x_k$'s are positive
with the condition that all the $x_k$'s are nonnegative and all the denominators are nonzero.
Indeed, if the inequality is proven for positive numbers, then it is not difficult to deduce the inequality
for nonnegative numbers (and nonzero denominators). Let
$$
f(x_1,x_2,\dots,x_n)= \frac{x_1}{x_2+x_3} + \frac{x_2}{x_3+x_4} + \ldots + \frac{x_{n-1}}{x_n+x_1}
+ \frac{x_n}{x_1+x_2}\,.
$$

\par}
\medskip

\begin{problem}
Prove the inequality (\ref{shapiro}) for $n=3$, $4$, $5$, $6$.
\end{problem}

\begin{problem}
Prove that the inequality (\ref{shapiro}) is wrong

a) for $n=20$; \qquad b) for $n=14$; \qquad c) for $n=25$.
\end{problem}

\begin{problem}\label{prbl:1.3}
Prove the inequality (\ref{shapiro}) for monotonic sequences.
\end{problem}

\begin{problem}
\label{prbl n -> n+2}
Prove that if the inequality (\ref{shapiro}) does not hold for $n=m$,
then it does not hold for $n=m+2$.
\end{problem}

\begin{problem}
Prove that if the inequality~(\ref{shapiro}) does not hold for $n=m$, where $m$ is odd,
then it does not hold for all $n>m$.
\end{problem}

\begin{problem}
Prove the inequality~(\ref{shapiro}) for $n=8$, $10$, $12$ and for
$n=7$, $9$, $11$, $13$, $15$, $17$, $19$, $21$, $23$.
Due to the statement of the previous problem it is sufficient
to prove the inequality only for $n=12$ and~$n=23$.
\end{problem}

\begin{problem}
Prove that $f(x_1,x_2,\dots,x_n)+f(x_n,x_{n-1},\dots,x_1)
% = \frac{x_1+x_4}{x_1+x_2} + \frac{x_2+x_5}{x_2+x_3} +
% \ldots + \frac{x_n+x_3}{x_n+x_1}
\geq n \,.$
\end{problem}


\begin{problem}
Assume that the function $f(x_1,x_2,\dots,x_n)$ has a local minimum in the point $(a_1, a_2, \dots, a_n)$,
$a_1$, $a_2$, \dots, $a_n > 0$.

a) Prove that  $f(a_1,a_2,\dots,a_n)=n/2$ if $n$ is even.

b*) Prove the same statement for odd $n$.

c) Use the statements пїЅa) and b) to prove the inequality for $n=7$ and $n=8$.
\end{problem}

\begin{problem}
Prove the inequality
$\displaystyle
f(x_1,x_2,\dots,x_n) \geq c n \,
$
for the following values of the constant $c$:

a) $c=1/4$; \qquad b) $c=\bigl(\sqrt{2}-1\bigr)$; \qquad c) $c=5/12$.
\end{problem}



\subsection{Useful and related inequalities}

{\small
Prove the following inequalities assuming that all the $x_k$'s are positive.
Prove that the constants printed in bold can not be decreased
(for each $n$).
\par}

\begin{problem}
\label{prbl:mordell}
Mordell's inequality.

a) $\ds \biggl( \Summa x_k \biggr)^2 \geq
\mathbf{\text{\bf min} \left\{ \frac{n}{2}, 3 \right\}}\cdot \Summa x_k(x_{k+1}+x_{k+2}) .$


b) Find all $n$-tuples $x_1$, $x_2$, \dots, $x_n$ such that the equality is achieved.

\end{problem}

\begin{problem}
\label{zadacha2.2}
$\ds \biggl( \Summa x_k \biggr)^2 \geq
%\mathbf{\text{\bf min\,} \left\{ \frac{n}{3}, \frac{8}{3} \right\}}\cdot
\mathbf{\text{\bf min}\left\{ \frac{n}{3}, \frac{8}{3} \right\}}\cdot
\Summa x_k(x_{k+1}+x_{k+2}+x_{k+3}) .$
\end{problem}

\begin{problem}
пїЅa) Prove that for $n \leq 8$
$$\displaystyle\frac{x_1}{x_2+x_3+x_4} + \frac{x_2}{x_3+x_4+x_5} + \ldots +
 \frac{x_{n-1}}{x_n+x_1+x_2} + \frac{x_n}{x_1+x_2+x_3} \geq \frac{n}{3} \,.$$

b) For which $n>8$ this inequality is also true?
\end{problem}

\begin{problem}\label{prbl:ginzburg}
$\displaystyle
(x_1 + x_2 + \ldots + x_n)^2 \geq 4 (x_1 x_2 + x_2 x_3 + \ldots
+ x_{n-1} x_n + x_n x_1) \,;\quad n\geq 4.
$
\end{problem}

\begin{problem}
$\ds\Summa \frac{x_k}{x_{k+1}+x_{k+2}} \geq \Summa \frac{x_{k+1}}{x_k+x_{k+1}}$.
\end{problem}


\begin{problem}
$\displaystyle
\frac{x_1}{x_n+x_2} + \frac{x_2}{x_1+x_3} + \ldots +
\frac{x_{n-1}}{x_{n-2}+x_n} + \frac{x_n}{x_{n-1}+x_1} \geq {\mathbf 2} \,; \quad n\geq 4.
$
\end{problem}

\begin{problem}
$\displaystyle
\frac{x_1+x_2}{x_1+x_3} + \frac{x_2+x_3}{x_2+x_4} + \ldots +
   \frac{x_{n-1}+x_n}{x_{n-1}+x_1} + \frac{x_n+x_1}{x_n+x_2} \geq {\mathbf 4} \,;  \quad n\geq 4.
$
\end{problem}


\begin{problem}
\label{prbl:chimedtseren}
%пїЅ) пїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅ, пїЅпїЅпїЅ пїЅб«Ё $x_1$, $x_2$, \dots, $x_n$ --- пїЅпїЅпїЅпїЅпїЅпїЅвҐ«пїЅпїЅпїЅпїЅ пїЅпїЅб«  пїЅ $n \geq 4$, пїЅпїЅ
$\displaystyle
\frac{x_1}{x_n+x_3} + \frac{x_2}{x_1+x_4} + \ldots +
   \frac{x_{n-1}}{x_{n-2}+x_1} + \frac{x_n}{x_{n-1}+x_2} \geq {\mathbf 3} \,; \quad n\geq 4.
$
\end{problem}

\begin{problem}
$ \displaystyle
\frac{x_2+x_3}{x_1+x_4} + \frac{x_3+x_4}{x_2+x_5} + \ldots +
\frac{x_{n}+x_1}{x_{n-1}+x_2} + \frac{x_1+x_2}{x_{n}+x_3} \geq {\mathbf 6} \,; \quad n\geq 6.
$
\end{problem}

\begin{problem}
$ \displaystyle
\frac{x_1+x_2}{x_1+x_4} + \frac{x_2+x_3}{x_2+x_5} + \ldots +
   \frac{x_{2004}+x_1}{x_{2004}+x_3} \geq {\mathbf 6} \,.
$
\end{problem}


\begin{problem}
$\displaystyle
\frac{x_1}{x_n+x_4} + \frac{x_2}{x_1+x_5} + \ldots +
   \frac{x_{n-1}}{x_{n-2}+x_2} + \frac{x_n}{x_{n-1}+x_3} \geq {\mathbf 4} \,,
$
where $n>5$ is even.
\end{problem}

\begin{problem}
\label{prbl:Diananda-62a}
$\displaystyle
\Summa \frac{x_k^2}{x_{k+1}^2 - x_{k+1} x_{k+2} + x_{k+2}^2} \geq
\mathbf{\left[ \frac{n+1}{2} \right]} .
$
\end{problem}


%\clearpage
%\section*{Shapiro's inequality}


\subsection{After the intermediate finish}

\setcounter{subsection}1
\setcounter{problem}9

\begin{problem}
a) Prove that for each $n$ there exists $q_n > 1$, such that for all
real $x_1$, $x_2$,~\dots, $x_n \in [\frac{1}{q_n};q_n]$
the inequality~(\ref{shapiro}) holds.

b*) Is it possible to choose $q > 1$, such that for all integers $n>0$ and for all $x_i \in [\frac{1}{q};q]$
the inequality~(\ref{shapiro}) holds?
\end{problem}


\begin{problem}
Let $S=f(x_1,x_2,\dots,x_n)$ be the left hand side of Shapiro's inequality.
Denote by $a_1$, $a_2$, \dots, $a_n$ the numbers
$x_2/x_1$, $x_3/x_2$, \dots, $x_n/x_{n-1}$, $x_1/x_n$,
arranged in increasing order.

a) Prove that
$S \geq \frac{1}{a_1(1+a_n)}+\frac{1}{a_2(1+a_{n-1})}+\ldots+\frac{1}{a_n(1+a_1)}$;

b) Let
$b_k=
\begin{cases}
\dfrac{1}{a_ka_{n+1-k}}, &a_ka_{n+1-k} \geq 1 \\
\dfrac{2}{a_ka_{n+1-k}+\sqrt{a_ka_{n+1-k}}}, &a_ka_{n+1-k} < 1 .
\end{cases}
$ \ \ \ \
Prove that
$2S \geq b_1+b_2+\ldots+b_n$;

c) Let  $g$ be the maximal convex function that does not exceed both functions
$e^{-x}$ пїЅ $2(e^x+e^{x/2})^{-1}$.
Prove that
$2S \geq g(\ln (a_1a_n))+g(\ln (a_2a_{n-1}))+\ldots+g(\ln (a_na_1)) \geq ng(0)$.

d) Prove that for each $\lambda > g(0)$ there exist a nonnegative integer
$n$ and positive numbers $x_1$, $x_2$,~\dots,
$x_n$, such that $S \leq \lambda n$.
\end{problem}


\clearpage
\section*{Solutions}

\setcounter{subsection}1

\begin{solution}
$\underline{n=3}$.
Let $S=x_1+x_2+x_3$. It is easy to see that the function $f(t)=\frac{t}{S-t}$ is convex on the interval $[0;S)$.
Apply the Jensen inequality to it:
$$
\frac{f(x_1)+f(x_2)+f(x_3)}3\geq f\left(\frac{x_1+x_2+x_3}3\right)=f\left(\frac S3\right)=\frac12.
$$
We are done.

\medskip
$\underline{n=4}$. This inequality is cyclic. Write down the values of $x_i$'s successively at the vertices of a square. Then on each diagonal put an
arrow leading from the smaller value to the greater one. Notice that there is a side of the square with two tails on it. Re-number the $x_i$'s in such a
manner that this side becomes $x_4x_1$. Now we may assume that $x_1\geq x_3$, $x_4\geq x_2$. For the variables with these restrictions
the following inequality is true:
$$
\frac{x_1}{x_2+x_3} + \frac{x_3}{x_4+x_1} \geq \frac{x_1}{x_4+x_3} + \frac{x_3}{x_2+x_1}\,.
$$
Indeed, re-write it in the following way:
$$
x_1\Bigl(\frac{1}{x_2+x_3}-\frac{1}{x_4+x_3}\Bigr) \geq x_3 \Bigl(\frac{1}{x_2+x_1}-\frac{1}{x_4+x_1}\Bigr)\,.
$$
Reduce both hands to a common denominator, cancel $x_4-x_2$ in both hands
(if $x_4-x_2=0$, we already have the equality), and multiply both hands to the product of denominators.
We obtain the evident (since $x_1\geq x_3$) inequality
$$
x_1(x_2+x_1)(x_4+x_1)\geq x_3(x_2+x_3)(x_4+x_3)\,.
$$

Use it to prove Shapiro's inequality:
$$
\frac{x_1}{x_2+x_3} + \frac{x_2}{x_3+x_4} + \frac{x_3}{x_4+x_1} + \frac{x_4}{x_1+x_2} \geq
\frac{x_1}{x_4+x_3} + \frac{x_2}{x_3+x_4} + \frac{x_3}{x_2+x_1} + \frac{x_4}{x_1+x_2} =
\frac{x_1+x_2}{x_3+x_4}+ \frac{x_3+x_4}{x_1+x_2}=a+a^{-1}\geq 2\,.
$$

\medskip
$\underline{n=5}$.
Notice that the function $f(t)=1/(S-t)$ is convex on the interval $[0;S)$.
So we can apply the Jensen inequality with $n=5$:
\begin{equation}
\label{Jensen-5}
a_1f(t_1)+a_2f(t_2)+a_3f(t_3)+a_4f(t_4)+a_5f(t_5)\geq f(a_1t_1+a_2t_2+a_3t_3+a_4t_4+a_5t_5)\,,
\end{equation}
where $a_i\geq 0$, $\sum a_i=1$.
Take $a_i=\frac{x_i}S$, and let $t_i=x_i+x_{i-1}+x_{i-2}$,  $i=1$, \dots, $5$ (we assume that the variables are enumerated cyclically:
$x_0=x_5$, $x_{-1}=x_4$). Then $f(t_i)=\frac1{S-t_i}=\frac1{x_{i+1}+x_{i+2}}$,
and it means that the left-hand side of inequality~(\ref{Jensen-5})
coincides with the left-hand side of Shapiro's inequality.
Now consider the right-hand side of~\ref{Jensen-5}:
$$
\frac1{S-\sum_{i=1}^5 a_it_i} =
\frac1{S-\sum_{i=1}^5 \frac{x_i}S(x_i+x_{i-1}+x_{i-2})}=
\frac S{S^2-\sum_{i=1}^5 x_i(x_i+x_{i-1}+x_{i-2})}.
$$
Open the brackets. It is easy to see that the denominator is the sum of pairwise products of the set of variables $x_i$. Since the initial inequality is
homogeneous, we may assume that $S=x_1+x_2+x_3+x_4+x_5=1$. Now the right-hand side of inequality~(\ref{Jensen-5}) is the inverse number to the
sum of pairwise products of the variables $x_i$, satisfying one condition $x_1+x_2+x_3+x_4+x_5=1$.
The right-hand side reaches its minimum when the sum of pairwise products reaches its maximum. It is well-known that for it all the variables
should be equal. But the right-hand side equals~$5/2$ in this point.

The analogous proof also works for $n=4$.

\medskip
$\underline{n=6}$. Proceed as above.
The function $f(t)=1/(S-t)$ is convex on the interval $[0;S)$.
So we can apply the Jensen inequality with $n=6$:
$$
\label{Jensen-6}
\sum_{i=1}^6 a_i f(t_i)\geq f\Bigl(\sum_{i=1}^6  a_it_i\Bigr).
$$
Let $a_i=\frac{x_i}S$, $t_i=x_i+x_{i-1}+x_{i-2}+x_{i-3}$,  $i=1$, \dots, 6 (we assume that the variables are enumerated cyclically:
$x_0=x_6$, $x_{-1}=x_5$, $x_{-2}=x_4$). Then $f(t_i)=\frac1{S-t_i}=\frac1{x_{i+1}+x_{i+2}}$,
and this means that the left-hand side of the inequality~(\ref{Jensen-6})
coincides with the left-hand side of Shapiro's inequality.
Now consider the right-hand side of~(\ref{Jensen-6}):
$$
\frac1{S-\sum_{i=1}^6 a_it_i} =
\frac1{S-\sum_{i=1}^6 \frac{x_i}S(x_i+x_{i-1}+x_{i-2}+x_{i-3})}=
\frac S{S^2-\sum_{i=1}^6 x_i(x_i+x_{i-1}+x_{i-2}+x_{i-3})}.
$$
Open the brackets. It is easy to see that the denominator is the sum of pairwise products of the variables $x_i$'s but the products $x_1x_4$, $x_2x_5$,
and $x_3x_6$. This sum can be re-written as
$(x_1+x_4)(x_2+x_5)+(x_1+x_4)(x_3+x_6)+(x_2+x_5)(x_3+x_6)$.
Denote $A=x_1+x_4$, $B=x_2+x_5$, $C=x_3+x_6$. The right-hand side of~(\ref{Jensen-6}) can be re-written as
\begin{equation}
\label{eqn1}
\frac{A+B+C}{AB+BC+AC}\,.
\end{equation}
Since the initial inequality is homogeneous, we may assume that $S=x_1+x_2+x_3+x_4+x_5=A+B+C=1$.
Now it is clear that the expression~(\ref{eqn1}) is greater than or equal to 3, since
$(A+B+C)^2\geq 3(AB+BC+AC)$. \chtd

\medskip
R\,e\,m\,a\,r\,k. \, Unfortunately, this method does not work for~$n>6$.

Second solution. Apply the Cauchy-Bunyakovsky inequality to the sets of numbers
\begin{gather*}
\sqrt{\frac{x_1}{x_2+x_3}},\quad \sqrt{\frac{x_2}{x_3+x_4}},\quad  \dots,\quad
\sqrt{\frac{x_n}{x_1+x_2}}\qquad\text{ and}
\\
\sqrt{x_1(x_2+x_3)}, \quad \sqrt{x_2(x_3+x_4)}, \quad \dots,\quad
\sqrt{x_n(x_1+x_2)} \quad .
\end{gather*}
We obtain
$$
\frac{x_1}{x_2+x_3} + \frac{x_2}{x_3+x_4} + \ldots
+ \frac{x_n}{x_1+x_2}\geq
\frac{(x_1+x_2+\ldots+x_n)^2}{x_1(x_2+x_3)+x_2(x_3+x_4)+\ldots+x_n(x_1+x_2)}\,.
$$

Use Mordell's inequality (problem~2.1). When $n\leq 6$, it gives us that the right-hand side of this inequality is greater than or equal to~$n/2$.
\end{solution}

\begin{solution}
a) \cite{Shapiro-Northover} Take as $x_1$, $x_2$, \dots, $x_{20}$ numbers
\begin{align*}
&1+5\eps,\! &&6\eps,\!\! &&1+4\eps, &&5\eps,\! &&1+3\eps, &&4\eps, &&1+2\eps, &&3\eps, &&1+\eps, &&2\eps, \\
&1+2\eps,\! &&\eps, &&1+3\eps, &&2\eps,\! &&1+4\eps, &&3\eps, &&1+5\eps, &&4\eps, &&1+6\eps,\!\! &&5\eps.
\end{align*}
Then $f(x_1,\dots,x_{20})<10-\eps^2+c\eps^3<10$ for some $c$ and small enough $\eps$.
 
\smallskip
b) \cite{Zulauf} Take as $x_1$, $x_2$, \dots, $x_{14}$ numbers
$$
1+7\eps, \ 7\eps, \ 1+4\eps, \ 6\eps, \ 1+\eps, \ 5\eps, \ 1, \ 2\eps, \ 1+\eps, \ 0, \
1+4\eps, \ \eps, \ 1+6\eps, \ 4\eps.
$$
Then $f(x_1,\dots,x_{20})<7-2\eps^2+c\eps^3<7$ for some $c$ and small enough $\eps$.
 
An alternative example~\cite{Troesch-85a}:
$$
0, \ 42, \ 2, \ 42, \ 4, \ 41, \ 5, \ 39, \ 4, \ 38, \ 2, \ 38, \ 0, \ 40 \,.
$$

c)  \cite{Daykin},~\cite{Malcolm}.
Take  
%\begin{gather*}
$$
0,\enskip 85,\enskip 0,\enskip 101,\enskip 0,\enskip 120,\enskip 14,\enskip
129,\enskip 41,\enskip 116,\enskip 59,\enskip 93,\enskip 64, %\\
71,\enskip 63,\enskip 52,\enskip 60,\enskip 36,\enskip 58,\enskip 23,\enskip
58,\enskip 12,\enskip 62,\enskip 3,\enskip 71 .
%\end{gather*}
$$
Alternatively, in~\cite{Kurlyandchik-91} the following example is given:
$$
32,\enskip 0,\enskip 37,\enskip 0,\enskip 43,\enskip 0,\enskip 50,\enskip
0,\enskip 59,\enskip 8,\enskip 62,\enskip 21,\enskip 55, %\\
29,\enskip 44,\enskip 32,\enskip 33,\enskip 31,\enskip 24,\enskip 30,\enskip
16,\enskip 29,\enskip 10,\enskip 29,\enskip 4 .
$$
\end{solution}

\begin{solution}
The statement of the problem is published in \cite{Diananda-62}.
We present here a short nice solution.

Let $x_1 \geq x_2 \geq \dots \geq x_n > 0$.
Observe that the product of  $n$ fractions $\frac{x_k+x_{k+1}}{x_{k+1}+x_{k+2}}$
is equal to~1.
Then by Cauchy inequality we conclude that
$$
\Summa \frac{x_k+x_{k+1}}{x_{k+1}+x_{k+2}} \geq
n = \Summa \frac{x_{k+1}+x_{k+2}}{x_{k+1}+x_{k+2}} .
$$
Hence
\begin{equation}
\label{eqn:2-5}
\Summa \frac{x_k}{x_{k+1}+x_{k+2}} \geq
\Summa \frac{x_{k+2}}{x_{k+1}+x_{k+2}} =
\Summa \frac{x_{k+1}}{x_k+x_{k+1}} .
\end{equation}
Now we will apply the \emph{rearranging inequality}:
Let $a_1\geq\ldots\geq a_n$ and  $b_1\geq \ldots\geq b_n$ be two sets of numbers.
Then for each permutation $k_1$, \dots, $k_n$ of numbers 1, \dots, $n$
the following inequality holds
$$
a_1b_1+a_2b_2+\ldots a_nb_n\geq
a_1b_{k_1}+a_2b_{k_2}+\ldots a_nb_{k_n}\geq
a_1b_n+a_2b_{n-1}+\ldots a_nb_1.
$$

Use the rearranging inequality twice
\begin{align*}
\Summa \frac{x_k}{x_{k+1}+x_{k+2}} &=
\sum_{k=1}^{n-2} \frac{x_k}{x_{k+1}+x_{k+2}} +
\frac{x_{n-1}}{x_n+x_1} + \frac{x_n}{x_1+x_2}
\underset{(*)}\geq \\
&\geq \sum_{k=1}^{n-2} \frac{x_k}{x_{k+1}+x_{k+2}} +
\frac{x_{n-1}}{x_1+x_2} + \frac{x_n}{x_n+x_1}
\underset{(**)}\geq \\
&\geq \Summa \frac{x_k}{x_k+x_{k+1}} .
\end{align*}
The inequality (*) here is the rearranging inequality
for two pairs of numbers:
$x_{n-1} \geq x_n$ and $\frac{1}{x_n+x_1} \geq \frac{1}{x_1+x_2}$;
and the inequality (**) is the rearranging inequality for
the sets
$x_1$, $x_2$, \dots, $x_{n-1}$ and
$\frac{1}{x_1+x_2}$, $\frac{1}{x_2+x_3}$, \dots, $\frac{1}{x_{n-1}+x_n}$
that have opposite ordering.

Thus
$$
2 \Summa \frac{x_k}{x_{k+1}+x_{k+2}} \geq
\Summa \frac{x_k}{x_k+x_{k+1}} + \Summa \frac{x_{k+1}}{x_k+x_{k+1}} = n .
$$

For the decreasing set $x_i$ the solution is similar because
we do not use the order of the variables when we apply the Cauchy inequality,
and for the rearranging inequalities we need the fact
that the sets
$x_i$ and  $\frac{1}{x_i+x_{i+1}}$ have different orderings. 
\end{solution}


\begin{solution} \cite{Kurlyandchik-91}
It is easy to see that  $f_{n+2}(x_1, x_2,\ldots, x_n, x_1, x_2)=f_{n}(x_1, x_2,\ldots, x_n)+1$. 
Therefore if $f_{n}(x_1, x_2,\ldots, x_n)<n/2$, then $f_{n+2}(x_1, x_2,\ldots, x_n, x_1, x_2)<(n+2)/2$.
\end{solution}

\begin{solution} \cite{Kurlyandchik-91}
Assume that $f_m(x_1,x_2,\dots,x_m)<\frac{m}{2}$.
For each $k$ let us calculate the difference
\begin{multline*}
f_{m+1}(x_1,\dots,x_k,x_k,x_{k+1},\dots,x_m)
  - f_m(x_1,x_2,\dots,x_m) - \smash[t]{\frac{1}{2}}
=\\=
\frac{x_{k-1}}{2x_k}+\frac{x_k}{x_k+x_{k+1}} - \frac{x_{k-1}}{x_k+x_{k+1}} - \frac{1}{2} =
\frac{(x_k-x_{k-1})(x_k-x_{k+1})}{2x_k(x_k+x_{k+1})} \,.
\end{multline*}
If $(x_k-x_{k-1})(x_k-x_{k+1}) \leq 0$, then
$$
f_{n+1}(x_1,x_2,\dots,x_k,x_k,x_{k+1},\dots,x_m) < \smash{\frac{m+1}{2}}
$$
and we are done.
If $n$ is odd, we can always choose $k$ such that $(x_k-x_{k-1})(x_k-x_{k+1}) \leq 0$ 
because otherwise the product of the (odd number of) inequalities
$(x_k-x_{k-1})(x_{k+1}-x_k) < 0$ for all $k$ is 
$$
(x_2-x_1)^2(x_3-x_2)^2 \dots (x_m-x_{m-1})^2(x_1-x_m)^2 < 0 \,.
$$

Thus if for odd $n$ the Shapiro inequality is wrong then for $n+1$ it is wrong, too.
It remains to apply the statement of the previous problem.
\end{solution}

\begin{solution} \cite{Bushell, Bushell-McLeod}
\end{solution}

\begin{solution}
\cite{Zulauf-62}
Let $y_k=x_k+x_{k+1}$. Then
$$
\frac{x_1+x_4}{x_2+x_3} + \frac{x_2+x_5}{x_3+x_4} +
\ldots + \frac{x_n+x_3}{x_1+x_2} =
\Summa \frac{y_k-y_{k+1}+y_{k+2}}{y_{k+1}} =
\Summa \frac{y_k}{y_{k+1}} + \Summa \frac{y_{k+2}}{y_{k+1}} - n \geq n ,
$$
because by Cauchy inequality each sum is at least $n$.
\end{solution}


\begin{solution} The statements a), b) were published in \cite{Nowosad}.

a) !!! This short proof is taken from  \cite{Bushell-McLeod}.

Denote for brevity $a=(a_1,a_2,\dots,a_n)$, $x=(x_1,x_2,\dots,x_n)$, and
$u=(-1,1,-1,1,\dots,-1,1)$.

Observe that
$$
\frac{\partial f}{\partial x_k} (x) =
\frac{1}{x_{k+1}+x_{k+2}} - \frac{x_{k-2}}{(x_{k-1}+x_k)^2}
- \frac{x_{k-1}}{(x_k+x_{k+1})^2} .
$$
It is easy to see that we have an identity
%пїЅпїЅпїЅпїЅпїЅ пїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅ, пїЅпїЅпїЅ пїЅпїЅпїЅпїЅпїЅ пїЅпїЅпїЅпїЅпїЅ пїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅ
$$
f(x+tu) = f(x)+t\sum_{k=1}^n (-1)^k \frac{\partial f}{\partial x_k} (x) .
$$
Since $a$ is the minimum point, we have
%пїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅ пїЅпїЅпїЅпїЅпїЅпїЅ пїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅ, пїЅпїЅпїЅпїЅпїЅ пїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅ
$$
\frac{\partial f}{\partial x_k} (a) = 0 .
$$
Therefore $f(a+tu)=f(a)$ if all the coordinates of the point
$a+tu$ are positive.
Hence $a+tu$ is the minimum point of the function $f$ as well.
Hence,
$$
\frac{\partial f}{\partial x_k} (a+tu) = 0 .
$$
So
$$
\frac{1}{a_{k+1}+a_{k+2}} - \frac{a_{k-2}}{(a_{k-1}+a_k)^2}
- \frac{a_{k-1}}{(a_k+a_{k+1})^2} = 0
$$
and
$$
\frac{1}{a_{k+1}+a_{k+2}} - \frac{a_{k-2}+t(-1)^{k-2}}{(a_{k-1}+a_k)^2}
- \frac{a_{k-1}+t(-1)^{k-1}}{(a_k+a_{k+1})^2} = 0 .
$$
Subtract the first equality from the second:
$$
\frac{t}{(a_{k-1}+a_k)^2} - \frac{t}{(a_k+a_{k+1})^2} = 0 .
$$
Therefore,
$$
a_{k-1}+a_k = a_k+a_{k+1} .
$$
and hence
$$
a_1 = a_3 = a_5 = \dots = a_{n-1}
\quad\hbox{and}\quad
a_2 = a_4 = a_6 = \dots = a_n .
$$
Thus, $f(a) = n/2$.

\medskip
b)  This short proof is taken from \cite{Bushell}.
Denote for brevity
$a=(a_1,a_2,\dots,a_n)$, $x=(x_1,x_2,\dots,x_n)$,
$y=(y_1,y_2,\dots,y_n)$, $z=(z_1,z_2,\dots,z_n)$, where
$y_k=x_k+x_{k+1}$ and $z_k=1/y_{n+1-k}$.

Set
$$
S(x) = \frac{x_1}{x_2+x_3} + \frac{x_2}{x_3+x_4} + \ldots + \frac{x_{n-1}}{x_n+x_1}
+ \frac{x_n}{x_1+x_2} = \summa \frac{x_k}{y_{k+1}} .
$$
Observe that
$$
\frac{\partial f}{\partial x_k} (x) =
\frac{1}{x_{k+1}+x_{k+2}} - \frac{x_{k-2}}{(x_{k-1}+x_k)^2}
- \frac{x_{k-1}}{(x_k+x_{k+1})^2} .
$$

It is easy to check the following identities:
$$
\frac{a}{b}+\frac{c}{d} =
\frac{a+c}{b+d}+\frac{\dfrac{a}{b^2}+\dfrac{c}{d^2}}{\dfrac{1}{b}+\dfrac{1}{d}} .
$$
Hence,
\begin{align*}
\frac{x_{k-2}}{x_{k-1}+x_k}+\frac{x_{k-1}}{x_k+x_{k+1}} &=
\frac{x_{k-2}+x_{k-1}}{(x_{k-1}+x_k)+(x_k+x_{k+1})}+
\frac{\dfrac{x_{k-2}}{(x_{k-1}+x_k)^2} +
\dfrac{x_{k-1}}{(x_k+x_{k+1})^2}}{\dfrac{1}{x_{k-1}+x_k}+\dfrac{1}{x_k+x_{k+1}}}
=\\
&= \frac{y_{k-2}}{y_{k-1}+y_k} +
\frac{z_{n-k}-\dfrac{\partial f}{\partial x_k} (x)}{z_{n-k+1}+z_{n-k+2}} .
\end{align*}
Therefore,
$$
2S(x) = S(y)+S(z)-
\Summa \frac{\dfrac{\partial f}{\partial x_k} (x)}{z_{n-k+1}+z_{n-k+2}} .
$$

If $x$ is a minimum point then we have  $2S(x) = S(y)+S(z)$.
Hence $S(x)=S(y)=S(z)$.

Let $u:=(x_1+x_2+\dots+x_n)/n$.
Consider the transformation $M:\mathbb R^n\to \mathbb R^n$ defined by 
$$
M(x)=\Bigl( \frac{x_1+x_2}{2}, \frac{x_2+x_3}{2}, \dots, \frac{x_n+x_1}{2} \Bigr).
$$
Let $M_k(x)$ be its $k$-th iteration. Observe that
$S(x)=S(y)=S(M(x))=\dots=S(M_k(x))$.
It is clear that $\lim\limits_{k\to\infty} M_k(x) =
(u,u,\dots,u)$. Then
$$
S(x) = \lim\limits_{k\to\infty} S(M_k(x)) = S((u,u,\dots,u)) = \frac{n}{2} .
$$


c)  \cite{Diananda-63a}, \cite{Bushell, Bushell-McLeod}
\end{solution}


\begin{solution} These solutions are taken from~\cite{Kurlyandchik-91}.

пїЅ) The problem was presented at the
Third USSR mathematical olympiad, 1969. Probably it was originally published in~\cite{Diananda-62a}.

Let $x_{i_1}$ be the maximal number among
%~--- пїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅ пїЅпїЅ пїЅпїЅпїЅпїЅпїЅ
$x_1$, $x_2$, \dots, $x_n$;
$x_{i_2}$ be the maximum of the two next numbers after $x_{i_1}$ (i.e. of $x_{i_1+1}$ and $x_{i_1+2}$);
%~--- пїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅ пїЅпїЅ пїЅпїЅпїЅпїЅ пїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅ пїЅпїЅ $x_{i_1}$ пїЅпїЅпїЅпїЅпїЅ;
$x_{i_3}$ be the maximum of the two next numbers after $x_{i_2}$, and so on.
%~--- пїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅ пїЅпїЅ пїЅпїЅпїЅпїЅ пїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅ пїЅпїЅ $x_{i_2}$ пїЅпїЅпїЅпїЅпїЅ пїЅ~пїЅ.\,пїЅ.
We will continue this sequence till the step number $k$ when
the maximum of the two next after $x_{i_k}$ numbers is  $x_{i_1}$.
%пїЅпїЅпїЅпїЅпїЅ пїЅпїЅпїЅпїЅпїЅпїЅпїЅ пїЅпїЅпїЅ пїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅ пїЅпїЅпїЅпїЅпїЅ пїЅпїЅ пїЅпїЅпїЅ пїЅпїЅпїЅ пїЅпїЅпїЅпїЅ пїЅпїЅ пїЅпїЅпїЅпїЅпїЅпїЅ
%пїЅпїЅ пїЅпїЅпїЅпїЅпїЅпїЅ $k$, пїЅпїЅпїЅ пїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅ пїЅпїЅ пїЅпїЅпїЅпїЅ пїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅ пїЅпїЅ $x_{i_k}$ пїЅпїЅпїЅпїЅпїЅ~--- пїЅпїЅпїЅ $x_{i_1}$.

It is clear that $k\geq n/2$. We have
$$
\frac{x_1}{x_2+x_3} + \frac{x_2}{x_3+x_4} + \ldots + \frac{x_n}{x_1+x_2} \geqslant
\frac{x_{i_1}}{2x_{i_2}} + \frac{x_{i_2}}{2x_{i_3}} + \ldots + \frac{x_{i_k}}{2x_{i_1}}.
$$
The last expression is at least $k/2$ by the Cauchy inequality
therefore it is at least  $n/4$.
%пїЅпїЅ пїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅ пїЅ пїЅпїЅпїЅпїЅпїЅпїЅпїЅ пїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅ пїЅ пїЅпїЅпїЅпїЅпїЅпїЅпїЅ пїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅ
%пїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅ пїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅ пїЅпїЅ пїЅпїЅпїЅпїЅпїЅпїЅ $k/2$, пїЅ пїЅпїЅпїЅпїЅпїЅпїЅ, пїЅпїЅ пїЅпїЅпїЅпїЅпїЅпїЅ $n/4$.

\medskip
b) %\cite{Kurlyandchik-91};
Rewrite each of the fractions $\frac{x_k}{x_{k+1}+x_{k+2}}$, $k=1$, 2, \dots, $n$,
in the form
$$
\frac{x_k}{x_{k+1}+x_{k+2}}=
\frac{x_k+\frac12 x_{k+1}}{x_{k+1}+x_{k+2}}+\frac{\frac12 x_{k+1}+x_{k+2}}{x_{k+1}+x_{k+2}}-1\,.
$$
We obtain $2n$ fractions. Combine them by pairs:
the first and the last, the second and the third, the fourth and the fifth and so on.
% пїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅ пїЅпїЅ пїЅпїЅ пїЅпїЅпїЅпїЅпїЅ~--- пїЅпїЅпїЅпїЅпїЅпїЅ пїЅ $2n$-пїЅ, пїЅпїЅпїЅпїЅпїЅпїЅ пїЅ пїЅпїЅпїЅпїЅпїЅпїЅпїЅ, пїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅ пїЅ пїЅпїЅпїЅпїЅпїЅ пїЅ~пїЅ.\,пїЅ.
Now estimate the sum of each pair from below
%пїЅпїЅпїЅпїЅпїЅпїЅ пїЅпїЅпїЅпїЅпїЅ пїЅпїЅпїЅпїЅпїЅ пїЅпїЅпїЅпїЅпїЅпїЅ пїЅпїЅ пїЅпїЅпїЅпїЅпїЅ пїЅпїЅпїЅпїЅ:
\begin{multline*}
\frac{\frac12 x_k+x_{k+1}}{x_{k}+x_{k+1}}+\frac{x_{k}+\frac12 x_{k+1}}{x_{k+1}+x_{k+2}}\geq
2\sqrt{\frac{(\frac12 x_k+x_{k+1})(x_{k}+\frac12 x_{k+1})}{({x_{k}+x_{k+1}})(x_{k+1}+x_{k+2})}}
=\\=
2\sqrt{\left(\frac12 +  \frac{x_kx_{k+1}}{4(x_k+x_{k+1})^2} \right)\frac{x_k+x_{k+1}}{x_{k+1}+x_{k+2}}}>
\sqrt{2}\cdot\sqrt{\frac{x_k+x_{k+1}}{x_{k+1}+x_{k+2}}}.
\end{multline*}
Since the product of $n$ numbers  $\sqrt{\frac{x_1+x_{2}}{x_{2}+x_{3}}}$,
$\sqrt{\frac{x_2+x_{3}}{x_{3}+x_{4}}}$, \dots, $\sqrt{\frac{x_n+x_{1}}{x_{1}+x_{2}}}$
equals 1, then by the Cauchy inequality their sum is at least  $n$.
Therefore $f(x_1,\dots,x_n)\ge\sqrt{2} n - n=(\sqrt2 -1)n$.

\medskip
c) %\cite{Kurlyandchik-91}
As in the previous solution rewrite each of the fractions
 $\frac{x_k}{x_{k+1}+x_{k+2}}$, $k=1$, 2, \dots, $n$, in the form
$$
\frac{x_k}{x_{k+1}+x_{k+2}}=
\frac{x_k+\beta x_{k+1}}{x_{k+1}+x_{k+2}}+\alpha\cdot\frac{\beta x_{k+1}+x_{k+2}}{x_{k+1}+x_{k+2}}-\alpha\,,
$$
where $\alpha$ and $\beta$ are parameters chosen to make the equality true.
%пїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅ пїЅпїЅпїЅ, пїЅпїЅпїЅпїЅпїЅ пїЅпїЅпїЅ пїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅ пїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅ пїЅпїЅпїЅпїЅпїЅпїЅ.
For such a choice of $\alpha$ and $\beta$ we need 
%пїЅпїЅпїЅ пїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅ пїЅпїЅпїЅпїЅпїЅпїЅ, пїЅпїЅпїЅ пїЅпїЅпїЅпїЅпїЅ пїЅпїЅпїЅпїЅпїЅ, пїЅпїЅпїЅпїЅпїЅ
$\beta+\alpha\beta=\alpha$, i.e. $\beta=\alpha/(\alpha+1)$.
Then
\begin{multline*}
\frac{x_k+\beta x_{k+1}}{x_{k+1}+x_{k+2}} + \alpha\cdot\frac{\beta x_{k}+x_{k+1}}{x_{k}+x_{k+1}}\geq
2\sqrt{\alpha\frac{(x_k+\beta x_{k+1})(\beta x_{k}+ x_{k+1})}{({x_{k}+x_{k+1}})(x_{k+1}+x_{k+2})}}
=\\=
2\sqrt{\alpha\frac{\beta(x_k+x_{k+1})^2+(\beta-1)^2 x_{k}x_{k+1}}{({x_{k}+x_{k+1}})(x_{k+1}+x_{k+2})}}>
2\sqrt{\alpha\beta\frac{x_k+x_{k+1}}{x_{k+1}+x_{k+2}}}=
\frac{2\alpha}{\sqrt{\alpha+1}} \cdot\sqrt{\frac{x_k+x_{k+1}}{x_{k+1}+x_{k+2}}}\,.
\end{multline*}
Therefore
\begin{multline*}
\frac{x_1}{x_2+x_3} + \frac{x_2}{x_3+x_4} + \ldots + \frac{x_{n-1}}{x_n+x_1}
+ \frac{x_n}{x_1+x_2}\geq
\frac{2\alpha}{\sqrt{\alpha+1}}\left( \sqrt{\frac{x_1+x_{2}}{x_{2}+x_{3}}}+
\sqrt{\frac{x_2+x_{3}}{x_{3}+x_{4}}}+ \ldots +\sqrt{\frac{x_n+x_{1}}{x_{1}+x_{2}}}\right) -\alpha n
>\\ >
\frac{2\alpha}{\sqrt{\alpha+1}} n -\alpha n =
\left(\frac{2\alpha}{\sqrt{\alpha+1}} -\alpha\right) n\,.
\end{multline*}
For $\alpha=\frac54$ we have $c=5/{12}$.
\end{solution}

{R\,e\,m\,a\,r\,k.} This is a good approximation.%???
The expression $g(\alpha)=\frac{2\alpha}{\sqrt{\alpha+1}} -\alpha$
reaches its maximal value at $\alpha=\alpha_0\approx 1.1479$
(this is a root of the cubic equation $g'(\alpha)=0$),
and the minimum value is $g(\alpha_0)\approx 0.4186$.
For $\alpha=\frac54$ we have $g(\alpha)=\frac5{12}\approx 0.416$. 


\smallskip
\begin{solution}
%{\bf 1.10.a.}
\cite{Cyrtioaje}.
Set ${y_k=x_k\!+\!x_{k+1}}$. We need to prove that
$$
\frac{x_1}{y_2}+\frac{x_2}{y_3}+\ldots+\frac{x_n}{y_1} \geq \frac{n}{2}\,,
$$
or
$$
\Summa \frac{2q_n^2x_k-y_{k+1}}{y_{k+1}} \geq n(q_n^2-1) .
$$
We suppose that the parameter $q_n$ will be chosen later.
Since
$$
2q_n^2x_k-y_{k+1}=(q_n^2x_k-x_{k+1})+(q_n^2x_k-x_{k+2}) \geq 0 \,,
$$
by the Cauchy-Bunyakovsky inequality for sets
$$
\left\{ \sqrt{\frac{2q_n^2x_k-y_{k+1}}{y_{k+1}}}\ \right\}
\enskip\hbox{and}\enskip
\left\{ \sqrt{(2q_n^2x_k-y_{k+1})y_{k+1}} \right\}
$$
we have
$$
\Summa \frac{2q_n^2x_k-y_{k+1}}{y_{k+1}} \geq
\frac{\smash[t]{\Bigl( \Summa (2q_n^2x_k-y_{k+1}) \Bigr)^2}}{\Summa
(2q_n^2x_k-y_{k+1})y_{k+1}} .
$$
So it suffices to prove that
$$
A^2:=\biggl( \Summa (2q_n^2x_k-y_{k+1}) \biggr)^2 \geq
n(q_n^2-1)\smash[t]{\Summa (2q_n^2x_k-y_{k+1})y_{k+1}} =: n(q_n^2-1)B .
$$
Since $\Summa \!y_k = 2\Summa \!x_k$, we have
%$A = (q_n^2-1)\Summa y_k$~пїЅ
\begin{align*}
A &= (q_n^2-1)\Summa y_k\,,\\
%$$
B &= 2q_n^2\Summa x_k y_{k+1}-\Summa y_k^2 =
2q_n^2\Summa y_ky_{k+1}-(q_n^2+1)\Summa y_k^2 \,.
%$$
\end{align*}
So it remains to prove that
\begin{equation}
\label{ciro}
(q_n^2-1)\biggl( \Summa y_k \biggr)^2 \geq n\biggl(2q_n^2\Summa
y_ky_{k+1}-(q_n^2+1)\Summa y_k^2\biggr) .
\end{equation}

Transform the left-hand side using the relation
$$
\biggl( \Summa y_k \biggr)^2 = n \Summa y_k^2 - \summaik (y_i-y_k)^2.
$$
The inequiality~(\ref{ciro}) will be transformed to
$$
n\Summa (y_k-y_{k+1})^2 \geq
\Bigl(1-\frac{1}{q_n^2}\Bigr) \summaik (y_i-y_k)^2 .
$$
By the Cauchy-Bunyakovsky inequality
$$
\Summa (y_k-y_{k+1})^2 \geq
\sum_{j=i}^{k-1} (y_j-y_{j+1})^2 \geq
\frac{1}{k-j} \biggl( \sum_{j=i}^{k-1} (y_j-y_{j+1}) \biggr)^2 =
\frac{1}{k-j} (y_i-y_k)^2 \geq
\frac{1}{n-1} (y_i-y_k)^2 .
$$
Hence
$$
\frac{n(n-1)}{2} \Summa (y_k-y_{k+1})^2 \geq
\frac{1}{n-1} \summaik (y_i-y_k)^2.
$$
So we can take $1-\frac{1}{q_n^2}=\frac{2}{(n-1)^2}$, i.\,e.
$q_n = \frac{n-1}{\sqrt{n^2-2n-1}} > 1$.

R\,e\,m\,a\,r\,k. \,When $n$ tends to infinity, the values $q_n$ which are found above tend to~$1$.

b)

\end{solution}


\smallskip
\begin{solution}
%{\bf 1.11.}
(a) Denote $k_i:=x_{i+1}/x_i$. Then
$$S=\frac1{k_1(k_2+1)}+\frac1{k_2(k_3+1)}+\dots+\frac1{k_n(k_1+1)} \ge
\frac1{a_1(a_n+1)}+\frac1{a_2(a_{n-1}+1)}+\dots+\frac1{a_n(a_1+1)}.$$

(b) The inequality holds because
$$\frac1{a_i(a_{n+1-i}+1)}+\frac1{a_{n+1-i}(a_i+1)}=
\frac{1+\frac{a_ia_{n+1-i}-1}{(1+a_i)(1+a_{n+1-i})}}{a_ia_{n+1-i}}\ge b_i
%\begin{cases}1/b_i& b_i\ge1 \\ 2(e^{y_i/2}+e^y_i)^{-1} & y_i<0 \end{cases},
$$
where the latter inequality holds because $(1+a_i)(1+a_{n+1-i})\ge (1+\sqrt{a_ia_{n+1-i}})^2$.

(c) The first inequality $2S\ge g(\ln(a_1a_n))+g(\ln(a_2a_{n-1}))+\dots+g(\ln(a_na_1))$ holds because
$g(x)$ is less than both $e^{-x}$ and $2(e^x+e^{x/2})^{-1}$.
The second inequality holds by the Jensen inequality because $g$ is convex.

(d) [Dr]
\end{solution}




%\begin{solution}
%\end{solution}


\refstepcounter{subsection}

\goodbreak

\begin{solution}
a) \cite{Mordell}

For $n=4$ we need to prove that
$$
(x_1+x_2+x_3+x_4)^2 \geq 2x_1x_2+2x_2x_3+2x_3x_4+2x_4x_1+4x_1x_3+4x_2x_4 \,.
$$
This follows from the inequality
$$
x_1^2+x_2^2+x_3^2+x_4^2 \geq 2x_1x_3+2x_2x_4 \,.
$$

For $n=3$ and $n=5$ re-write the inequality. We need to prove that
\begin{equation}
\label{ai ak}
(n-1)(a_1+a_2+\ldots+a_n)^2 \geq 2n\summaik a_ia_k .
\end{equation}
Indeed, notice that the Cauchy--Bunyakovsky inequality applied to sets
$a_1,a_2,\dots,a_n$ and $1, 1, \dots, 1$ gives us:
 $$
n (a_1^2+a_2^2+\ldots+a_n^2)\ge (a_1+a_2+\ldots+a_n)^2.
%\end{equation}
$$
Now we have
$$n (a_1+a_2+\ldots+a_n)^2 = n (a_1^2+a_2^2+\ldots+a_n^2) +
\smash[b]{2n\summaik a_ia_k \geq  (a_1+a_2+\ldots+a_n)^2 + 2n\summaik a_ia_k }\,,
$$
which implies (\ref{ai ak}).

Now assume that $n \geq 6$.
We may suppose that $x_3 \geq x_1$ and $x_3 \geq x_2$ (e.g. make a cyclic shift of variables such that $x_3$ becomes the maximum).
For $r=1$, 2, and 3 denote by $a_r$ the sum of all $x_k$ such that $k \equiv r \pmod{3}$ and $k \leq n$.
Then $x_1+x_2+\ldots+x_n = a_1+a_2+a_3$. Hence by~(\ref{ai ak}) we have
$$
(x_1+x_2+\ldots+x_n)^2=(a_1+a_2+a_3)^2
\geq 3(a_1a_2+a_2a_3+a_3a_1) =
\smash[b]{3\cdot \sum\limits_{(i-k) \,\nekratno\, 3} x_ix_k\,.}
$$
Set
$$
A:=\sum\limits_{(i-k)\,\nekratno\, 3} x_ix_k
\quad\hbox{and}\quad
B:=\Summa x_k(x_{k+1}+x_{k+2}).
$$
We have $A\geq B$ because

$\bullet$ for $n \equiv 0 \pmod{3}$ all the summands of $B$ are contained in~$A$;

$\bullet$ for $n \equiv 1 \pmod{3}$ the sum $A$ contains all the summands of~$B$ except
$x_nx_1$, but $x_nx_1$ does not exceed $x_nx_3$;

$\bullet$ for $n \equiv 2 \pmod{3}$ the sum $A$ contains all the summands of~$B$ except
$x_{n-1}x_1$ and $x_nx_2$, but these summands do not exceed $x_{n-1}x_3$ and $x_nx_3$, respectively.

Hence
$$
(x_1+x_2+\ldots+x_n)^2 \geq 3A \geq 3B = 3\Summa x_k(x_{k+1}+x_{k+2}) .
$$

In order to show that $\min \left\{ \frac{n}{2}, 3 \right\}$ is the sharp constant
for $n \leq 6$ we set $x_1=x_2=\ldots=x_n=1$ and for $n \geq 6$~we set
$x_1=x_2=x_3=1$ and $x_4=x_5=\ldots=x_n=0$.

\medskip
b) The case $n<6$ is trivial. For $n=6$ the equality is achieved when
$x_1+x_4=x_2+x_5=x_3+x_6$. For $n\geqslant 6$ the equality is achieved for the
sets of form $(t,1,1,1-t,0,\ldots,0)$, where $t\in [0,1]$, and their cyclic 
shifts.
\end{solution}

\begin{solution} \cite{Mordell}

For $n=4$ and $n=7$ this is a particular case of~(\ref{ai ak}).

For $n=5$ the inequality coincides with $\sum (x_k-2x_{k+2}+x_{k+4})^2 \geq 0$.

For $n=6$ the inequality follows from $x_1^2+x_2^2+\ldots+x_6^2 \geq 2x_1x_4+2x_2x_5+2x_3x_6$.

For $n=8$ open brackets in the following corollary of the Cauchy--Bunyakovsky inequality
$$
4(x_1^2+x_2^2+x_3^2+x_4^2) \geq (x_1+x_2+x_3+x_4)^2.
$$
We obtain
$$
3(x_1^2+x_2^2+x_3^2+x_4^2) \geq
2(x_1x_2+x_1x_3+x_1x_4+x_2x_3+x_2x_4+x_3x_4) .
$$
Hence
\begin{equation}
\label{8/3}
3(x_1+x_2+x_3+x_4)^2 \geq
8(x_1x_2+x_1x_3+x_1x_4+x_2x_3+x_2x_4+x_3x_4) ,
\end{equation}
This is the required inequality for $n=8$.

Now assume that $n > 8$.
We may suppose that $x_4 \geq x_1$, $x_4 \geq x_2$, and $x_4 \geq x_3$.
For $r=1$, 2, 3, and 4 denote by $a_r$ the sum of all $x_k$ such that
$k \equiv r \pmod{4}$ and $k \leq n$.
Then $x_1+x_2+\ldots+x_n = a_1+a_2+a_3+a_4$.
Hence by~(\ref{8/3})
$$
3(x_1+x_2+\ldots+x_n)^2=3(a_1+a_2+a_3+a_4)^2 \geq
8(a_1a_2+a_2a_3+a_3a_4+a_4a_1)\geq
\smash[b]{8\cdot \sum\limits_{(i-k) \,\nekratno\, 4} x_ix_k\,.}
$$
Set
$$
A:=\sum\limits_{(i-k)\,\nekratno\, 4} x_ix_k
\quad\hbox{and}\quad
B:=\Summa x_k(x_{k+1}+x_{k+2}+x_{k+3}).
$$
We have $A\geq B$ because

$\bullet$ for $n \equiv 0 \pmod{4}$ all the summands of $B$ are contained in~$A$;

$\bullet$ for $n \equiv 1 \pmod{4}$ the sum $A$ contains all the summands of $B$
except $x_nx_1$, but $x_nx_1$ does not exceed $x_nx_4$;

$\bullet$ for $n \equiv 2 \pmod{4}$ the sum $A$ contains all the summands of $B$
except $x_{n-1}x_1$ and $x_nx_2$, but these summands do not exceed $x_{n-1}x_4$ and $x_nx_4$;

$\bullet$ for $n \equiv 3 \pmod{4}$ the sum $A$ contains all the summands of $B$
except $x_{n-2}x_1$, $x_{n-1}x_2$ and $x_nx_3$, but these summands do not exceed
$x_{n-2}x_4$, $x_{n-1}x_4$, and $x_nx_4$.

Hence
$$
3(x_1+x_2+\ldots+x_n)^2 \geq 8A \geq 8B = 8\Summa x_k(x_{k+1}+x_{k+2}+x_{k+3}) .
$$
\end{solution}


%\refstepcounter{subsection}

\begin{solution}
a) Cf. \cite{Diananda-59}.
By the Cauchy--Bunyakovsky inequality and Problem~\ref{zadacha2.2} we have
$$
\frac{x_1}{x_2+x_3+x_4} + \frac{x_2}{x_3+x_4+x_5} + \ldots +
  \frac{x_{n-1}}{x_n+x_1+x_2} + \frac{x_n}{x_1+x_2+x_3} \geq
\frac{(x_1+x_2+\ldots+x_n)^2}{\sum x_k(x_{k+1}+x_{k+2}+x_{k+3})} \geq
\frac{n}{3}.$$

b) ???
\end{solution}

\begin{solution}
\cite[Problem 187]{VasEgorov}.
We may assume that $x_1 \leq x_2$. Set
$$S: = x_1 + x_2 + \ldots + x_n,\quad S_1: = x_1 + x_3 + \dots,\quad S_2: = x_2 + x_4 + \dots.$$
Then
$S_1^2 + S_2^2 \geq (S_1+S_2)^2/2 = S^2/2$. Hence
\begin{equation}
\label{eqn:union187-hihi}
\frac{S^2}{2} \geq S^2 - S_1^2 - S_2^2 =
   2 \sum \limits_{(i-k) \nekratno 2} x_i x_k .
\end{equation}
If $n$ is even, then the last sum contains all the summands of form
$x_k x_{k+1}$. If $n$ is odd, then the summand $x_n x_1$ is missing, however the sum
contains a greater summand $x_n x_2$. So
$$
\frac{S^2}{2} \geq 2(x_1 x_2 + x_2 x_3 + \ldots + x_n x_1).
$$
\end{solution}


\begin{solution}
See the solution of \ref{prbl:1.3} up to the inequality (\ref{eqn:2-5}).
 \end{solution}


\begin{solution}
Induction on $n\geqslant n=4$.
Denote the left-hand side by $L_n$. We have
$$
L_4=\frac{x_1+x_3}{x_2+x_4}+\frac{x_2+x_4}{x_1+x_3}=a+a^{-1}\geq2.
$$
Let us prove the inductive step.
We may assume that $x_{n+1}$~is the minimal of all $x_i$'s.
Now remove the last summand from $L_{n+1}$, and then decrease two others.
We obtain
$$
L_{n+1}\geq \frac{x_1}{x_{n+1}+x_2}+\ldots+\frac{x_n}{x_{n-1}+x_{n+1}}\geq
\frac{x_1}{x_{n}+x_2}+\ldots+\frac{x_n}{x_{n-1}+x_{n}}=L_n\,.
$$
In order to show that the constant 2 is sharp, take
$$
x_1=x_2=1, \quad x_3=t, \quad x_4=t^2, \quad \ldots, \quad x_{n}=t^{n-2}\,.
$$
When $t\to+0$, the first two summands tend to $1$ and the remaining tends to 0.
\end{solution}


\begin{solution} \cite{Daykin}.
Set $S: = x_1 + x_2 + \ldots + x_n$.
Use the Cauchy--Bunyakovsky inequality for sets
$ \left\{ \frac{x_k+x_{k+1}}{x_k+x_{k+2}} \right\}$
and ${\{ (x_k+x_{k+1})(x_k+x_{k+2}) \}}$.
We obtain
$$ \frac{x_1+x_2}{x_1+x_3} + \frac{x_2+x_3}{x_2+x_4} + \ldots +
 \frac{x_{n-1}+x_n}{x_{n-1}+x_1} + \frac{x_n+x_1}{x_n+x_2} \geq
 \frac{4(x_1 + x_2 + \ldots + x_n)^2}{\Summa (x_k + x_{k+1})(x_k + x_{k+2})} .$$
So it suffices to prove that
$$ S^2 \geq \Summa (x_k + x_{k+1})(x_k + x_{k+2}) =
   \Summa x_k^2 + 2 \Summa x_k x_{k+1} + \Summa x_k x_{k+2}. $$
This can be shown by opening brackets in the left-hand side, because for
$n \geq 4$ all the summands $x_k x_{k+1}$ and $x_k x_{k+2}$, where $k = 1$, 2, \dots, $n$,
are different.

In order to show that the constant 4 is sharp, take $x_k = a^{k-1}$ for
$k = 1$, 2, \dots, $n-1$ and $x_n = a^{n-2}$.
When $a \to \infty$, the first $n-3$ summands tend to 0 and the remaining summands tend to 1, 2 and 1.

\medskip
Using the Cauchy--Bunyakovsky inequality as it is done in the solution of the next problem, the reader will easily find another solution of this problem
reducing it to the inequality from Problem~~\ref{prbl:ginzburg}.
\end{solution}


\begin{solution}
\cite{Chimedtseren}.
Use the Cauchy--Bunyakovsky inequality for sets
 $ \left\{ \frac{x_k}{x_{k-1} + x_{k+2}} \right\}$ пїЅ
$\{ x_k(x_{k-1} + x_{k+2}) \}$.
We obtain
$$
%\begin{multline*}
\frac{x_1}{x_n+x_3} + \frac{x_2}{x_1+x_4} + \ldots +
   \frac{x_{n-1}}{x_{n-2}+x_1} + \frac{x_n}{x_{n-1}+x_2}
\geq %\\ \geq
\frac{(x_1 + x_2 + \ldots + x_n)^2}{(x_1 x_2 + x_2 x_3 + \ldots + x_n x_1) +
   (x_1 x_3 + x_2 x_4 + \ldots + x_n x_2)} .
%\end{multline*}
$$
So it suffices to prove that
$$ S^2 \geq 3(x_1 x_2 + x_2 x_3 + \ldots + x_n x_1) +
         3(x_1 x_3 + x_2 x_4 + \ldots + x_n x_2) =: 3Y ,$$
where $S: = x_1 + x_2 + \ldots + x_n$.
Set
$$S_1: = x_1 + x_4 + \dots,\quad S_2 = x_2 + x_5 + \ldots\quad\mbox{and}\quad S_3 = x_3 + x_6 + \dots.$$
Then $S = S_1 + S_2 + S_3$ and $S_1^2 + S_2^2 + S_3^2 \geq S^2/3$.
We may assume that $x_3 \geq x_1$ and $x_3 \geq x_2$.
Notice that
$$
S^2 \geq \frac{3}{2} (S^2 - S_1^2 - S_2^2 - S_3^2) =
   3 \sum \limits_{(i-k) \nekratno 3} x_i x_k =: 3Z .
$$

$\bullet$ If $n \equiv 0 \pmod{3}$, then all the summands of $Y$ are contained in $Z$.

$\bullet$ If $n \equiv 1 \pmod{3}$, then $Z$ contains all the summands of $Y$ except
 $x_n x_1$, but this summand does not exceed $x_n x_3$.

$\bullet$ If $n \equiv 2 \pmod{3}$, then $Z$ contains all the summands of $Y$ except
$x_{n-1} x_1$ and $x_n x_2$, but these summands do not exceed $x_{n-1} x_3$ and $x_n x_3$.

Hence $S^2 \geq 3Y \geq 3Z$, which proves the initial inequality.

In order to show that the constant 3 is sharp, take $x_k = a^{k-1}$ for
$k = 1$, 2, \dots, $n-2$ and~$x_{n-1} = x_n = 1$. When $a \to 0$, the first and the
last two summands tend to 1, while the remaining summands tend to 0.
\end{solution}

\begin{solution} \cite{Chimedtseren-99}.
The inequality is obtained by summing two inequalities of \ref{prbl:chimedtseren}
(for the direct and the opposite order of variables).

In order to show that the constant 6 is sharp, take $x_k = a^{k-1}$ for
$k = 1$, 2, \dots, $n-2$ and~$x_{n-1} = x_n = 1$.
When $a \to 0$, the last four summands tend to 1, 2, 2, 1, respectively; the remaining tend to 0.
\end{solution}

\begin{solution} This is conjectured in \cite{Mitrinovich}.

The following proof is due to P.Milo\v sevi\'c  пїЅ M.~Buki\'c, participants of the Conference.

This inequality can be represented as sum of two inequalities for $n=2004$~--- the inequality from Problem~\ref{prbl:chimedtseren} and the inequality
$$
\frac{x_1}{x_1+x_4} + \frac{x_2}{x_2+x_5} + \ldots +
   \frac{x_{n}}{x_{n}+x_3} \geq 3\,.
$$
Prove the last inequality. For $n=3m$ it is the sum of three inequalities:
\begin{align*}
\frac{x_1}{x_1+x_4} + \frac{x_4}{x_4+x_7} + \ldots +
   \frac{x_{n-2}}{x_{n-2}+x_1} &\geq 1\,. \\
\frac{x_2}{x_2+x_5} + \frac{x_5}{x_5+x_8} + \ldots +
   \frac{x_{n-1}}{x_{n-1}+x_2} &\geq 1\,. \\
\frac{x_3}{x_3+x_6} + \frac{x_6}{x_6+x_9} + \ldots +
   \frac{x_{n}}{x_{n}+x_3} &\geq 1\,.
\end{align*}
Each of these inequalities can be re-written as
$$
\frac1{1+a_1}+ \frac1{1+a_3}+\ldots+ \frac1{1+a_m} \geq 1
\qquad\text{ where } \ a_1a_2\dots a_m=1.
$$
This can be shown by induction. The base $m=2$ is the following inequality:
$$
\frac1{1+a_1}+\frac1{1+\frac1{a_1}}=1\geq 1\,.
$$
To prove the induction step, let us check that
$$
\frac1{1+b}+\frac1{1+c}\geq \frac 1{1+bc}\,.
$$
This can be done directly by reducing to a common denominator and opening brackets.

\medskip

Here is the proof of A. Khrabrov.
Let us prove that
$$ Z: = \frac{x_1 + x_2}{x_1 + x_4} + \frac{x_2 + x_3}{x_2 + x_5} + \ldots +
   \frac{x_{3n} + x_1}{x_{3n} + x_3} \geq 6 .$$
Set $x_{3n+k} := x_k$ and, for $r=0,1,2$,
$$ S_r: = \Summa x_{3k+r}, \quad
X_r := \Summa \frac{x_{3k+r}}{x_{3k+r} + x_{3k+3+r}}, \quad\hbox{and}\quad
Y_r := \Summa \frac{x_{3k+r+1}}{x_{3k+r} + x_{3k+3+r}}. $$
First we prove that $X_r \geq 1$.
Consider only the case $r = 0$. Then
$$ X_0 S_0^2 \geq X_0 \left( \Summa x_{3k}^2 + \Summa x_{3k} x_{3k+3} \right) =
   X_0 \left( \Summa x_{3k} (x_{3k} + x_{3k+3}) \right) \geq S_0^2 ,$$
where the last inequality holds by the Cauchy--Bunyakovsky inequality. So $X_0 \geq 1$.

Now prove that $Y_r \geq S_{r+1}/S_r$ (we set $S_3: = S_0$).
Consider only the case $r = 0$.
$$%\begin{align*}
Y_0 S_0 S_1 \geq Y_0 \left( \Summa x_{3k} x_{3k+1} + \Summa x_{3k+1} x_{3k+3} \right) =
 Y_0 \left( \Summa x_{3k+1} (x_{3k} + x_{3k+3}) \right) \geq S_1^2 ,
$$%\end{align*}
where the last inequality holds by the Cauchy--Bunyakovsky inequality. So $Y_0 \geq S_1/S_0$.

Summing up all the proved inequalities we obtain
$$ Z = X_0 + X_1 + X_2 + Y_0 + Y_1 + Y_2 \geq 3 +
  \frac{S_1}{S_0} + \frac{S_2}{S_1} + \frac{S_0}{S_2} \geq 6 .$$

In order to show that the constant 6 is sharp, take $x_1=x_2=x_3=1$,
$x_k = a^{n-k+1}$ for $k = 3$, 4,~\dots,~$n$.
When $a \to 0$, the first and the second summands tend to 2, the third and the last tend to 1,
and the remaining summands tend to 0.
\end{solution}

\begin{solution} This proof is due to A. Khrabrov.
Set $S = x_1 + x_2 + \ldots + x_n$ and $T = \sum \limits_{(i-k) \nekratno 2} x_i x_k$.
By the Cauchy--Bunyakovsky inequality for sets
$\displaystyle \left\{ \frac{x_k}{x_{k-1} + x_{k+3}} \right\}$ and
$\{ x_k(x_{k-1} + x_{k+3}) \}$
we have
$$
%\begin{multline*}
\frac{x_1}{x_n+x_4} + \frac{x_2}{x_1+x_5} + \ldots +
   \frac{x_{n-1}}{x_{n-2}+x_2} + \frac{x_n}{x_{n-1}+x_3}
\geq %\\ \geq
\frac{(x_1 + x_2 + \ldots + x_n)^2}{(x_1 x_2 + x_2 x_3 + \ldots + x_n x_1) +
   (x_1 x_4 + x_2 x_5 + \ldots + x_n x_3)} .
%\end{multline*}
$$
So it suffices to prove that
$$ S^2 \geq 4(x_1 x_2 + x_2 x_3 + \ldots + x_n x_1) +
         4(x_1 x_4 + x_2 x_5 + \ldots + x_n x_3) .$$
In the solution of problem \ref{prbl:ginzburg} we proved that $S^2 \geq 4T$, see (\ref{eqn:union187-hihi}).
So it suffices to prove that
\begin{equation}
\label{chimedts-4}
T \geq (x_1 x_2 + x_2 x_3 + \ldots + x_n x_1) +
   (x_1 x_4 + x_2 x_5 + \ldots + x_n x_3) .
\end{equation}
Since $n$ is even, all the summands of the right-hand sum are contained in the left-hand sum.

In order to show that the constant 6 is sharp, take $x_k = a^{k-1}$ and $k = 1$, 2, \dots, $n-3$
and~$x_{n-2} = x_{n-1} = x_n = 1$. When $a \to +0$ the first summand and the three last summands tend to 1,
and the remaining summands tend to 0.
\end{solution}

\begin{solution} \cite{Diananda-62a}.
Note that $a^2-ab+b^2 \leq \max \{ a, b \}^2$.

Let $x_{i_1}$~be the maximal number of $x_1$, $x_2$, \dots, $x_n$.
Let $x_{i_2}$~be the maximal number of $x_{i_1+1}$ and $x_{i_1+2}$.
Let $x_{i_3}$~be the maximal number of $x_{i_2+1}$ and $x_{i_2+2}$, and so on.
There exists a number $k$ such that $x_{i_{k+1}}=x_{i_1}$.
Hence
$$
\Summa \frac{x_k^2}{x_{k+1}^2 - x_{k+1} x_{k+2} + x_{k+2}^2} \geq
\sum_{j=1}^k \frac{x_{i_j}^2}{x_{i_{j+1}}^2} \geq k \geq \Bigl[\frac{n+1}{2}\Bigr],
$$
where the latter inequality holds because $k\geq n/2$.

In order to show that the constant $\Bigl[\frac{n+1}{2}\Bigr]$ is sharp, take
  $x_k = 1$ for odd $k$ and $x_k = 0$ for even $k$. Then the left-hand side is $\Bigl[\frac{n+1}{2}\Bigr]$.
\end{solution}


{\footnotesize

\begin{thebibliography}{99}
\bibitem{VasEgorov}
{\it Васильев Н. Б., Егоров А. А.}\/ Задачи Всесоюзных математических
олимпиад. М.: Наука, 1988.
%\bibitem{Godunova-Levin}
%{\it Годунова Е. К., Левин В. И.}\/
%Об одной циклической сумме двенадцати слагаемых /\!/
%Мат. Заметки.  1976. Т.~19. \No~6. С.~873--885.
\bibitem{Drinfeld}
{\it Дринфельд В. Г.}\/
Об одном циклическом неравенстве /\!/
Мат. заметки. 1971. Т.~9. \No~2. С.~113--119.
%\bibitem{SPb2004}
%%{\it Кохась К. П., Храбров А. И., Берлов С. Л., Иванов С. В., Карпов~Д.\,В.,
%%Петров Ф. В.}\/
%Задачи Санкт-Петербургской олимпиады школьников по математике, 2004 год.
%СПб: Невский Диалект, 2004.
\bibitem{Kurlyandchik-91}
{\it Курляндчик Л. Д., Файбусович А.}\/
История одного неравенства /\!/ Квант. 1991. \No~4. С.~14--18.
\bibitem{TG}
{\it Толпыго А. К.\/} Тысяча задач Международного математического Турнира городов.
М.: МЦНМО, 2009.
%%{\it Васильев Н. Б., Константинов Н. Н., Толпыго А. К., Фомин С. В.}\/
%%Двенадцать турниров. М., 1991.
%%
%%КК. Я заменил на эту книгу. Это как бы теперь библия ТГ
%%
%\bibitem{AIH-99}
%{\it Храбров А. И.}\/
%Доказательство неравенств при помощи квазилинеаризации /\!/
%Задачи Санкт-Петербургской олимпиады школьников по математике, 1999
%год. СПб.: Изд-во СПбГУ, 1999.
%(Воспроизведена в~книге: Петербургские олимпиады школьников по математике
%2000--2002. СПб.: Невский Диалект; БХВ-Петербург, 2006. С.~374--382.
%\bibitem{AIH-03}
%{\it Храбров А. И.}\/
%И снова неравенство Коши--Буняковского /\!/
%B сб. Задачи Санкт-Петербургской олимпиады школьников по математике, 2003 год.
%СПб.: Невский диалект, 2003. С.~118--151.
%(Воспроизведена в~книге Петербургские олимпиады школьников по математике
%2003--2005. СПб.: Невский Диалект; БХВ-Петербург, 2007. С.~484--517.)
\bibitem{Chimedtseren-99}
{\it Чимэдцэрэн С.}\/
Нэгэн орчилт нийлбэр /\!/
Математикийн олимпиадын цуврал. 1999. Т.~22. (На монгольск. яз.).
\bibitem{Chimedtseren}
{\it Чимэдцэрэн С., Адъяасурен В., Батболд С.}\/
Оценка в одной циклической сумме /\!/
Монгол улсын их сургууль, Эрдэм шинжилгээний бичиг. 2000. Т. 7 (168).
С.~79--84.

%\bibitem{Bajsanski}
%{\it Baj\v{s}anski B.}\/
%A remark concerning the lower bound of
%$x_1/(x_2+x_3) + $\linebreak$+x_2/(x_3+x_4) + \ldots + x_n/(x_1+x_2)$ /\!/
%Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Math. Fiz. 1962. \No~70--76.
%P.~19--20.
%\bibitem{Bushell-Craven}
%{\it Bushell P. J., Craven A. M.}\/
%On Shapiro's cyclic inequality /\!/
%Proc. Roy. Soc. Edinburgh, 1975/76. 75A. Vol. 26. P.~333--338.
%%
%%пїЅпїЅ: пїЅпїЅпїЅ пїЅпїЅпїЅпїЅпїЅ 75пїЅ
%%
\bibitem{Bushell}
{\it Bushell P. J.}\/
Shapiro's Cyclic Sum /\!/
Bull. London Math. Soc. 1994. Vol.~26.  No~6. P.~564--574
\bibitem{Bushell-McLeod}
{\it Bushell P. J., McLeod J. B.}\/
Shapiro's cyclic inequality for even $n$ /\!/
J.~Inequal. \& Appl., 2002. Vol. 7(3). P.~331--348
%\bibitem{Clausing}
%{\it Clausing A.}\/
%A review of Shapiro's cyclic inequality /\!/
%General inequalities, {\bf 6} (Oberwolfach, 1990).
%Internat. Ser. Numer. Math. Vol. 103. Birkh\"auser, Basel, 1992. P.~17--31.
\bibitem{Cyrtioaje}
{\it C\^\i rtoaje V.}\/
Crux Mathematicorum. 2006. Vol. 32. No. 8. Problem 3195.
\bibitem{Daykin}
{\it Daykin D. E.}\/
Inequalities for certain cyclic sums /\!/
Proc. Edinburgh Math. Soc. (2) 1970/71. Vol. 17. P.~257--262.
\bibitem{Diananda-59}
{\it Diananda P. H.}\/
Extensions of an inequality of H. S. Shapiro /\!/
Amer. Math. Monthly 1959. Vol. 66. P.~489--491.
\bibitem{Diananda-61}
{\it Diananda P. H.}\/
On a conjecture of L. J. Mordell regarding an inequality involoving
quadratic forms /\!/
J. London Math. Soc. 1961. Vol. 36. P.~185--192.
\bibitem{Diananda-62}
{\it Diananda P. H.}\/
Inequalities for a class of cyclic and other sums /\!/
J.~London Math. Soc. 1962. Vol. 37. P.~424--431.
\bibitem{Diananda-62a}
{\it Diananda P. H.}\/
Some cyclic and other inequalities /\!/
Proc. Cambridge Philos. Soc. 1962. Vol. 58. P.~425--427.
\bibitem{Diananda-62b}
{\it Diananda P. H.}\/
Some cyclic and other inequalities, II /\!/
Proc. Cambridge Philos. Soc. 1962. Vol. 58. P.~703--705.
%\bibitem{Diananda-62c}
%{\it Diananda P. H.}\/
%A cyclic inequality and an extension of it, I /\!/
%Proc. Edinburgh Math. Soc. (2). 1962/63. Vol. 13. P.~79--84.
%\bibitem{Diananda-62d}
%{\it Diananda P. H.}\/
%A cyclic inequality and an extension of it, II /\!/
%Proc. Edinburgh Math. Soc. (2). 1962/63. Vol. 13. P.~143--152.
%\bibitem{Diananda-63}
%{\it Diananda P. H.}\/
%Inequalities for some cyclic sums /\!/
%J.~London Math. Soc. 1963. Vol.~38. P.~60--62.
\bibitem{Diananda-63a}
{\it Diananda P. H.}\/
On a cyclic sum /\!/
Proc. Glasgow Math. Assoc. 1963. Vol.~6. P.~11--13.
%\bibitem{Djokovic-62}
%{\it Djokovi\'c D. \v{Z}.}\/
%Sur une in\'egalit\'e /\!/
%Math. Gaz. 1962. Vol.~46. \No~356. P.~145--146.
%\bibitem{Djokovic}
%{\it Djokovi\'c D. \v{Z}.}\/
%Sur une in\'egalit\'e /\!/
%Proc. Glasgow Math. Assoc. 1963. Vol.~6. P.~1--10.
\bibitem{Elbert}
{\it Elbert A.}\/
On a cyclic inequality /\!/
Period. Math. Hungarica. 1973. Vol.~4. \No~2--3. P.~163--168.
%\bibitem{Fan-Taussky-Todd}
%{\it Fan K., Taussky O., Todd J.}\/
%Discrete analogs of inequalities of Wirtinger /\!/
%Monatsh. Math. 1957. Vol. 59. P.~73--79.
%\bibitem{Fink}
%{\it Fink A. M.}\/
%Shapiro's inequality /\!/
%Recent progress in inequalities (Ni\v{s}, 1996).
%Math. Appl. Vol. 430. Dordrecht: Kluwer Acad. Publ., 1998. P.~241--248.
%\bibitem{Freidkin}
%{\it Freidkin E. S., Freidkin S. A.}\/
%On a problem by Shapiro /\!/
%Elem. Math. 1990. Vol. 45. P.~137--139.
%\bibitem{Goldberg}
%{\it Goldberg K.}\/
%The minima of cyclic sums /\!/
%J. London Math. Soc. 1960. Vol. 35. \No\, 3. P.~262--264.
\bibitem{Malcolm}
{\it Malcolm M. A.}\/
A note on a conjecture of L.~J.~Mordell /\!/
Math. Comp. 1971. Vol.~25. P.~375--377.
\bibitem{Mitrinovich}
{\it Mitrinovi\'c D. S., Pe\v{c}ari\'c J. E., Fink A. M.}
Classical and new inequalities in analysis.
Kluwer Academic Publishers Group, Dordrecht, 1993.
(Mathematics and its Applications (East European Series), Vol.~61).
\bibitem{Mordell}
{\it Mordell L.\,J.}\/
On the inequality $\sum\limits_{r=1}^n \frac{x_r}{x_{r+1}+x_{r+2}} \geq \frac n2$ and some
others /\!/ Abh. Math. Sem. Univ. Hamburg. 1958. Vol.~22. P.~229--240.
%\bibitem{Mordell-62}
%{\it Mordell L. J.}\/
%Note on the inequality $\sum_{k=1}^n x_k/(x_{k+1}+x_{k+2}) \geq n/2$ /\!/
%J.~London Math. Soc. 1962. Vol.~37. P.~176--178.
%\bibitem{Nesbitt}
%{\it Nesbitt A. M.}\/
%Problem 15114 /\!/
%Educational Times. 1903. Vol. (2) 3. \hbox{P.~37--38}.
\bibitem{Nowosad}
{\it Nowosad P.}\/
Isoperimetric eigenvalue problems in algebras /\!/
Comm. Pure Appl. Math. 1968. Vol. 21. P.~401--465.
%\bibitem{Rankin}
%{\it Rankin R. A.}\/
%An inequality /\!/
%Math. Gaz. 1958. Vol.~42. P.~39--40.
%%
%%пїЅпїЅ: пїЅпїЅпїЅпїЅ пїЅпїЅпїЅ пїЅ пїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅ?
%%
%\bibitem{Shapiro}
%{\it Shapiro H. S.}\/
%Problem 4603 /\!/
%Amer. Math. Monthly. 1954. Vol.~61. \No~8. P.~571--572.
\bibitem{Shapiro-Northover}
{\it Shapiro H. S., Northover F. H.}\/
Amer. Math. Monthly. 1956. Vol.~63. \No~3. P.~191--192.
\bibitem{Tanahashi-Tomiyama}
{\it Tanahashi K., Tomiyama J.}\/
Indecomposable positive maps in matrix algebras /\!/
Canad. Math. Bull. 1988. Vol.~31. \No~3. P.~308--317.
%% \bibitem{Thomas}
%% Thomas D. G. S.
%% On the definitness of certain quadratic forms arising in a conjecture of
%% L. J. Mordell} /\!/
%% Amer. Math. Monthly, {\bf 68}, No ?, 1961, P.~472--473.
%% пїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅ, пїЅпїЅпїЅ пїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅ пїЅпїЅпїЅ 8, 10 пїЅ 12 пїЅпїЅ пїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅ пїЅпїЅпїЅ пїЅпїЅпїЅпїЅпїЅпїЅпїЅпїЅ,
%% пїЅпїЅпїЅпїЅпїЅпїЅпїЅ пїЅпїЅ пїЅпїЅпїЅпїЅпїЅпїЅпїЅ :-).
%\bibitem{Troesch-85}
%{\it Troesch B. A.}\/
%On Shapiro's cyclic inequality for $N=13$ /\!/
%Math. Comp. 1985. Vol.~45. \No~171. P. 199-207.
\bibitem{Troesch-85a}
{\it Troesch B. A.}\/
Full solution of Shapiro's cyclic inequality /\!/
Notices Amer. Math. Soc. 1985. Vol.~39.  \No~4. P.~318.
%\bibitem{Troesch-89}
%% For n = 15, 17, 19, 21 and 23.
%{\it Troesch B. A.}\/
%The validity of Shapiro's cyclic inequality /\!/
%Math. Comp. 1989. Vol.~53.  \No~188. P.~657--664.
\bibitem{Vukomirovich}
{\it Vukmirovi\'c J.}\/
A note on an inequality for the cyclic sums introduced by D. E. Daykin /\!/
Math. Balk. 1978. Vol. 8. P.~293--297.
\bibitem{Yamagami}
{\it Yamagami S.}\/
Cyclic inequalities /\!/
Proc. Amer. Math. Soc. 1993. Vol.~118. \No~2. P.~521--527.
\bibitem{Zulauf}
{\it Zulauf A.}\/
Note on a conjecture of L.~J.~Mordell /\!/
Abh. Math. Sem. Univ. Hamburg. 1958. Vol.~22. P.~240--241.
\bibitem{Zulauf-62}
{\it Zulauf A.}\/
Note on an Inequality /\!/
Math. Gazette. 1962. Vol.~46. \No\,355. P.~41--42.
%\bibitem{Zulauf-59}
%{\it Zulauf A.}\/
%On a conjecture of L.~J.~Mordell, II /\!/
%Math. Gaz. 1959. Vol.~43. P.~182--184.

\end{thebibliography}

}

\end{document}

 