China Western Mathematical Olympiad 2015 ,Problem 1

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

China Western Mathematical Olympiad 2015 ,Problem 1

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: China Yinchuan Aug 16, 2015

The post below has been deleted. Click to close.

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

41454 posts

sqing

#1 h Aug 17, 2015, 6:54 AM • 2 Y

Y by Adventure10, Mango247

Let the integer $n \ge 2$ , and $x_1,x_2,\cdots,x_n$ be real numbers such that $\sum_{k=1}^nx_k$ be integer . $d_k=\underset{m\in {Z}}{\min}\left|x_k-m\right|$ , $1\leq k\leq n$ .Find the maximum value of $\sum_{k=1}^nd_k$ .

This post has been edited 1 time. Last edited by sqing, Aug 17, 2015, 6:55 AM

Z K Y

The post below has been deleted. Click to close.

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

670 posts

#2 h Aug 17, 2015, 11:18 AM • 3 Y

Y by techniqq, Adventure10, Mango247

The answer is $\left[\frac{n}{2}\right]$ .

Let $\{x_i\}=\frac{1}{2}\pm\epsilon_i,0\le\epsilon_i\le\frac{1}{2}$ .Note that $d_k=\frac{1}{2}-\epsilon_i$ .Thus $d_k\le\frac{1}{2}$ .From here we split the problem in to two cases:

Case $1$ : $n\equiv 0\pmod{2}$

Since $d_k\le\frac{1}{2}$ it follows that $\sum_{k=1}^nd_k\le\frac{n}{2}$ .The maximum of $\sum_{k=1}^nd_k$ is indeed $\frac{n}{2}$ ,with equality if and only if $\{x_1\}=\{x_2\}=...=\{x_n\}=\frac{1}{2}$ .

Note:If $\{x_1\}=\{x_2\}=...=\{x_n\}=\frac{1}{2}$ ,then $\sum_{k=1}^nx_k\in\mathbb{Z}$ ,because $\frac{n}{2}\in\mathbb{N}$ .

Case $2$ : $n\equiv 1\pmod{2}$

Suppose that form the set $\{\{x_1\},\{x_2\},...,\{x_n\}\}$ there are exactly $k$ elements smaller that $\frac{1}{2}$ .Suppose that $\{x_1\},\{x_2\},...,\{x_k\}<\frac{1}{2}$ .Then the sum $\sum_{k=1}^nx_k$ is equal to $\frac{n}{2}+\sum_{i=k+1}^{n}\epsilon_{i} -\sum_{i=1}^{k}\epsilon_{i}$ .Note that $\frac{n-1}{2}\in\mathbb{N}$ ,so the number $\frac{1}{2}+\sum_{i=k+1}^{n}\epsilon_{i} -\sum_{i=1}^{k}\epsilon_{i}$ must be an integer(because $\sum_{k=1}^nx_k$ is an integer).
Therefore $\sum_{i=k+1}^{n}\epsilon_{i} -\sum_{i=1}^{k}\epsilon_{i}=S+\frac{1}{2}$ ,for some integer $S$ .This forces that $\left|\sum_{i=k+1}^{n}\epsilon_{i} -\sum_{i=1}^{k}\epsilon_{i}\right|\ge\frac{1}{2}$ ,resulting that $\sum_{i=1}^{n}\epsilon_i\ge\frac{1}{2}$ .
Finally,we have $\sum_{k=1}^nd_k=\frac{n}{2}-(\epsilon_1+\epsilon_2+...+\epsilon_{n})\le\frac{n}{2}-\frac{1}{2}=\frac{n-1}{2}$ .The maximum of $\sum_{k=1}^nd_k$ is indeed $\frac{n-1}{2}$ .An example for which $\sum_{k=1}^nd_k=\frac{n-1}{2}$ is when $x_1=x_2=...=x_{n-1}=\frac{1}{2}$ and $x_n=0$ .(Note that if $x_1=x_2=...=x_{n-1}=\frac{1}{2}$ and $x_n=0$ ,then $\sum_{k=1}^nx_k\in\mathbb{Z}$ ,because $\frac{n-1}{2}\in\mathbb{N}$ .)

Now from the above two cases we can conclude that the maximum value of $\sum_{k=1}^nd_k$ is $\left[\frac{n}{2}\right]$ .

