Silk Road Mathematics Competition

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$.