Determine if there exist positive real numbers $x, \alpha$, so that for any non-empty finite set of positive integers $S$, the inequality \[\left|x-\sum_{s\in S}\frac{1}{s}\right|>\frac{1}{\max(S)^\alpha}\]holds, where $\max(S)$ is defined as the maximum element of the finite set $S$.
Problem
Source:
Tags: algebra, olympic revenge, inequalities
TLP.39
20.07.2022 11:11
The answer is no.
The main idea is to consider the family of functions $\{f_n:\mathbb{R}^+\to\mathbb{R}\}_{n\in\mathbb{N}_0}$ defined recursively by $f_0(x)\equiv x^{-1}$ and
$$f_{n+1}(x)\equiv f_n(x)-f_n(x+2^n)$$
By induction on $n$, we can prove that $f^{(m)}_n(x)$ has the sign $(-1)^m$ for any $m,n\in\mathbb{N}_0$. We can also prove that $f_n(x)$ is a rational function of the form $\frac{P_n(x)}{Q_n(x)}$ for some polynomial $P_n(x)\in\mathbb{Z}[x]$ with leading coefficient $c_n=2^{\binom{n}{2}}n!$ and degree $p_n=2^n-n-1$ and monic polynomial $Q_n(x)\in\mathbb{Z}[x]$ with degree $q_n=2^n$.
In particular, we need the following three properties:
$f_n(x)$ is positive.
$f_n(x)$ is decreasing.
$f_n(x)\sim c_nx^{-(n+1)}$
For any $a<b\in\mathbb{R}^+$, $\alpha\in\mathbb{N}_0$, and $\varepsilon\in\mathbb{R}^+$, there exists $N_{a,b,\alpha,\varepsilon}$ such that for any $x\in (a,b)$ and $n > N_{a,b,\alpha,\varepsilon}$, there exists a finite set $S\subset \mathbb{N}$ such that $\max(S)\le n$ and
$$\varepsilon n^{-\alpha} > x - \sum_{s\in S}\frac{1}{s} > 0$$
This clearly solves the initial problem.
We will prove the statement by induction on $\alpha$.
The base case is easy: choose an arbitrary $n\in\mathbb{N}$ such that $\frac{1}{n} < \min\{a,\varepsilon\}$. Consider the sum $s_m=\sum_{i=n}^m \frac1i$ and let $N$ be an arbitrary positive integer such that $s_N > b$. Note that for any $x\in (a,b)$, there exists a largest integer $m_x < N$ such that $s_{m_x} < x$. This means that $\varepsilon > \frac1n > \frac{1}{m_x+1}\ge x - s_{m_x} > 0$. Thus, $N_{a,b,0,\varepsilon} = N$ works.
For the inductive step, assume that the claim is true for $\alpha = n$. Do the following steps:
Choose a large $p<1$ such that $a+\ln(p) > 0$ and $c_n\left(\left(\frac{1}{p}\right)^{n+1}-\left(\frac{2}{p+1}\right)^{n+1}\right) \ll \varepsilon$. This means that for any large $x$ and $c\in\mathbb{R}^+_0$, we have $f_n(px+c)-f_n\left(\frac{p+1}{2}x+c\right) < \varepsilon x^{-(n+1)}$
Consider a block of positive integers $(pk,k]$. Divides it into two halves, front ($\left(pk,\frac{p+1}{2}k\right]$) and back ($\left(\frac{p+1}{2}k,k\right]$). In each half, further divide it into several blocks containing $2^n$ positive integers.
For each block in the front half that begins with $x$, choose $x+i$ if and only if the coefficient of $\frac{1}{x+i}$ in $f_n(x)$ is negative. Do the opposite for each block in the back half.
Choose a positive $\varepsilon_0 \ll \frac{1-p}{2^{n+1}}\left(\left(\frac{2}{p+1}\right)^{n+1}-1\right)c_n$. Notice that if we instead chose, and only chose, the unchosen numbers from the previous two steps, then the sum of the reciprocal of all the chosen numbers would increase by more than $\frac{1-p}{2^{n+1}}k\left(f_n\left(\frac{p+1}{2}k\right)-f_n(k)\right)>\varepsilon_0 k^{-n}$.
Let $S_2$ denotes the set of all numbers already chosen. The sum of reciprocals of its elements is guaranteed to be no more than $-\ln(p)$, at least for large $k$. Moreover, according to the induction hypothesis, for any $x'\in (a+\ln(p),b)$ and large $k$ (independent of $x'$), there must exists a set $S_1$ with $\max(S_1)\le pk$ such that $\varepsilon_0 k^{-n} > x' - \sum_{s\in S_1}\frac1s > 0$. Let $x'=x-\sum_{s\in S_2}\frac 1s$ and define $S'=S_1\cup S_2$.
As long as $\sum_{s\in S'}\frac1s$ is less than $x$, keep 'flipping' -- that is, choose the unchosen numbers and discard all currently chosen numbers -- the first unflipped block in both the front and back halves. Note that by the time we flip every single block, the sum $\sum_{s\in S'}\frac1s$ will change by more than $\varepsilon_0 k^{-n}$ (as stated earlier), thus surpassing $x$, meaning that this step must stop.
Undo the last flip and consider the sum at this moment. Note that the next flip will change the sum by less than $\varepsilon x^{-(n+1)}$. As this change the sum from less than $x$ to at least $x$, we get that $x-\sum_{s\in S'}\frac 1s$ at this moment must be positive but less than $\varepsilon x^{-(n+1)}$. Done.
Ailyta
07.11.2022 13:00
is there offical answer?
Phorphyrion
12.11.2022 22:23
There's an official solutions document, attached to this message.
Attachments:
SolEnglish.pdf (88kb)
Ailyta
03.08.2023 19:00
wonderful!Is there official solutions of other years?thank you!