Silk Road Mathematics Competition

Answer: 2. Let's consider the subset $S=\{(p+1)/2,\dots ,p-2,p-1\}$. Then $${\Pi }_s=(-1{)}^{\frac{p-1}{2}}\left(\frac{p-1}{2}\right)!=-\left(\frac{p-1}{2}\right)!\equiv a(\mathrm{mod}p),$$ $${\overline{\Pi }}_s=\left(\frac{p-1}{2}\right)!\equiv -a(\mathrm{mod}p).$$ By the Wilson's theorem $a^2\equiv 1(\mathrm{mod}p)$. Hence, two cases are possible: Case 1. $a\equiv 1(\mathrm{mod}p)$. Then the deviation of the essential subset $S$ is equal to ${\Delta }_s=2(\mathrm{mod}p)$. Case 2. $a\equiv -1(\mathrm{mod}p)$. Then the deviation of the essential subset $T$, where $T$ is obtained from $S$ by substituting $\frac{p+1}{2}$ to $\frac{p-1}{2}\equiv -\frac{p+1}{2}(\mathrm{mod}p)$, is equal to ${\Delta }_T={\Pi }_T-{\overline{\Pi }}_T\equiv 1-(-1)\equiv 2(\mathrm{mod}p)$. Now we prove that $2$ is the least possible remainder. Note that ${\Pi }_s\cdot {\overline{\Pi }}_s=-1$ by the Wilson's theorem again. Since $-1$ is not a quadratic residue by modulo a prime number of the kind $4k+3$, we have certainly ${\Pi }_s\ne {\overline{\Pi }}_s(\mathrm{mod}p)$. In other words, the deviation is not divisible by $p$. Suppose to the contrary, let $S$ be a subset with deviation ${\Pi }_s-{\overline{\Pi }}_s=1$. Then ${\Pi }_s\equiv m+1(\mathrm{mod}p)$, ${\overline{\Pi }}_s\equiv m(\mathrm{mod}p)$ for some $m\in \{2,3,\dots ,p-3\}$ and $m^2+m\equiv -1(\mathrm{mod}p)$. This implies $m^3\equiv 1(\mathrm{mod}p)$ and by the Fermat's (little) theorem $p-1$ is divisible by $3$, which is a contradiction.