Городская олимпиада по математике среди физ-мат школ г. Алматы, 2018 год

На уроке математики присутствует простое число учеников $p$. Учитель определил каждому ученику номер $0$ до $p-1$ и задал им следующее упражнение: каждый ученик должен посчитать сумму чисел от нуля до $k$, для каждого $k$ от $0$ до $p-1$, а затем найти остаток от деления полученной суммы на $p$. Если остаток совпадает с номером ученика, то он должен записать число $k$ в свою тетрадь. Определите, сколько учеников не запишут в свои тетради ни одного числа.

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Ответ: $0$ для $p=2$, $\dfrac{p-1}{2}$ иначе.
Решение. 1) Пусть $p=2$, тогда все ученики запишут в своей тетради число, в этом случае ответ $0$. 2) Пусть $p > 2$. Если при $k=m$ и $k=n$ ($m\ne n$ соответствующие суммы дают одинаковый остаток, то $$ \dfrac{m(m+1)}{2}\equiv\dfrac{n(n+1)}{2} $$ (все сравнимости здесь и в дальнейшем $\mod p$). Отсюда $$m^2+m\equiv n^2+n;\quad m^2-n^2\equiv n-m;\quad (m-n)(m+n)\equiv n-m; \quad(m-n)(m+n+1)\equiv 0. $$ Так как $m$ и $n$ — различные остатки, то $m\equiv-1-n\equiv p-m-n$. Получается, что остатки сумм совпадают по парам $(0, p-1)$, $(1, p-2), \ldots$, причём $\dfrac{p-1}{2}$ не имеет пары. Следовательно, различных остатков будет $\dfrac{p-1}{2}+1$, а тех учеников, которым не досталось ни одного остатка $p-\dfrac{p-1}{2}-1=\dfrac{p-1}{2}$.