Processing math: 27%

Математикадан республикалық олимпиада, 2015-2016 оқу жылы, 10 сынып


Кез келген a,bT үшін (a мен b әртүрлі болуы міндетті емес), 2a+b санын 2016-ға бөлгендегі қалдығы да T-да жататындай, S={0,1,2,2015} жиынының бос емес қанша T ішкі жиыны бар? ( Е. Байсалов )
посмотреть в олимпиаде

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

пред. Правка 3   3
4 года 11 месяца назад #

Решение: Фиксируя число a, мы находим все числа b, которые удовлетворяют условию задачи. При a=1008 и a=0 любая пара {a,b} удовлетворяет условию задачи. Таких подмножеств будет 22016=4032 штук. Пусть теперь a1008. Тогда мы можем представить число a следующим образом: a=1008±r, где 1r1007. Отсюда имеем 2a+b=2(1008±r)+b=2016±2r+bb±2r,(mod2016). По условию задачи, остаток от деления 2a+b на 2016 тоже лежит в T. Следовательно, b±2r=a=1008±r . Для каждого 1r1007 существуют единственная пара {1008±r,1008r}.

Ответ:4032+1007=5039

пред. Правка 4   5
4 года назад #

В решении 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

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

  5
4 года назад #

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

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

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

пред. Правка 2   0
4 года назад #

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

пред. Правка 3   5
4 года назад #

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