# Minimizing $\sum_{i=1}^{2023}[(a_i+a_{i+1})(\frac{1}{a_i}+\frac1{a_{i+1}})+\frac1{a_ia_{i+1}}]$, where the $a_i$ are a permutation of $\{1,...,2024\}$

Let $$a_1, a_2, \ldots, a_{2024}$$ be a permutation of integers from $$1$$ to $$2024$$. Find the minimum possible value of $$\sum_{i=1}^{2023}\left[(a_i+a_{i+1})\left(\frac{1}{a_i}+\frac{1}{a_{i+1}}\right)+\frac{1}{a_ia_{i+1}}\right]$$

My approach:

\begin{align} &\sum_{i=1}^{2023}\left[(a_i+a_{i+1})\left(\frac{1}{a_i}+\frac{1}{a_{i+1}}\right)+\frac{1}{a_ia_{i+1}}\right] \tag1\\[4pt] \text{or,}\; &\sum_{i=1}^{2023}\left[(a_i+a_{i+1})\left(\frac{a_i+a_{i+1}}{a_ia_{i+1}}\right)+\frac{1}{a_ia_{i+1}}\right] \tag2\\[4pt] \text{or,}\; &\sum_{i=1}^{2023}\left[\frac{(a_i+a_{i+1})^2}{a_ia_{i+1}}+\frac{1}{a_ia_{i+1}}\right] \tag3\\[4pt] \text{or,}\, &\sum_{i=1}^{2023}\left[\frac{(a_i)^2+2a_ia_{i+1}+(a_{i+1})^2}{a_ia_{i+1}}+\frac{1}{a_ia_{i+1}}\right] \tag4\\[4pt] \text{or,}\, &\sum_{i=1}^{2023}\left[\frac{a_i}{a_{i+1}}+2+\frac{a_{i+1}}{a_i}+\frac{1}{a_ia_{i+1}}\right] \tag5 \end{align}

As, we can see $$a_ia_{i+1}$$ has to be big and $$a_i. Also, $$a_{i+1}. But this is impossible. So, we can conclude that $$a_i \approx a_{i+1}$$. So,the permutation must be $$1,2,..,2024$$ so that we can minimize the sum. If we calculate, the sum will be $$8093.99901$$ .

Conclusion:

I am uncertain with my answer. Specially, assuming the permutation $$1,2,3..,2024$$ .The answer should be rounded because the problem is taken from BDMO $$2024$$ national(secondary).Please verify my answer. If my answer is wrong, feel free to help me. Any suggestions are appreciated.

source: BDMO(Bangladesh Mathematical Olympiad) $$2024$$ national secondary question(problem no-$$6$$)

• Why must $a_i < a_{i+1}$ and also $a_{i+1} < a_i$? That's a contradiction which should suggest that your logic is faulty. Commented Aug 11 at 16:23
• Because, there are 2 fractions. One is $\frac{a_i}{a_{i+1}}$ . You want to minimize it. So, $a_i<a_{i+1}$. Another one is $\frac{a_{i+1}}{a_i}$. You also want to minimize it. So, $a_{i+1}<a_i$. I told that it is a contradiction. So $a_i$ and $a_{i+1}$ has to be approximately equal. So $a_i \approx a_{i+1}$. That's why I said the sequence is 1,2,..,2024. Commented Aug 11 at 17:11
• Note that minimizing $f(x) +g(x)$ is not the same as minimizing $f(x)$ and minimizing $g(x)$ and then adding them together. (EG Try for $f(x) = x^2, g(x) = (x-1)^2$.) That's the misconception / fallacy that you have. Commented Aug 11 at 17:18
• Checking for smaller values instead of $2024$ shows that the minimum value is attained with $a_n = n$ (or $a_n=2025-n$). Commented Aug 11 at 17:23
• @MdSalimAzad For my $f(x), g(x)$ problem, 1/ Can you write out the proof that the minimum of $g(x)$ is 1? I agree that $g(0) = 1$. 2/ I'm considering it over all reals, not just integers. That is what Sahaj was referring to "check what happens at $x = \frac{1}{2}$". They are not referring to your $a_n$ question. Commented Aug 11 at 17:41

