Show that the solution set of the inequality \[ \sum^{70}_{k = 1} \frac {k}{x - k} \geq \frac {5}{4} \] is a union of disjoint intervals, the sum of whose length is 1988.
Problem
Source: IMO 1988/4, IMO Shortlist 16, IMO Longlist 42
Tags: algebra, polynomial, Vieta, Inequality, roots, IMO, IMO 1988
17.03.2007 18:52
It is not hard. Let \[p(x)=\prod_{k=1}^{n}(x-k)^{k}. \] Then \[\sum_{k=1}^{n}\frac{k}{x-k}=\frac{p'(x)}{p(x)}. \] Consider roots of polinom $q(x)=p(x)-\frac{4}{5}p'(x)$. It had n(n-1)/2 trivial roots $2,3,3,4,4,4,...,n,n,...,n$ and n nontrivial roots $1<x_{1}<2<x_{2}<3<x_{3}<...n<x_{n}$ (n=70). It is easy to chek, that needed lengh of intervals is $L=\sum_{k=1}^{n}(x_{k}-k)$. We have $q(x)=x^{n(n+1)/2}-ax^{n(n+1)/2-1}+...$, were \[a=\sum_{k=1}^{n}k^{2}+2n(n+1)/5. \] Therefore $L=\sum_{k=1}^{n}(x_{k}-k)=a-\sum_{k=1}^{n}k^{2}=2n(n+1)/5=1988 (n=70).$ It can be prove for \[\sum_{k=1}^{n}\frac{a_{k}}{x-x_{k}}\ge a. \] Were $a_{k}>0,a>0$. Then lengs of intervals is $L=\frac{1}{a}\sum_{k=1}^{n}a_{k}$.
15.01.2009 02:09
Would this be rigorous enough? Let $ p(x)$ be the left hand side of the inequality. Consider the behavior of the graph on each interval $ (k,k+1)$. Considering the term $ \frac{k}{x-k}$, the graph starts at infinity+, and considering the term $ \frac{k+1}{x-k-1}$ tends towards infinity- as $ x$ approaches $ k+1$. Thus we have one root in each interval $ (k,k+1)$, $ 1\leq k \leq 70$ (so the intervals are disjoint). Then vietas and computation to get numeric answer.
17.10.2020 01:27
Solved with nukelauncher. I will show that the total length of the solution set to \[f(x):=\sum_{k=1}^m\frac k{x-k}\ge r\]is given by \(\frac1r\frac{m(m+1)}2\). Claim: \(f'(x)<0\), except at the discontinuities \(x=1,\ldots,m\). Proof. Each addend \(\frac k{x-k}\) is strictly decreasing except at the discontinuity \(x=k\). \(\blacksquare\) Therefore, (by intermediate value theorem) the solution set should be of the form \((1,1+\varepsilon_1)\cup(2,2+\varepsilon_2)\cup\cdots\cup(m,m+\varepsilon_m)\) for some \(0<\varepsilon_i<1\); here, \(1+\varepsilon_1\), \ldots, \(m+\varepsilon_m\) are roots of \(f(x)=r\). The goal is to evaluate \(\varepsilon_1+\cdots+\varepsilon_m\). Let \(g(x)=(x-1)^1(x-2)^2\cdots(x-m)^m\). It readily follows that \[f(x)=\frac{g'(x)}{g(x)}.\]Hence the roots of \(g'-rg\) are \(1+\varepsilon_1\), \ldots, \(m+\varepsilon_m\), and also \(k\) with multiplicity \(k-1\) for each \(k=1,\ldots,m\), so the sum of the roots of \(g'-rg\) is \((1^2+\cdots+m^2)+(\varepsilon_1+\cdots+\varepsilon_m)\). We can also use Vieta's to determine the sum of the roots of \(g'-rg\). If \(M=\binom{m+1}2\), then \begin{align*} g(x)&=x^M-\left(1^2+\cdots+m^2\right)x^{M-1}+\cdots\\ g'(x)&=Mx^{M-1}-\cdots,\quad\text{thus}\\ g'(x)-rg(x)&=-rx^M+x^{M-1}\left[M+r\left(1^2+\cdots+m^2\right)\right]+\cdots \end{align*}so the sum of the roots of \(g'-rg\) is \((1^2+\cdots+m^2)+\frac Mr\). It follows that \(\varepsilon_1+\cdots+\varepsilon_m=\frac Mr\), which is what we wanted to show.
12.12.2020 08:28
Note that $1988=\frac{70\cdot 71}{2}\div\frac{4}{5};$ we conjecture that \[\sum_{k=1}^{n}\frac{k}{x-k}\geq r\]has length $\frac{n(n+1)}{2r}$ as well. Say for convenience $\sum\limits_{k=1}^{n}\frac{k}{x-k}=f(x).$ Here's the smart part: $f'(x)<0$ where $x\neq 1,2,\ldots, n$ since all of these summands have negative derivative, and adding negative stuff together gives you a negative result. In other words, since $f(x+\epsilon)\approx \infty$ and $f((x+1)-\epsilon)\approx -\infty$ for small positive $\epsilon,$ there exist $\epsilon_i\in(0,1)$ for all $1\leq i\leq n$ such that $f(i+\epsilon_i)=r.$ Thus the sets $x\in (i,i+\epsilon_i)$ work. Now we want to find the sum of the roots of $r-f(x)=0$ minus $1+2+\cdots+n$ to finish. Let $P(x)=(x-1)(x-2)\cdots(x-n)$ for convenience. Clear the denominators to get \[rP(x)-\sum_{k=1}^{n}\frac{k}{x-k}P(x)\]and see that the coefficient of the $x^n$ term is $r,$ and the coefficient of the $x^{n+1}$ term is $-r(1+2+\cdots+n)-\sum_{k=1}^n,$ where the first term is contributed by $rP(x)$ and the second is contributed by the summation. Then we can see the sum of the roots is $\frac{r+1}{r}\cdot\frac{n(n+1)}{2};$ subtracting $1+2+\cdots+n$ gives our length as $\frac{1}{r}\cdot\frac{n(n+1)}{2},$ as desired.
30.06.2022 02:59
Define $f(x)=\tfrac{1}{x-1}+\tfrac{2}{x-2}+\cdots+\tfrac{70}{x-70}.$ Our function is undefined at $1, 2, \ldots, 70.$ Note we can split $x$ into intervals of $(-\infty, 1) \cup (k,k+1) \cup (70, \infty)$ where $k$ is an integer $[1,69].$ (so $(k, k+1)$ is the union of intervals $(1, 2) \cup (2,3) \ldots \cup (69,70)$). Consider when $x$ is in a single interval of $(k, k+1).$ As $x$ approaches $k,$ we see $\tfrac{k}{x-k}$ tends to $+\infty,$ as the numerator is positive integer and the denominator is an infinitely small positive integer. Similarly, when $x$ approaches $k+1$ we see $\tfrac{k+1}{x-(k+1)}$ tends to $-\infty.$ Therefore $f(x)$ takes on all values $(-\infty, +\infty)$ when $x \in (k, k+1).$ Then by the Intermediate Value Theorem there exists some $k<a_k<k+1$ satisfying $f(a_k)=\tfrac{5}{4}.$ Now consider intervals $(-\infty, 1)$ and $(70, \infty).$ For the former, our function is completely negative and as $x$ approaches $1$ we will have a vertical asymptote to $-\infty$ at $x=1.$ Thus the function never satisfies conditions in this range. For the second interval, our function can attain all values from $(0, \infty).$ By Intermediate Value Theorem again, there exists an $70<a_{70}<\infty$ such that $f(a_{70})=\tfrac{5}{4}.$ Therefore we have found $70$ values $a_1, \ldots, a_{70}$ where $f(a_k)=\tfrac{5}{4}.$ Further note these are all solutions as $f(x)=\tfrac{5}{4}$ has degree $70,$ so by the Fundamental Theorem of Algebra it has $70$ complex roots, and we indeed have found $70.$ It is easy to see in order for $f(x) \geq \tfrac{5}{4},$ we simply consider intervals $x \in (k, a_k).$ It follows all $(k,a_k)$ are disjoint. It suffices to compute the sum of the lengths of our intervals $(k, a_k)$ where $k$ is an integer $[1, 70].$ The sum of the lengths is $a_1+a_2+\cdots+a_{70}-(1+2+\cdots+70).$ It suffices to compute $a_1+\cdots+a_{70}.$ Let $p(x)=(x-1)(x-2)\cdots(x-70).$ By setting $f(x)=\tfrac{5}{4},$ multiplying both sides by $p(x)$ and then clearing denominators, we obtain \[4((x-2)\cdots(x-70)+(x-1)(x-3)\cdots(x-70)+\cdots) = 5(x-1)\cdots(x-70).\]It is easy to see the coefficient of the $x^{70}$ term is $5,$ and furthermore the coefficient of the $x^{60}$ term is $-5(1+2+\cdots+70)-4(1+2+\cdots+70)=-9\cdot35\cdot 71.$ By Vieta's Formula, we know $a_1+a_2+\cdots a_{70}$ is simply $\tfrac{9 \cdot 35 \cdot 71}{5}=4473.$ Thus, the sum of the lengths of all these intervals is $4473-2486=1988.$