Question

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

Answer 1

Рассмотрим набор из некоторых 2014 различных степеней двойки. Каждая при делении на 2013 может давать один из 2013 остатков (0, 1, ... 2012).

Тогда, по Принципу Дирихле, в этом наборе есть хотя бы 2 числа, дающих одинаковые остатки при делении на 2013. Пусть первое равно (2013 * a + r), а второе равно (2013 * b + r), где a, b, r - целые неотрицательные числа, r < 2013.

Тогда их разность равна (2013 * a + r) - (2013 * b + r) = 2013 * (a - b) - т.е. в таком наборе обязательно найдутся две степени двойки, разность которых кратна 2013

Ч.т.д.

Answer 2

Давайте рассмотрим последовательность степеней двойки: 2^0, 2^1, 2^2, 2^3, 2^4, и так далее. Для удобства обозначим эти степени как a_0, a_1, a_2, a_3, a_4 и так далее.

Рассмотрим разности между соседними степенями: D_1 = a_1 - a_0 = 2^1 - 2^0 = 2 - 1 = 1, D_2 = a_2 - a_1 = 2^2 - 2^1 = 4 - 2 = 2, D_3 = a_3 - a_2 = 2^3 - 2^2 = 8 - 4 = 4, D_4 = a_4 - a_3 = 2^4 - 2^3 = 16 - 8 = 8, и так далее.

Мы видим, что разности D_1, D_2, D_3, D_4 и так далее образуют последовательность 1, 2, 4, 8, ... , которая является удвоенной последовательностью степеней числа 2.

Теперь давайте рассмотрим разности между степенями двойки и удвоенной последовательностью: E_n = a_n - 2^n.

E_0 = a_0 - 2^0 = 1 - 1 = 0, E_1 = a_1 - 2^1 = 2 - 2 = 0, E_2 = a_2 - 2^2 = 4 - 4 = 0, E_3 = a_3 - 2^3 = 8 - 8 = 0, и так далее.

Мы видим, что разности E_0, E_1, E_2, E_3 и так далее равны нулю, так как они образуют разности между степенями двойки и удвоенной последовательностью степеней двойки.

Теперь мы можем записать разность между произвольными степенями двойки:

a_m - a_n = (a_m - 2^m) + (2^m - 2^n) + (2^n - a_n) = E_m + D_{m+1} + E_n.

Мы знаем, что D_{m+1} - разность удвоенной последовательности степеней двойки, и она делится на 2013.

Таким образом, разность между произвольными степенями двойки разбивается на три компоненты: E_m, D_{m+1} и E_n. Первая и третья компоненты равны нулю, поэтому разность между степенями двойки делится на 2013.

Таким образом, мы доказали, что среди степеней двойки существуют две, разность между которыми делится на 2013.