Consider the numbers from $1$ to $16$. The "solitar" game consists in the arbitrary grouping of the numbers in pairs and replacing each pair with the great prime divisor of the sum of the two numbers (i.e from $(1,2); (3,4); (5,6);...;(15,16)$ the numbers which result are $3,7,11,5,19,23,3,31$). The next step follows from the same procedure and the games continues untill we obtain only one number. Which is the maximum numbers with which the game ends.
Problem
Source: Romanian JBTST IV 2007, problem 3
Tags: combinatorics proposed, combinatorics
13.05.2007 19:14
Hello, pohoatza wrote: Consider the numbers from $1$ to $16$. The "solitar" game consists in the arbitrary grouping of the numbers in pairs and replacing each pair with the great prime divisor of the sum of the two numbers (i.e from $(1,2); (3,4); (5,6);...;(15,16)$ the numbers which result are $3,7,11,5,19,23,3,31$). The next step follows from the same procedure and the games continues untill we obtain only one number. Which is the maximum numbers with which the game ends. Nice problem. The answer is $19$ (and not $17$, as it seems at first glance). Demo : 1) $19$ is possible : $(1,8),(2,15),(3,14),(4,13),(5,12),(6,11),(7,10),(9,16)$ $\Rightarrow $ $3,17,17,17,17,17,17,5$ $(3,17),(5,17),(17,17),(17,17)$ $\Rightarrow $ $5,11,17,17$ $(5,11),(17,17)$ $\Rightarrow $ $2,17$ $(2,17)$ $\Rightarrow $ $19$ 2) nothing above 19 is possible 2.1) Every number in the process is $\leq 31$ : It is easy to see that maximum p at a given step is $\leq$ maximum q at the previous step + 2 (equality iff q and $q+2$ are primes). And since maximum after first step is $31=16+15$ and $(31,2)\Rightarrow 11<31$, Point 2.1 is achieved. As a consequence, maximum at end of game may only be $31,29,23$ or $19$ 2.2) $31$ may only be obtained with $(31,31)$ or $(29,2)$ obvious 2.3) $29$ may only be obtained with $(29,29)$ obvious 2.4) $23$ may only be obtained with $(23,23)$ or $(29,17)$ obvious 2.5) $31$ can not be obtained From 2.2 and 2.3 above, it is clear that $31$ at end of step 4 (the last one) demands either at least 2 numbers 31 at end of step 1, either at least 4 numbers 29 at end of step 1. And this is cleary impossible. 2.6) $29$ can not be obtain From 2.3 above, $29$ at end of step 4 demands 8 numbers 29 at end of step 1, and this is impossible. 2.7) $23$ can not be obtained From 2.3 and 2.4 above, $23$ at end of step 4 demands either at least 3 numbers 29, either 2*29 and 5*23, either 8*23 at end of step 1. And this is impossible. Hence the result : $19$ -- Patrick