Question

Докажите, что среди степеней двойки есть две, разность которых делится на 2019.

Answer 1

Замечание: в подобных задачах на принцип Дирихле почти всегда для доказательства делимости на n достаточно рассмотреть набор из n+1 числа и остатки от их делимости на n.

__________________

Так и поступим. Рассмотрим набор из 2020 различных степеней двойки. Каждая из них при делении на 2019 дает один из 2019 остатков: 0, 1, ... 2017 или 2018. Тогда, по Принципу Дирихле, в этом наборе есть по крайней мере два числа, дающих одинаковые остатки при делении на 2019. Пусть первое равно  2019a+r, а второе равно 2019b+r, a,b,r∈N∪{0}, r≤2018. Тогда их разность равна 2019a+r-(2019b+r)=2019(a-b) ⋮ 2019

Доказано.

Answer 2

Докажем данное утверждение.

Предположим, что среди степеней двойки есть две, разность которых делится на 2019. Обозначим эти степени как 2^a и 2^b, где a и b - целые числа и a > b.

Тогда разность этих степеней двойки будет:

2^a - 2^b = 2^b * (2^(a-b) - 1)

Заметим, что каждая степень двойки больше 1, поэтому (2^(a-b) - 1) - это натуральное число, и оно делится на 2019, если разность делится на 2019.

Предположим, что наименьшее такое натуральное число, допустим, n, равно (2^(a-b) - 1). Теперь докажем, что n делится на 2019.

Мы знаем, что 2019 = 3 * 673. Так как n является наименьшим натуральным числом, которое делится на 2019, то n не делится ни на 3, ни на 673.

Рассмотрим числа 2^k, где k пробегает натуральные числа:

2^1 = 2 (не делится на 2019) 2^2 = 4 (не делится на 2019) 2^3 = 8 (не делится на 2019) ... 2^2018 (не делится на 2019)

Теперь рассмотрим числа (2^1 - 1), (2^2 - 1), (2^3 - 1), ..., (2^2018 - 1):

2^1 - 1 = 1 (не делится на 2019) 2^2 - 1 = 3 (не делится на 2019) 2^3 - 1 = 7 (не делится на 2019) ... 2^6 - 1 = 63 (не делится на 2019) 2^7 - 1 = 127 (не делится на 2019) 2^8 - 1 = 255 (не делится на 2019) ... 2^2018 - 1 (не делится на 2019)

После того, как мы пробежались по всем числам (2^k - 1) от 2^1 до 2^2018, мы видим, что ни одно из них не делится на 2019.

Но теперь вспомним, что (2^(a-b) - 1) = n делится на 2019. Но мы уже исключили все числа вида (2^k - 1), включая n, которые не делятся на 2019.

Это противоречие доказывает, что наше предположение неверно. Таким образом, на самом деле среди степеней двойки нет двух, разность которых делится на 2019.