Математикадан республикалық олимпиада, 2015-2016 оқу жылы, 10 сынып
Комментарий/решение:
Решение: Фиксируя число a, мы находим все числа b, которые удовлетворяют условию задачи. При a=1008 и a=0 любая пара {a,b} удовлетворяет условию задачи. Таких подмножеств будет 2⋅2016=4032 штук. Пусть теперь a≠1008. Тогда мы можем представить число a следующим образом: a=1008±r, где 1≤r≤1007. Отсюда имеем 2a+b=2(1008±r)+b=2016±2r+b≡b±2r,(mod2016). По условию задачи, остаток от деления 2a+b на 2016 тоже лежит в T. Следовательно, b±2r=a=1008±r . Для каждого 1≤r≤1007 существуют единственная пара {1008±r,1008∓r}.
Ответ: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
(Комментарий: Насколько мне известно, это авторское решение. Рассказал мне его мой учитель.)
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.