Given that $a_1, a_2, \dots, a_{10}$ are positive real numbers, determine the smallest possible value of \[\sum \limits_{i = 1}^{10} \left\lfloor \frac{7a_i}{a_i+a_{i+1}}\right\rfloor\]where we define $a_{11} = a_1$. Proposed by Sutanay Bhattacharya
Problem
Source: India EGMO TST 2024/2
Tags: algebra, floors, Summation, Egmo tst
starchan
31.12.2023 16:40
a very funny problem
Denote by $r_i$ the ratio $a_{i+1}/a_i$. The problem is equivalent to minimising: \[\sum_{i = 1}^{10} \left\lfloor \frac{7}{1+r_i}\right\rfloor\]over the constraint that the $r_i$ are positive real numbers with product $1 ~$. We show that the required minimum is $6$, achieved when: \[r_1 = 10^{-9}, r_2 = r_3 = \dots = r_{10} = 10\]The first term evaluates to $6$, while the others evaluate to $0$. Suppose otherwise, and that there exist positive reals $r_i$ with product $1$ such that\[\sum_{i = 1}^{10} \left\lfloor \frac{7}{1+r_i}\right\rfloor < 6\]Without losing generality, let us assume $r_1 < r_2 < \dots < r_{10}$. If $r_j \leq 6$ for some index $j$, then \[\sum_{i = 1}^{10} \left\lfloor \frac{7}{1+r_i}\right\rfloor \geq \sum_{i = 1}^{j} \left\lfloor \frac{7}{1+r_i}\right\rfloor \geq j\]implying that $j < 6$ or that $j \leq 5$.
In particular, $r_i > 6$ for $i > 5$. This means that \[r_1^5 < r_1r_2\dots r_5 = \frac{1}{r_6r_7\dots r_{10}} < 6^{-5}\]This implies that $r_1 < 1/6$. But now \[\left\lfloor \frac{7}{1+r_1}\right\rfloor \geq \left\lfloor \frac{7}{1+(1/6)}\right\rfloor = 6\]a plain contradiction. The required minimum is therefore $6$.
I think the problem is funny, because my solution seems to use the constants $7, 10$.
Tintarn
02.01.2024 19:07
starchan wrote: I think the problem is funny, because my solution seems to use the constants $7, 10$. In fact, one can replace $7,10$ by any $m,n$ with $n \ge 2m-4$ in your argument (and the resulting bound will be $m-1$ in that case). However, as you might have guessed, the problem remains true for general $m,n$ with $n \ge 2$ i.e. we always have that \[\sum_{i=1}^n \left\lfloor \frac{ma_i}{a_i+a_{i+1}}\right\rfloor\]has its minimum at $m-1$.
As before, we can choose the $a_i$ to be a geometric sequence with sufficiently large ratio to make $n-1$ of the summands $0$ and the remaining one $m-1$. For the lower bound, again it suffices to prove that
\[\sum_{i=1}^n \left\lfloor \frac{m}{1+r_i}\right\rfloor \ge m-1\]whenever the product of the $r_i$ is at most $1$. But then it suffices to consider $n=2$ since there are certainly two $r_i$ with product at most $1$ (take the smallest two).
But if $\left\lfloor\frac{m}{1+r_1} \right\rfloor=m-d-1$, this means that $\frac{m}{1+r_1}<m-d$ and hence $1+r_1>\frac{m}{m-d}$ and hence $r_1>\frac{d}{m-d}$ and hence $r_2 <\frac{m-d}{d}$ and hence $\frac{m}{1+r_2}>d$ so that $\left\lfloor \frac{m}{1+r_2}\right\rfloor \ge d$ as desired.
Rg230403
03.01.2024 08:39
The official document has three different proofs for the lower bound (getting increasingly better conditions on $m,n$ instead of $7,10$): We use the variable $x_i$ for the ratio $\frac{a_{i+1}}{a_i}$ across all solutions and $z_i=\left\lfloor{\frac{7a_i}{a_i+a_{i+1}}}\right\rfloor=\left\lfloor{\frac{7}{1+x_i}}\right\rfloor$. We now have that $\prod x_i=1$. Proof 1. (due to Sutanay Bhattacharya) We claim that the minimum is $6$. Thus, if there are at least $6$ $x_i$s $\le 6$ then, the corresponding $z_i$s are at least $1$ so we will be done. Else, there are $5$ $x_i$s $>6$. But since the product of all $x_i$s is $1$, there is at least some $i$ such that $x_i<\frac{1}{6}$. Thus, the corresponding $z_i\ge 6$ and we are done! This proof crucially used $7$ and $10$. Proof 2. (due to Ananya Ranade and Aditi Muthkhod) If there are $2$ $x_i$s $ \le 1$, as they will each give sum at least $3$. Thus, exactly $1$ $x_i\le 1$, WLOG this is $x_1$. All others are $>1$. Now, if any $x_i>6$, then, $x_i<\frac{1}{6}$ since $\prod x_i =1$. Thus, $x_i\le 6$ for all $i$ and thus, the corresponding $z_i$s are atleast $1$ and the proof goes through. This version of the proof uses the fact that $n\ge m$ and $m$ odd but some work lets us remove the odd condition. This is still not general though. The final proof which is arguably the simplest directly works in full generality with $m,n\ge 2$. Proof 3. (by Prethusha P) WLOG, $a_{10}$ is the largest amongst all $a_i$. Now, \[\sum_{i=1}^{10} \left\lfloor{}\frac{7a_i}{a_i+a_{i+1}}\right\rfloor{}\ge \left\lfloor{}\frac{7a_1}{a_1+a_{2}}\right\rfloor+\left\lfloor{}\frac{7a_{10}}{a_{10}+a_{1}}\right\rfloor{}\ge \left\lfloor{}\frac{7a_1}{a_1+a_{10}}\right\rfloor+\left\lfloor{}\frac{7a_{10}}{a_{10}+a_{1}}\right\rfloor{} \ge \left\lfloor{}\frac{7(a_1+a_{10})}{a_{10}+a_1}\right\rfloor{}-1\ge 6\] We just use the fact that $\lfloor{x}\rfloor + \lfloor{y}\rfloor \ge \lfloor{x+y}\rfloor -1$.