Республиканская олимпиада по математике, 2016 год, 10 класс


Найдите количество таких непустых подмножеств $T$ множества $S=\left\{ 0,1,2\ldots ,2015 \right\}$, что для любых двух элементов $a,b\in T$ (не обязательно различных) остаток от деления $2a+b$ на $2016$ тоже лежит в $T$. ( Е. Байсалов )
посмотреть в олимпиаде

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

пред. Правка 3   0
2020-05-20 20:36:27.0 #

$\textbf{Решение:}$ Фиксируя число $a$, мы находим все числа $b$, которые удовлетворяют условию задачи. При $a=1008$ и $a=0$ любая пара $\left\{ a,b\right\}$ удовлетворяет условию задачи. Таких подмножеств будет $2\cdot 2016=4032$ штук. Пусть теперь $a\ne1008$. Тогда мы можем представить число $a$ следующим образом: $a=1008\pm r$, где $1\leq r \leq 1007$. Отсюда имеем $2a+b=2(1008\pm r)+b=2016\pm 2r+b \equiv b \pm 2r, (mod 2016)$. По условию задачи, остаток от деления $2a+b$ на $2016$ тоже лежит в $T$. Следовательно, $b \pm 2r=a=1008\pm r$ . Для каждого $1\leq r \leq 1007$ существуют единственная пара $\left\{ 1008 \pm r, 1008 \mp r \right\}.$

$\textbf{Ответ:} \quad 4032+ 1007=5039$