At first, on a board, the number $1$ is written $100$ times. Every minute, we pick a number $a$ from the board, erase it, and write $a/3$ thrice instead. We say that a positive integer $n$ is persistent if after any amount of time, regardless of the numbers we pick, we can find at least $n$ equal numbers on the board. Find the greatest persistent number.
Problem
Source:
Tags: romania, EGMO, combinatorics
starchan
15.02.2022 14:52
gg nice problem
Clearly any number that ever appears on the board is of the form $1/3^{i}$ for some $i$. Further the sum of the numbers on the board, is fixed, it is always $100$. Letting $a_i$ denote the number of copies of $1/3^{i}$ at a certain fixed moment we have: \[100 = \sum_{i \geqslant 0} \frac{a_i}{3^i}\]Let $K$ be the greatest persistent number. Then clearly there exists a valid arrangement of the board such that each $a_i \leqslant K$. This yields $100 \leqslant \sum_{i \geqslant 0} \frac{K}{3^i} = 3K/2$ giving $K \geqslant 200/3 > 66$ and so $K \geqslant 67$. This proves that no matter what at least $67$ numbers on the board are equal. Now let us show that $68$ is not persistent, by displaying a set of moves that gives us a position where no $68$ numbers are all equal. Pick $33$ of the original ones and do the tripling. Now we have $99$ 1/3s. Pick the first $32$ of these and triple again. Now we have $96$ 1/9s. As we can clearly see each time picking $n-67$ people and performing a tripling is reducing the numbers we have each time. Thus eventually we will overcome and odds and come up with a nice construction.
the last part is badly handwaved although continuing the inductive approach there does work.
R8kt
15.02.2022 14:53
I claim the answer is 67. Upper bound: just simple construction shows that it’s possible for n =< 67. Lower bound: Say at some point, there are at max 66 of each amount then. The sum a1 * 1 + a2* (1/3) + a3*(1/9)… <= 66 ( 1 + 1/3 + 1/9…) = 66(3/2) = 99 < 100 contradiction (since the sum is invariant).
Ru83n05
12.03.2022 16:29
https://artofproblemsolving.com/community/c6h1159663p5515606
jasperE3
11.06.2022 02:54
We claim that the greatest $n$ is $67$. First, we show that we can always find at least $67$ equal numbers. Suppose that at some point that there are at most $66$ of each number, and that there are $m$ numbers written on the board. Then, note that each number written on the board is of the form $\frac1{3^i}$ for some integer $i$. Let $a_i$ be the number of times $\frac1{3^i}$ is written on the board for any $1\le i\le m$. Now note that $\sum_{i=1}^m\frac{a_i}{3^i}=100$, since the sum of the numbers on the board is always the same. Then: $$100=\sum_{i=1}^m\frac{a_i}{3^i}\le\sum_{i=1}^m\frac{66}{3^i}\le\sum_{i=1}^\infty\frac{66}{3^i}=99$$which is a contradiction.
Next, choose $29$ of the $\frac19$'s, erase them, and instead write $87$ $\frac1{81}$'s. Next, choose $20$ of the $\frac1{81}$'s, erase them, and instead write $60$ $\frac1{243}$'s.
At this point, we have $67$ each of $1,\frac13,\ldots,\frac1{81}$ and $60$ of $\frac1{243}$.
john0512
12.01.2023 20:45
The answer is 67. If there were at most 66 of each number, then the sum cannot exceed 66(1+1/3+1/9....)=99. However, note that the total sum is invariant at 100, so this cannot happen, contradiction. Take a configuration with 67 1's, 67 1/3s, 67 1/9s, 67 1/27s, and 60 1/81s. This configuration is achivable by doing 1 -> 1/3 33 times, then doing 1/3 -> 1/9 32 times, 1/9 -> 1/27 29 times, and finally 1/27 -> 1/81 20 times. In this configuration, there are no more than 67 of each number, so 68 and higher do not work. Therefore the answer is 67.
cursed_tangent1434
24.12.2023 16:38
We claim that the answer is 67. Now, we look at the following grid. $1$ $\frac{1}{3}$ $\frac{1}{9} \dots $ $a_1$ $a_2$ $a_3 \dots $ where, $a_1$ is the number of occurrences of each number currently on the board. By way of contradiction, assume we can eventually have almost 66 of each number. It is clear that the order of moves is irrelevant. So, if there exists a sequence of moves, which allows almost 66 of each number to remain then, we simply consider the rearranged version of these moves such that moves on larger weighted numbers are done first. Now, if we at some point have a column with at least 100, then, in order to make this value below 67 at least 34 moves must be made on this column (the relevant number must be chosen at least 34 times). But, when 1 move is done on the $n^{th}$ column, the value of the $n+1^{th}$ column increases by 3. Thus, the neighbouring column increases by at least $3 \times 34=102$. Thus, we are again left with a column with value atleast 100. Thus, it is impossible to have no columns with value less than 100, if we wish to have each value less than 67. Thus, this is a clear contradiction and it is impossible to make each column have almost 67 numbers. To see why we can't do better than 67, simply consider doing 33 moves on 1, 32 moves on $\frac{1}{3}$, 29 moves on $\frac{1}{9}$ and 20 moves on $\frac{1}{27}$. This leaves us with 67 1s, 67 1/3s, 67 1/9s, 67 1/27s and 60 1/81s.