let $a_{1},a_{2},\cdots,a_{6}$ be real numbers,and such $$a_{1}+a_{2}+a_{3}+a_{4}+a_{5}+a_{6}=2014$$
Find the minimum of the value $$\sum_{1\le i<j\le 6}[a_{i}+a_{j}]$$
where $[x]$ is the largest integer not greater than $x$.
My idea: since $$[x]>x-1$$
but this inequality can't solve this problem. this is Beijing university mathematics in 2014 Thank you
If $x+y+z=2014$, then
$$[x]+[y]+[z]\geq 2012$$
In fact $$[x]+[y]+[z]= [x]+[y]+[2014-x-y]=2014+[-\{x\}-\{y\}]\geq 2012$$
so $$[a_1+a_2]+[a_3+a_4]+[a_5+a_6]\geq 2012$$
we have
$$\sum_{1\le i<j\le 6}[a_{i}+a_{j}]\geq2012\times5=10060$$
Let $a_1=2012+\dfrac13,a_2=a_3=\dotsb=a_6=\dfrac13$, then $\sum[a_{i}+a_{j}]=10060$.
I am writing this as a separate answer
because I am going to formulate a more general problem
(for any number $n\geq 2$ of $a_i$'s instead of only for six,
and for any integer $b$ in place of $2014$)
and will give its solution.
$\newcommand{\floor}[1]{{\left\lfloor#1\right\rfloor}}
$$\newcommand{\fracpart}[1]{{\{#1\}}}
$$\newcommand{\RR}{\mathbb{R}}
$$\newcommand{\set}[1]{{\{#1\}}}
$
I shall write the greatest integer less than or equal to a real number $x$ as $\floor{x}$ (the floor of $x$) and the fractional part $x-\floor{x}$ of $x$ as $\fracpart{x}$.
Let $n\geq 2$ and $b$ be integers, and let $A$ be the set of all $a=(a_1,\ldots,a_n)\in\RR^n$ satisfying the condition $\sum_{i=1}^n\! a_i=b$. Find $S_\min$, the minimum of the sum $$ S(a) \::=\: \!\sum_{1\leq i<j\leq n}\!\floor{a_i+a_j} $$ over all $a\in A$.
We will see that $S_\min$ depends on $b$ in a very simple way, so that the actual value of $b$ is of little importance; the only important property of $b$ is that it is an integer.
First we reduce the problem of finding the minimum of a sum of floors
to the problem of finding the maximum of a sum of fractional parts.
We rewrite $S(a)$:
$$
S(a) \:=\: \!\sum_{1\leq i<j\leq n}(a_i+a_j)
~- \!\sum_{1\leq i<j\leq n}\!\fracpart{a_i+a_j}
\:=\: (n-1)\cdot b \,-\, T(a)~,
$$
where $T(a) := \sum_{1\leq i<j\leq n}\!\fracpart{a_i+a_j}$.
Since $\fracpart{a_i+a_j}=\fracpart{\fracpart{a_i}+\fracpart{a_j}}$,
$T(a)$ depends only on the fractional parts
$\theta_1 := \fracpart{a_1}$, $\ldots$, $\theta_n := \fracpart{a_n}$;
moreover,
$\sum_{i=1}^n\!\theta_i=b\,-\,\sum_{i=1}^n\!\floor{a_i}$ is an integer,
and $T(a)=(n-1)b-S(a)$ is an integer.
Conversely, let $m_1$, $\ldots$, $m_n$ be integers,
let $\theta_1$, $\ldots$, $\theta_n$ be real numbers in the interval $[0,1)$
such that $\sum_{i=1}^n\!\theta_i$ is an integer,
and set $a_1 := m_1+\theta_1$, $\ldots$, $a_n := m_n+\theta_n$.
Then we surely can choose (an that in many ways) the integers $m_1$, $\ldots$, $m_n$
so that we will have $\sum_{i=1}^n\!a_i=b$.
In particular it follows that
$T(\theta)=\sum_{1\leq i<j\leq n}\!\fracpart{\theta_i+\theta_j}$ is an integer;
we can see this directly, without involving the integers $m_i$,
from
$$T(\theta) \:=\: (n-1)\sum_{i=1}^n\theta_i\;-
\!\sum_{1\leq i<j\leq n}\!\floor{\theta_i+\theta_j}~.$$
What all this means is that we minimize $S(a)$ iff we maximize $T(a)=T(\theta)$,
so it suffices to solve the following problem:
Let $n\geq 2$ be an integer, and let $\Theta_n$ be the set of all $\theta=(\theta_1,\ldots,\theta_n)\in[0,1)^n$ such that $\sum_{i=1}^n\!\theta_i$ is an integer. Find the maximum $T_n$ of the sum $$ T(\theta) \::=\: \!\sum_{1\leq i<j\leq n}\!\fracpart{\theta_i+\theta_j} $$ over all $\theta\in\Theta_n$.
Since each number $T(\theta)$, for $\theta\in\Theta_n$, is an integer, their maximum $T_n$ is an integer. We have an obvious upper bound $T_n\leq{\binom{n}{2}}-1$.
We shall prove:
$T_n \,=\, (n-1)\cdot\floor{(n-1)/2}\:$ for every integer $\,n\geq 2\,$.
Note that $T_n={\binom{n}{2}}-1$ only for $n=2,\,3$; otherwise, for $n\geq 4$, we have $T_n<{\binom{n}{2}}-1$.
For a warm-up we look at the values of $T_n$ for a few small $n$.
$T_2=0$.$~$ In this case $T(\theta)=\fracpart{\theta_1+\theta_2}=0$ for all $\theta\in\Theta_2$ because $\theta_1+\theta_2$ is an integer (either $\theta_1=\theta_2=0$ or $\theta_1+\theta_2=1$).
$T_3=2$.$~$ $T(\theta)=\fracpart{\theta_1+\theta_2}+\fracpart{\theta_1+\theta_3} +\fracpart{\theta_2+\theta_3}$ is an integer less than or equal to $2$. Choosing $\theta_1=\theta_2=\theta_3=\frac{1}{3}$ we get $T(\theta)=2$.
$T_4=3$.$~$ We write $T(\theta)$ as $$ \begin{aligned} T(\theta) \:=\: ~&\fracpart{\theta_1+\theta_2} + \fracpart{\theta_3+\theta_4} +\\ ~&\fracpart{\theta_1+\theta_3} + \fracpart{\theta_2+\theta_4} +\\ ~&\fracpart{\theta_1+\theta_4} + \fracpart{\theta_2+\theta_3}~. \end{aligned} $$ The partial sum in the first row on the right hand side is $$ \sum_{i=1}^4\theta_i - \floor{\theta_1+\theta_2} - \floor{\theta_3+\theta_4}~, $$ hence an integer. The partial sums in the other two rows are likewise integers. Each of the three partial sums is an integer $\leq 1$, thus $T(\theta)\leq 3$. Choosing all $\theta_i=\frac{1}{4}$, we get $T(\theta)={\binom{4}{2}}\cdot\frac{2}{4} = 3$.
$T_5=8$.$~$
Now we write
$$
\begin{aligned}
T(\theta) \:=\:
~&\fracpart{\theta_1+\theta_2} + \fracpart{\theta_1+\theta_5}
+ \fracpart{\theta_2+\theta_3} + \fracpart{\theta_3+\theta_4}
+ \fracpart{\theta_4+\theta_5} +\\
~&\fracpart{\theta_1+\theta_3} + \fracpart{\theta_1+\theta_4}
+ \fracpart{\theta_2+\theta_4} + \fracpart{\theta_2+\theta_5}
+ \fracpart{\theta_3+\theta_5}~.
\end{aligned}
$$
Each of the partial sums in the two rows on the right hand side is
$2\sum_{i=1}^5\theta_i - (\textit{sum of floors})$,
thus is an integer $\leq 4$, whence $T(\theta)\leq 8$.
Choosing all $\theta_i=\frac{2}{5}$
we get $T(\theta)={\binom{5}{2}}\cdot\frac{4}{5}=8$.
$T_6=10$.$~$ This time we write $$ \begin{aligned} T(\theta) \:=\: ~&\fracpart{\theta_1+\theta_2} + \fracpart{\theta_3+\theta_6} + \fracpart{\theta_4+\theta_5} +\\ ~&\fracpart{\theta_1+\theta_3} + \fracpart{\theta_2+\theta_4} + \fracpart{\theta_5+\theta_6} +\\ ~&\fracpart{\theta_1+\theta_4} + \fracpart{\theta_2+\theta_6} + \fracpart{\theta_3+\theta_5} +\\ ~&\fracpart{\theta_1+\theta_5} + \fracpart{\theta_2+\theta_3} + \fracpart{\theta_4+\theta_6} +\\ ~&\fracpart{\theta_1+\theta_6} + \fracpart{\theta_2+\theta_5} + \fracpart{\theta_3+\theta_4}~. \end{aligned} $$ Each of the five partial sums is $\sum_{i=1}^5\theta_i - (\textit{sum of floors})$, thus an integer $\leq 2$, whence $T(\theta)\leq 10$. Choosing all $\theta_i=\frac{1}{3}$ we get $T(\theta)={\binom{6}{2}}\cdot\frac{2}{3}=10$.
We can already discern, from the proofs of $T_5=8$ and $T_6=10$, how the things will go on. It is also apparent that we will have to treat two cases, of an even $n$ and of an odd $n$.
Before we proceed, we introduce into the fray the complete graph $K_n$. This is the simple undirected graph on the set of vertices $V_n=\set{1,2,\ldots,n}$ whose set of edges $E_n$ consists of all two-element subsets of $V_n$. The sum $T(\theta)=\sum_{1\leq i<j\leq n}\!\fracpart{\theta_i+\theta_j}$ can be interpreted as the sum over all edges $\set{i,j}$ of $K_n$. In order to obtain the upper bound for $T(\theta)$, $\theta\in\Theta_n$, we partition the set $E_n$ of edges into subsets, and accordingly split the defining sum for $T(\theta)$ into the sum of partial sums. We do the partitioning of $E_n$ in one way when $n$ is even, and in a different way when $n$ is odd.
Case $n=2m$, $m\geq 1$: $~T_n=T_{2m}=(n-1)(m-1)$, where $m-1=\floor{(n-1)/2}$.
$\qquad$We partition $E_n$ into $n-1$ maximal matchings.
A maximal matching $M$
is a partition of the set $V_n$ of vertices into $m$ two-element subsets,
that is, into $m$ edges.
So we have $E_n$ split into the union of
pairwise disjoint maximal matchings $M_1$, $\ldots$, $M_{n-1}$.
You can see here how this splitting can be done
(it's laughably simple once you know the trick).
For any $\theta\in\Theta_n$ the number $T(\theta)$
is the sum of partial sums of $m$ terms $\fracpart{\theta_i+\theta_j}$
over each of the $n-1$ maximal matchings.
Each partial sum can be rewritten as
$\sum_{i=1}^n\!\theta_i - (\textit{sum of floors})$,
therefore it is an integer $\leq m-1$,
and it follows that $T(\theta)\leq (n-1)(m-1)$.
This upper bound is attainable:
choosing all $\theta_i=\frac{m-1}{n}$
we get $T(\theta)={\binom{n}{2}}\cdot\frac{2(m-1)}{n}=(n-1)(m-1)$.
Case $n=2m+1$, $m\geq 1$: $~T_n=T_{2m+1}=(n-1)m$, where $m=\floor{(n-1)/2}$.
$\qquad$We partition $E_n$ into $m$ graphs of permutations of $V_n$
that have no $1$-cycles and also
no $2$-cycles.
For every integer $x$ we define $x\bmod_1 n$ as follows:
if $x\bmod n>0$ then $x\bmod_1 n:=x\bmod n$,
and if $x\bmod n=0$ then $x\bmod_1 n:=n$.
For each $k=1,\,2,\,\ldots,\,m$ the translation $t_k\colon V_n\to V_n$
defined by $t_k(i):=(i+k)\bmod_1 n$ is a permutation of the set $V_n$ of vertices
that decomposes into $\gcd(n,k)$ cycles,
where each cycle is of length $n/{\gcd(n,k)}$ which is an odd integer $\geq 3$.
The corresponding graph $C_k$ consists of the $n$ edges $\set{i,t_k(i)}$, $i\in V_n$;
each vertex $i$ is an endpoint of precisely two edges in $C_k$.
Moreover, the set $E_n$ of edges is partitioned into the sets $C_1$, $\ldots$, $C_m$.
Each partial sum of $n$ terms $\fracpart{\theta_i+\theta_j}$
over the edges in any $C_k$
can be rewritten as $2\sum_{i=1}^n\!\theta_i-(\textit{sum of floors})$,
thus is an integer $\leq n-1$, whence $T(\theta)\leq (n-1)m$.
The upper bound is attainable:
choosing all $\theta_i=\frac{m}{n}$
we get $T(\theta)={\binom{n}{2}}\cdot\frac{2m}{n}=(n-1)m$.
We are through. At last we have the answer to the problem stated at the beginning of this post:
$S_\min \:=\: (n-1)\bigl(b-\floor{(n-1)/2}\bigr)~.$
The answer by Clin is correct: the minimum is 10060. One has only to fill in some details of the derivation of the lower bound $$ \sum_{1\leq i<j\leq 6}[a_i+a_j] \:\geq\: 5\cdot 2012 \:=\: 10060~. $$ The missing details are embodied in the identity $$ \begin{aligned} \sum\nolimits_{1\leq i<j\leq 6}[a_i+a_j] \:=\: &~[a_1+a_2]+[a_3+a_4]+[a_5+a_6]+\\[-.9ex] &~[a_1+a_3]+[a_2+a_5]+[a_4+a_6]+\\ &~[a_1+a_4]+[a_2+a_6]+[a_3+a_5]+\\ &~[a_1+a_5]+[a_2+a_4]+[a_3+a_6]+\\ &~[a_1+a_6]+[a_2+a_3]+[a_4+a_5]~. \end{aligned} $$ Now one uses the lower estimate, proved by Clin, $$ [a_{\pi1}+a_{\pi2}]+[a_{\pi3}+a_{\pi4}]+[a_{\pi5}+a_{\pi6}]\:\geq\: 1012 $$ for the five permutations $\pi$ that can be read off the 'rows' on the right hand side of the identity.
Re the tentative solution offered by john mangual. The tight upper bound for the sum $\sum_{1\leq i<j\leq 6}\{a_i+a_j\}$ is $10$, so it is indeed smaller than $\binom{6}{2}=15$. Mark that the fractional parts $\{a_i\}$ are not independent, they must satisfy the condition that $\sum_{i=1}^6\{a_i\}$ is an integer $\bigl($and so is then the sum $\sum_{1\leq i<j\leq 6}\{a_i+a_j\}$$\bigr)$.
Using the identity $ [x] + \{ x\} = x$, we have
$$ \sum_{1\le i<j\le 6}[a_{i}+a_{j}] + \boxed{ \displaystyle\sum_{1\le i<j\le 6} \{a_{i}+a_{j}\} }= \sum_{1\le i<j\le 6} a_{i}+a_{j} = 5 \cdot 2014 $$
In order to maximize the middle term it is certainly at most
$$ \sum_{1\le i<j\le 6} 1 = \tfrac{6\cdot 5}{2} = 15$$
How is that, $5 \cdot 2014 - 15$?
