Республиканская олимпиада по математике, 2016 год, 10 класс
Комментарий/решение:
$\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
(Комментарий: Насколько мне известно, это авторское решение. Рассказал мне его мой учитель.)
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.