On the table there are written numbers $673, 674, \cdots, 2018, 2019.$ Nibab chooses arbitrarily three numbers $a,b$ and $c$, erases them and writes the number $\frac{\min(a,b,c)}{3}$, then he continues in an analogous way. After Nibab performed this operation $673$ times, on the table remained a single number $k$. Prove that $k\in(0,1).$
Problem
Source: Moldova TST 2019
Tags: combinatorics, TST, easy
08.03.2019 16:58
Here's how to crack it: Let's build a tree, such that the nodes are the numbers written on the table at any point. The root will have value $k$, the children of a node will be the 3 values we merged in one operation to get the value of that node, and the leaves will be the initial values. It's easy to see that the minimal value on each height is at least triple the minimal value of the previous height. Thus if $k>1$ then the tree's height is at most $6$. However, then we will only have at most $3^6$ leaves, which is less than the number of initial values. Thus $k \in (0,1)$.
09.03.2019 13:46
Consider the quantity $\frac{1}{a_1} + \frac{1}{a_2} + \dots + \frac{1}{a_k}$ where $a_1,a_2, \dots, a_k$ are numbers currently written on the table. This quantity is a monovariant, because every time we replace $a,b,c$ with $\frac{\min (a,b,c)}{3}$, the quantity will change by $\frac{3}{\min (a,b,c)} - \frac{1}{a} - \frac{1}{b} - \frac{1}{c} \ge 0$. So, we get that: $\frac{1}{k} \ge \frac{1}{673} + \frac{1}{674} + \dots + \frac{1}{2019} \ge \frac{1347^2}{(673+674+\dots +2019)} > 1$, where the penultimate inequality comes from CS-Engel. So, it follows that $k<1$. Since $k$ is clearly positive, so the result follows.
09.03.2019 16:18
Seicchi28 wrote: Consider the quantity $\frac{1}{a_1} + \frac{1}{a_2} + \dots + \frac{1}{a_k}$ where $a_1,a_2, \dots, a_k$ are numbers currently written on the table. This quantity is a monovariant, because every time we replace $a,b,c$ with $\frac{\min (a,b,c)}{3}$, the quantity will change by $\frac{3}{\min (a,b,c)} - \frac{1}{a} - \frac{1}{b} - \frac{1}{c} \ge 0$. So, we get that: $\frac{1}{k} \ge \frac{1}{673} + \frac{1}{674} + \dots + \frac{1}{2019} \ge \frac{1347^2}{(673+674+\dots +2019)} > 1$, where the penultimate inequality comes from CS-Engel. So, it follows that $k<1$. Since $k$ is clearly positive, so the result follows. What was you inspiration to think about this quantity?
07.10.2022 14:49
XxProblemDestroyer1337xX wrote: On the table there are written numbers $673, 674, \cdots, 2018, 2019.$ Nibab chooses arbitrarily three numbers $a,b$ and $c$, erases them and writes the number $\frac{\min(a,b,c)}{3}$, then he continues in an analogous way. After Nibab performed this operation $673$ times, on the table remained a single number $k$. Prove that $k\in(0,1).$ If we have $3$ numbers $<3$ then after the moves there is on $<1$ If we have $7$ numbers $<9$ then after the moves there is on $<1$ Generali if we have $2*3^n+1$ numbers $<3^n$ then after the moves there is on $<1$