Consider the numbers from $1$ to $32$. A game is made by placing all the numbers in pairs and replacing each pair with the largest prime divisor of the sum of the numbers of that couple. For example, if we match the $32$ numbers as: $(1, 2), (3,4),(5, 6), (7, 8),..., (27, 28),(29, 30), (31,32)$, we get the following list of $16$ numbers: $3,7,11,5,...,11,59,7$. where there are repetitions. The game continues in a similar way until in the end only one number remains. Determine the highest possible value from the number that remains at the end.
Problem
Source: Peru EGMO TST 2019 p4
Tags: Prime number, number theory, game, combinatorics, Sum
cosinechicken
01.03.2020 03:53
At each step are we allowed to rearrange the order of the numbers?
CANBANKAN
01.03.2020 04:03
cosinechicken wrote: At each step are we allowed to rearrange the order of the numbers? Yes. General strategy: try smaller cases. If the game goes from 1 to 4, then the answer is 5. Also I just want to make sure the final two numbers is divisible by a large prime and try working backwards.
CANBANKAN
01.03.2020 04:10
For 8, this works: (1,8), (2,7), (3,5) (4,6) -> 3,3,2,5 -> 5,2 -> 7 I think it can be proven that the smallest prime less than $2^n$ can be achieved given a game of $2^n$ numbers. Also note after every term the numbers are all primes so categorizing the number of 2s may be helpful.
CANBANKAN
01.03.2020 04:19
Actually I don't think checking small cases work, I think we have to use brute force and work backwards. For example, $ 59$ is impossible as a final answer because it is $2+57$. Easy but too bashy.... Though we can reduce our final answer to a few possibilities and we can binary search on the low side (if p>q and p work, only consider primes larger than p).
Jjesus
14.03.2021 21:14
any ideas?