This post has been edited 1 time. Last edited by huricane, Aug 17, 2015, 11:19 AM

Z K Y

The post below has been deleted. Click to close.

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

178 posts

#3 h Mar 27, 2016, 7:52 AM • 2 Y

Y by Adventure10, Mango247

WLOG let all $x_i\in [0,1)$ .Note that $d_k= \left| \left\lfloor x_k +\frac{1}{2}\right\rfloor-x_k\right|$ . WLOG let $x_1,\ldots ,x_k\in \left[0,\frac{1}{2}\right), x_{k+1},\ldots , x_n\in \left[\frac{1}{2}, 1\right)$ . For $1\le i\le k$ , $d_i=x_i,$ for $k+1\le i\le n$ , $d_i=1-x_i$ .
Thus note
$\begin{align*} \sum d_i & = x_1+\ldots + x_k + (1-x_{k+1})+\ldots + (1-x_n)\\ &= n-k+x_1+\ldots + x_k - x_{k+1}-\ldots - x_n\\ &= \sum x_i + n-k -2(x_{k+1}+\ldots + x_n)\\ &\le \sum x_i \end{align*}$ where the last inequality is due to $x_i\ge \frac{1}{2}$ for $k+1\le i\le n$ .
On the other hand
$\begin{align*} n-k+x_1+\ldots + x_k - x_{k+1}-\ldots - x_n & = n-k-\sum x_i +2(x_1+\ldots +x_k)\\ &\le n-\sum x_i \end{align*}$ where the last inequality is due to $x_i\le \frac{1}{2}$ for $1\le i\le k$ .
Thus follows that $\sum d_i\le \min(\sum x_i, n-\sum x_i)\implies \sum d_i\le \left\lfloor \frac{n}{2}\right\rfloor$ since $\sum x_i$ is an integer, and the construction for $\sum d_i=\left\lfloor \frac{n}{2}\right\rfloor$ can be seen above.

Z K Y

The post below has been deleted. Click to close.

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

1721 posts

#4 h Aug 17, 2017, 10:46 AM • 2 Y

Y by Adventure10, Mango247

We will show that the answer is $\lfloor \frac{n}{2} \rfloor$ . Here's an example showing that $\lfloor \frac{n}{2} \rfloor$ is possible.

For $n$ even: $x_1= x_2 = \cdots = x_n= \frac{1}{2}$ For $n$ odd: $x_1 = x_2 = \cdots = x_n = \frac{n+1}{2n}$ .

It is easy to see that these two are indeed sufficient examples. Now we will show that this is indeed the maximum.
If $n$ is even, from the trivial fact $d_k \le \frac{1}{2}$ , we get $\sum_{k=1}^n d_k \le \frac{n}{2}$ .
If $n$ is odd, we will first replace $x_i$ with $x_i - \lfloor x_i \rfloor$ , which is a valid transformation for obvious reasons.
Then notice $d_k = \text{min}(x_i, 1-x_i) = \frac{1}{2} ( 1- |2x_i-1|)$ . This enables us to write $\sum_{k=1}^n d_k = \frac{n}{2} - \frac{1}{2} \sum_{k=1}^n |2x_k - 1|$ Meanwhile, $\sum_{k=1}^n (2x_k-1)$ is an odd integer. This shows that, by the triangle inequality, $\sum_{k=1}^n d_k = \frac{n}{2} - \frac{1}{2} \sum_{k=1}^n \left| 2x_k - 1 \right| \le \frac{n}{2} - \frac{1}{2} \left| \sum_{k=1}^n (2x_k -1) \right| \le \frac{n-1}{2}$

This post has been edited 3 times. Last edited by rkm0959, Aug 17, 2017, 11:02 AM

Z K Y

The post below has been deleted. Click to close.

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

215 posts

#5 h Aug 9, 2019, 3:55 PM • 1 Y

Y by Adventure10

Sorry but can you explain for me why $d_k = \min_{m \in \mathbb{Z}} \left|x_k - m \right| \le \frac{1}{2} \ ?$

Z K Y

The post below has been deleted. Click to close.

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

798 posts

#6 h Aug 9, 2019, 5:03 PM • 2 Y

Y by Adventure10, Mango247

Do you need a rigorous proof or is it enough to see that distance between real number and the nearest integer is at most half?

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a