Processing math: 65%

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


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

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

Комментарии от администратора Комментарии от администратора №1.     Ответ: 0 для p=2, p12 иначе.
Решение. 1) Пусть p=2, тогда все ученики запишут в своей тетради число, в этом случае ответ 0. 2) Пусть p>2. Если при k=m и k=n (mn соответствующие суммы дают одинаковый остаток, то m(m+1)2n(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}.