Preamble: As conjectured by Sahaj in the comments, when 2024 is replaced with the general case $$n$$, the expression is minimized with the permutations $$(1, 2, 3, \ldots, n)$$ or $$(n, n-1, n-2, \ldots, 1)$$. It's just as easy to prove either version, so we'd prove the general case and then set $$n = 2024$$.
In fact, we'd prove a much larger generalization, then apply it to this problem. If I was writing up the solution for the competition, I'd likely have it reversed compared to this writeup.

Solution: The problem requires us to study $$f(x, y) = \frac{ (x+y)^2 + 1 }{ xy}$$ over pairs of distinct (positive) integers.

Show the following (If you're stuck, explain what you tried and why you can't push through):

1. $$f(x, y) = f(y, x)$$.
2. $$f(x, y) < f( x+1, y) \Leftrightarrow x > y$$. (Note that this isn't true over the reals. Why?)

More accurately, $$f(x, y) < f( x+1, y) \Leftrightarrow x^2 + x > y^2 + 1 \Leftrightarrow x > y$$ over the positive integers.

As it turns out, these are the only properties that we need. So, you can forget the exact form of $$f(x, y)$$ for the rest of the proof.

The expression can be written as $$\sum f( \sigma(i), \sigma(i+1) )$$. Suppose that the expression is minimized for some permutation $$\sigma ^*$$ (which need not be unique), with $$\sigma^* (i) = a_i^*$$ .

Show the following (If you're stuck, explain what you tried and why you can't push through):

1. Fix $$i > 1$$. If $$a_i ^* < a_{i+1}^*$$, then $$a _ 1 ^* < a_i ^* < a_{i+1} ^ * < a_ n ^*$$.
Similarly, if $$a_i ^* > a_{i+1}^*$$, then $$a_1^* > a_i^* > a_{i+1}^* > a_n ^*$$.

Proof by contradiction. If the desired inequality is not satisfied, then find/state a permutation with a small change, that yields a smaller total.

Further hint: Why did I state seemingly obvious observation 1? How can we use it to minimize changes to the expression?

1. If $$a_ 2 ^* < a_3 ^*$$, then $$a_i^* = i$$.
Similarly, if $$a_2^* > a_3^*$$, then $$a_i ^* = n+1 - i$$.

$$a_2 ^* < a_3^* \Rightarrow a_1 ^* < a_3^* \Rightarrow a_3 ^* < a_4^* \Rightarrow a_1^* < a_4^* \Rightarrow \ldots$$.

In particular, note that we're not showing/requiring $$\{ a_1^*, a_n^* \} = \{ 1, n\}$$ first. (Ross suggested a version of this in the comments)

Hence, we're shown the much larger generalization:

Suppose that $$f(x, y)$$ on distinct integers satisfies A/ $$f(x, y) = f(y, x)$$ and B/ $$f(x, y) < f(x+1, y) \Leftrightarrow x > y$$, then $$\sum f( \sigma(i), \sigma(i+1) )$$ is minimized at $$\sigma = (1, 2, \ldots, n)$$ and $$(n, n-1, \ldots, 1)$$.

Note: To calculate the exact numerical value, pair up terms to get a bunch of 2's, and use partial fractions for $$\frac{1}{a_i a_{i+1} }$$. I did not verify OP's value.
If I was the grader, I would accept $$\sum f(i, i+1)$$ as the answer, since that's the crux of the problem, and which is why I'm not doing the calculation explicitly.

• For the sake of completeness, the exact minimum value obtained is $8093\frac{1011}{1012}$, which matches approximately with what the OP claimed. Commented Aug 11 at 18:29
• @Sahaj While I normally argue on behalf for completeness and hence would agree with you, I also want to make it clear that I don't consider calculating the exact value as crucial. I'm aware that someone else might disagree and that could cost the solution a point. If the phrasing of the question asked for the exact numerical value (which it doesn't in OP's writeup), then that's a different scenario. Commented Aug 11 at 18:34
• What does it mean(σ)? Commented Aug 13 at 13:20
• @Sahaj My answer was $8093\frac{1011}{1012}$. Commented Aug 13 at 13:23
• @MdSalimAzad $\sigma$ is a common notation for a permutation, where we have $\sigma(i) = a_i$ for $i = 1$ to $n$. People also use $\pi$ and $\tau$. You can think of it like a function, where the input is the original value and the output is the permuted value. $\quad$ $\sigma = (a, b, c)$ in this case means $\sigma(1) = a_1 = a, \sigma(2) = a_2 = b, \sigma(3) = a_3 = c$. Commented Aug 13 at 16:19