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

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

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

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

В решении $f(x) = x \pmod{2016} \quad \forall x \in \mathbb{N}$ и $P(a,b)$ обозначает, что $2a + b \in \mathbb{T}$, где $a,b \in \mathbb{T}$. Теперь рассмотрим произвольное множество $\mathbb{T}$, удовлетворяющее условию.

Лемма 1:

Если $a \in \mathbb{T}$, тогда $$\{f(3a), f(5a), ..., f(2015a)\} \in \mathbb{T}.$$

Доказательство:

$$P(a,a): f(3a) \in \mathbb{T}.$$

$$P(a,f(3a)): 2a + f(3a) \equiv 5a \equiv f(5a) \pmod{2016} \Rightarrow f(5a) \in \mathbb{T}$$

Аналогично, индукцией можно доказать, что $f((2k-1)a) \in \mathbb{T} \quad \forall k = 1, 2,..., 1008$. Лемма 1 доказана.

Лемма 2:

Пусть $d$ - наименьший элемент множества $\mathbb{T} / \{0\}$. Тогда $d \mid 2016.$

Доказательство:

Докажем от противного. Пусть $2016 = qd + r, \ 0 < r < d.$ Из леммы 1 знаем, что если $2 \mid q$, то $(q+1)d \equiv \ d-r \pmod{2016} \Rightarrow d-r \in \mathbb{T}$, что противоречит минимальности $d$. Если же $2 \mid q+1$, то $2015qd \equiv r \pmod{2016}$, опять получили противоречие. Лемма 2 доказана.

Лемма 3:

Пусть $d$ - наименьший элемент множества $\mathbb{T} / \{0\}$. Тогда $d \mid a \quad \forall a \in \mathbb{T}.$

Доказательсво:

Предположим это не так. В таком случае существует $a \in T, \ a = qd + r, \ 0<r<d$.

$$P(2015d, a): f(4030d + qd + r) = f(-2d + qd + r) \equiv (q-2)d + r \pmod{2016} \Rightarrow f((q-2)d + r) \in \mathbb{T}$$

$$P(2015d, f((q-2)d+r)): f(4030d + (q-2)d + r) \equiv (q-4)d + r \pmod{2016} \Rightarrow f((q-4)d + r) \in \mathbb{T}$$

Аналогично, индукцией можем доказать, что $r \in \mathbb{T}$, если $2 \mid q$, или же $f(-d+r) \in \mathbb{T} \ \Rightarrow d-r \ \in \mathbb{T}$, если $2 \mid q+1$. Но $r<d$ и $d-r < d$, что противоречит минимальности элемента $d$. Лемма 3 доказана.

Теперь есть два случая для произвольного множества $\mathbb{T}$:

1. $0 \in \mathbb{T}, \ \mathbb{T} \neq \{0\}$

2. $0 \notin \mathbb{T}$

Случай 1:

Утерждение 1:

Если $a$ - произвольный элемент $\mathbb{T}$, то $$f(ka) \in \mathbb{T} \ \forall \ 0 \leq k \leq 2015.$$

Доказательство: $$P(a,a): f(2a) \in \mathbb{T}$$

$$P(a, f(a)): 2a + f(2a) \equiv 4a \equiv f(4a) \pmod{2016}$$

Как и в доказательстве леммы, с помошью индукции можем легко получить, что $f(2ka) \in \mathbb{T} \quad \forall k = 0, 1, ..., 1007$. Из этого и леммы 1 получаем утверждение 1.

Итог:

Из всех лемм и утверждения 1 становится понятно, что $$\mathbb{T} = \{0,d,f(2d),f(3d), ..., f(2015d)\}.$$ То есть $\mathbb{T}$ полностью задается минимальным ненулевым элементом $d$, где $d$ - делитель 2016. Следовательно таких множеств ровно столько же, сколько и делителей числа 2016 без числа 2016, то есть 35.

Случай 2:

Утверждение 2:

Пусть $d$ - наименьший элемент множества $\mathbb{T} / \{0\}$. Тогда число $\frac{2016}{d}$ четно.

Доказательство:

Если это не так, то $d = 32k$ для какого-то $k \in \mathbb{N}$. По лемме 1 $f(63d) = f(2016k)=0 \in \mathbb{T}$, противоречие.

Утверждение 3:

$2kd \notin \mathbb{T} \quad \forall k=0,1,2,...,1007$.

Доказательство:

Докажем от противного. Пусть $2kd \in \mathbb{T}$ для какого-то натурального $k$. Из леммы 1 $f(2015d) = f(-d) \in \mathbb{T}$. Тогда $$P(f(-d),2kd): f(2k-2)d \in \mathbb{T}.$$

Так можно индукцией доказать, что $0 \in \mathbb{T}$, противоречие.

Итог:

Из всех лемм и утверждений 2 и 3 становится понятно, что $T = \{d,f(3d),f(5d),...,f(2015d)\}$, то есть такие множества $T$ задаются своим наименьшим элементом - делителем $2016/2 = 1008$. Тогда количество таких множеств в точности равно количеству делителей $1008$, то есть 30.

Также остался вариант когда $T =\{0\}$, который, очевидно, удовлетворяет условию.

Поэтому ответ 66

(Комментарий: Насколько мне известно, это авторское решение. Рассказал мне его мой учитель.)

Лемма 3 доказана не корректно:

Если $2\mid q,$ то $(q+1)d=qd+d=a+d-r,$ что не обязательно $\equiv d-r\pmod {2016}.$

Второй случай не верен по тем же причинам.

Спасибо, доказательство леммы 3 исправлено.

Опечатка в "Итоге", вместо $2016-d$ должно быть просто $2015d.$ Так же стоит отметить, что такие $d$ действительно являются наименьшим элементом такого подмножества, но не суть. Классное решение