The numbers $2, 2, ..., 2$ are written on a blackboard (the number $2$ is repeated $n$ times). One step consists of choosing two numbers from the blackboard, denoting them as $a$ and $b$, and replacing them with $\sqrt{\frac{ab + 1}{2}}$. $(a)$ If $x$ is the number left on the blackboard after $n - 1$ applications of the above operation, prove that $x \ge \sqrt{\frac{n + 3}{n}}$. $(b)$ Prove that there are infinitely many numbers for which the equality holds and infinitely many for which the inequality is strict.
Problem
Source: JBMO Shortlist 2022
Tags: Junior, Balkan, shortlist, algebra, game, Inequality
27.06.2023 15:01
Sorry for no Latex. Obviously every number always stays above 1, so we can introduce a function F(x) = 1/(x^2 - 1). To see (A) note that the sum of these functions doesn’t increase and it stays the same only when operating on two equal numbers. So for (B) one can take a power of 2.
01.07.2023 02:02
Surely easier than A4 and according to some contestants who had this problem and others in team selection tests, it is easier than A2 and A3. Strong induction on $n$, with $n=1$ being true since $2 = \sqrt{\frac{1+3}{1}}$. Suppose the statement holds for all $n<k$, where $k\geq 2$ is a given integer, and we aim for a proof when $n=k$. Let $u$ and $v$ be the numbers on the board after $k-2$ operations. Then the number after the last move is $\sqrt{\frac{uv+1}{2}}$ and we wish to prove $\frac{uv+1}{2} \geq 1 + \frac{3}{k}$, i.e. $uv \geq 1 + \frac{6}{k}$. Observe that $u$ is obtained from a set of $1 \leq t \leq k-1$ $2$s via $t-1$ operations and $v$ is obtained from the other $k-t$ $2$s via $k-t-1$ operations. Hence from the induction hypothesis we obtain $u\geq \sqrt{1 +\frac{3}{t}}$ and $v \geq \sqrt{1+\frac{3}{k-t}}$ and we reduce to showing $\sqrt{\left(1+\frac{3}{t}\right)\left(1+\frac{3}{k-t}\right)} \geq 1 + \frac{6}{k}$. The latter is equivalent to $(k-2t)^2 \geq 0$, thus completing the induction. A necessary condition for equality when $n=k\geq 2$ is $k=2t$; in particular no odd $n$ works. On the other hand, replacing all inequalities above with equalities and taking $t = \frac{k}{2}$ shows that all powers of $2$ work (in fact, by considering the above process in a tree structure we see in a similar manner that equality holds only when $n$ is a power of two and the operations correspond to a perfect binary tree).
20.03.2024 10:24
Use strong induction. Denote with $M(n)$ the expression $\sqrt{\frac{n+3}{n}}$. Further denote with $P(a,b)$ the expression $\sqrt{\frac{M(a)M(b)+1}{2}}$. Assume true for all $1,\dots,n$. We note that, after the penultimate step, we are left with two numbers which are the result of applications summing to the amount of $2$s at the start. One can verify that if $a \leq b$ then $P(a,b)\le P(a-1,b+1)$. By induction we can see that the "minimum minimum" for $a+b$ occurs at $P(a,b)$ where $a$ and $b$ are closest together. So this is true for $2n$ since we can verify $P(n,n) \geq M(2n)$. And it is also true for $2n-1$ since we can verify $P(n-1,n) \geq M(2n-1)$. We can also verify that induction with $(1,\dots,n)\to(2n-1, 2n)$ works. I know this is pretty inefficient (time and calculation-wise) but this is the solution I came up with after working on it on-and-off...
18.05.2024 23:30
27.12.2024 15:24
See Engel 1.28, ELMO Shortlist 2013 C2 and perhaps IMO Shortlist 2014 C2 for very similar problems (even the binary tree equality construction works in some of these).
01.01.2025 13:13
Trivial by induction