4
$\begingroup$

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<a_{i+1}$. Also, $a_{i+1}<a_i$. 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$)

$\endgroup$
15
  • $\begingroup$ 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. $\endgroup$
    – Calvin Lin
    Commented Aug 11 at 16:23
  • $\begingroup$ 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. $\endgroup$
    – Math12
    Commented Aug 11 at 17:11
  • 2
    $\begingroup$ 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. $\endgroup$
    – Calvin Lin
    Commented Aug 11 at 17:18
  • $\begingroup$ Checking for smaller values instead of $2024$ shows that the minimum value is attained with $a_n = n$ (or $a_n=2025-n$). $\endgroup$
    – Sahaj
    Commented Aug 11 at 17:23
  • 1
    $\begingroup$ @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. $\endgroup$
    – Calvin Lin
    Commented Aug 11 at 17:41

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ For the sake of completeness, the exact minimum value obtained is $8093\frac{1011}{1012}$, which matches approximately with what the OP claimed. $\endgroup$
    – Sahaj
    Commented Aug 11 at 18:29
  • 1
    $\begingroup$ @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. $\endgroup$
    – Calvin Lin
    Commented Aug 11 at 18:34
  • $\begingroup$ What does it mean(σ)? $\endgroup$
    – Math12
    Commented Aug 13 at 13:20
  • $\begingroup$ @Sahaj My answer was $8093\frac{1011}{1012}$. $\endgroup$
    – Math12
    Commented Aug 13 at 13:23
  • $\begingroup$ @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$. $\endgroup$
    – Calvin Lin
    Commented Aug 13 at 16:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .