Let $m$ and $n$ be two positive integers for which $m<n$. $n$ distinct points $X_1,\ldots , X_n$ are in the interior of the unit disc and at least one of them is on its border. Prove that we can find $m$ distinct points $X_{i_1},\ldots , X_{i_m}$ so that the distance between their center of gravity and the center of the circle is at least $\frac{1}{1+2m(1- 1/n)}$.
Problem
Source: Romania TST 2012, Problem 3
Tags: inequalities, vector, algebra proposed, algebra
17.05.2012 18:53
I think this should go in combinatorics, as it is combinatorial geometry... [Amir Hossein: Done.] (unless, of course, it turns out to be a massive complex bash- I haven't tried this problem so I do not know).
17.05.2012 22:42
First remark that for this problem it suffices to consider the $X_i$ to be collinear with at least one point on the endpoints. To see why, take the projection of all the $X_i$ onto a line through the center and at least one of the points on the border and the center of masses's distances from the center all decrease. Hence we re-formulate the problem as follows : given $n$ distinct real numbers $x_1,x_2,...,x_n \in [-1,1]$ where $x_1 = 1$, show that for each $m<n$ we can choose $m$ values $x_{i_1},x_{i_2},...,x_{i_m}$ such that $\left | \frac{\sum_{j=1}^m x_{i_j}}{m} \right | \ge \frac{1}{1+2m(1-1/n)}$ To prove this is *fairly* simple. We require $\left | \sum_{j=1}^m x_{i_j} \right | \ge \frac{1}{2 - 2/n + 1/m}$ Let $a$ be the number of $x_i$ which are positive, and so $n-a$ be the number of $x_i$ where are negative. Let $x_1,x_2,...,x_a$ be the positive ones. WLOG let $x_1 \ge x_2 \ge ... \ge x_{n-1} \ge x_n$. By choosing all of the $i_j$ to be such that $x_{i_j}$ are positive we get the center of mass is at least $\frac{1}{m} > \frac{1}{1 + 2m(1 - 1/n)}$ away from the center, and hence we are done with $m \le a$. Choose $x_1,x_2,...,x_m$ as the $m$ $x_i$ until it breaks, i.e. when $\left | \sum_{i=1}^m x_{i} \right | < \frac{1}{2 - 2/n + 1/m}$. Then I claim that choosing $x_n,x_{n-1},...,x_{n-m+1}$ has a sufficiently high center of mass to satisfy the problem. The fact that the inequality broke implies that $|x_m| \ge \frac{1 - \frac{1}{1+2m(1-1/n)}}{m-a}$ Now if $n-m+1 \ge m$, we have the center of mass of $x_n,...,x_{n-m+1}$ is at least $\frac{1 - \frac{1}{1+2m(1-1/n)}}{m-a} \ge \frac{1}{1+2m(1-1/n)}$ If $m > n-m+1$, then it's not hard to show the center of mass is at least $\frac{\frac{1 - \frac{1}{1+2m(1-1/n)}}{m-a} \cdot (n-m) + 1 - \frac{1}{1+2m(1-1/n)}}{m}$ $ = \left ( 1 - \frac{1}{1 + 2m(1 - 1/n)} \right ) \cdot \frac{n-a}{m(m-a)}$ Hence it suffices to show $\frac{n-a}{m(m-a)} \ge \left (1 + \frac{n-a}{m(m-a)} \right ) \frac{1}{1 + 2m(1-1/n)}$ which after a lot of algebra (show it's equivalent to $\frac{2m(n-a) \cdot \frac{n-1}{n} - m(m-a)}{m(m-a)(2m \cdot \frac{n-1}{n} + 1)} \ge 0$ is true) iff: $2(n-a) \cdot \frac{n-1}{n} \ge (m-a)$ which is trivial since $\frac{n-1}{n} \ge \frac{1}{2}$, $n > m$ and hence we are done. NOTE : This proof looks ugly, but all of the steps are pretty obvious because even though they are very weak bounds, they must hold if the problem is true.
18.05.2012 05:45
Well, yugrey, I put it in the algebra section because either of the two solutions I know are absolutely algebraic. So you may move it back to algebra.
18.05.2012 08:44
yugrey wrote: I think this should go in combinatorics, as it is combinatorial geometry ... (unless, of course, it turns out to be a massive complex bash - I haven't tried this problem so I do not know). Drytime wrote: Well, yugrey, I put it in the algebra section because either of the two solutions I know are absolutely algebraic. So you may move it back to algebra. Indeed; moved back to algebra, where it belongs (the official solution even offers a generalization for vectors in a normed vector space over $\mathbb{C}$). It only has a combinatorial flavour.
27.01.2018 07:54
dinoboy wrote: If $m > n-m+1$, then it's not hard to show the center of mass is at least $\frac{\frac{1 - \frac{1}{1+2m(1-1/n)}}{m-a} \cdot (n-m) + 1 - \frac{1}{1+2m(1-1/n)}}{m}$ $ = \left ( 1 - \frac{1}{1 + 2m(1 - 1/n)} \right ) \cdot \frac{n-a}{m(m-a)}$ I don't understand this part.