Silk Road Mathematics Competition competition problems

Note that $a < \sqrt{a^2 - ab + b^2} < b$ if $a < b$. That's why simplification of two successive prime numbers is equivalent to removing the maximal (from that two) number. If between prime numbers $a < b$ there is exactly one prime number $c$, then operation of simplification to pair $(a, b)$ gives $a$ or $c$. Hence, the "hole" between $a$ and $b$ can vanish or move down to one "step".

The maximal possible value is $1999$, and this value doesn't depend on first removed number $2 < q < 2003$. The algorithm of getting this number can be described as a repeating the operation of simplification to the maximal numbers of the set, except the number $2003$. Before the last operation board will have a pair $2$, $2003$ or $3$, $2003$. And last simplification gives $1999$.

Algorithm of getting the minimal number can be described as a repeating the operation of simplification to the maximal numbers of the set. If the "hole" obtained by removing the number $q$ disappear at some step, then we get the minimal number $2$, else $3$.

It is easy to see that the "hole" vanishes if $q \ge 17$. In that case the minimal number is equal to $2$. On the other hand, if $3 \le q \le 13$ then easy analysis shows that it vanishes for all steps of student; in this case, the minimal number is equal to $3$.