Question

Докажите что существует число из одних единиц и нулей которое делится на 2018

Answer 1

Это задача на принцип Дирихле (про кролики и клетки - кроликов больше, чем клеток)

Возьмем 2019 чисел-кроликов вида 1, 11, 111, 1111, ...., 111...(2019 единиц) и распределим их по 2018 клеткам с номерами 0, 1, 2, .... , 2017 (номер клетки совпадает с остатком от деления этого числа на 2018.

По принципу Дирихле найдутся два числа, имеющие одинаковые остатки от деления на 2018 (найдется клетка, в которой два кролика, т.к. кроликов больше, чем клеток).

Разность этих чисел не имеет остатка от деления на 2018 (делится без остатка) и содержит только 1 и 0 (нули получаются при вычитании единиц в одинаковых разрядах этих чисел).

например 111...(n единиц) и 111(k единиц) и n>k

разность этих чисел 111...(n-k единиц)000...(k нулей)

Answer 2

Для решения этой задачи воспользуемся принципом Дирихле.

Рассмотрим последовательность чисел 1, 11, 111, 1111, ... Все эти числа записаны в десятичной системе счисления и содержат только цифры 0 и 1.

Рассмотрим остатки от деления этих чисел на 2018. Поскольку чисел 1 и 2018 взаимно просты, то по принципу Дирихле найдутся два числа из этой последовательности, скажем, a и b, такие, что a > b и остатки от деления a и b на 2018 совпадают. То есть a - b делится на 2018.

Тогда число, состоящее из единиц и нулей и имеющее разность a - b нулей и b единиц в начале и конце соответственно, будет делиться на 2018. Действительно, это число можно записать в виде b + k(a - b), где k - некоторое натуральное число, и остаток от деления этого числа на 2018 будет совпадать с остатком от деления числа a на 2018.

Таким образом, мы доказали, что существует число из одних единиц и нулей, которое делится на 2018.