НЕделимость на 11

Ок, вы можете сказать, что вопрос о делимости, в принципе, победимый, достаточно найти всего одно подтверждение и все. Но что бы доказать, то что ни один билет не делится на какое-то число, нам нужно проверить все варианты. Это и правда проблематично. Как же быть??? Но ответ тот же - алгебраическая теория чисел. Просто на этот раз мы никаких значений подставлять не будем, а будем стараться вывести такие выражения, которые должны содержать противоречия, а эти противоречия в свою очередь и будут индикатором неделимости.

Почему мы выбрали именно 11? Если сделать нехитрый скрипт, то окажется что чисел, на которые не делится ни одино счастливое число не так уж много. Проверьте, 11 – является наименьшим из них:

In[]

r = [int(i)%11 for i in N]

pprint.pprint(r, compact = True)    #  используем для компактного вывода
print('\n0 in r =', 0 in r)

Out[]

[4, 2, 6, 2, 8, 6, 4, 2, 10, 8, 4, 2, 1, 10, 8, 6, 4, 2, 3, 1, 10, 6, 4, 2, 5,
 3, 1, 10, 8, 6, 4, 2, 4, 9, 6, 9, 8, 4, 2, 9, 10, 6, 2, 9, 1, 8, 6, 4, 2, 9, 3,
 10, 8, 4, 2, 9, 5, 1, 10, 8, 6, 4, 2, 9, 3, 1, 10, 6, 4, 2, 2, 7, 6, 4, 9, 7,
 8, 6, 9, 7, 10, 8, 4, 2, 9, 7, 1, 10, 6, 2, 9, 7, 3, 1, 8, 6, 4, 2, 9, 7, 3,
 10, 8, 4, 2, 9, 1, 10, 8, 6, 4, 2, 9, 7, 2, 5, 4, 2, 7, 5, 8, 6, 4, 9, 7, 5,
 10, 8, 6, 9, 7, 5, 1, 10, 8, 4, 2, 9, 7, 5, 1, 10, 6, 2, 9, 7, 1, 8, 6, 4, 2,
 9, 10, 8, 4, 2, 9, 5, 2, 9, 7, 3, 4, 2, 5, 3, 6, 4, 2, 7, 5, 3, 10, 8, 6, 4, 9,
 7, 5, 3, 10, 8, 6, 9, 7, 5, 10, 8, 4, 2, 9, 7, 10, 6, 2, 9, 8, 6, 4, 2, 9, 7,
 5, 3, 2, 9, 5, 1, 4, 2, 9, 7, 3, 1, 6, 4, 2, 5, 3, 1, 8, 6, 4, 2, 7, 5, 3, 1,
 8, 6, 4, 9, 7, 5, 8, 6, 9, 7, 8, 4, 2, 9, 6, 2, 9, 7, 3, 1, 2, 9, 7, 5, 3, 10,
 4, 2, 9, 5, 1, 10, 6, 4, 2, 9, 7, 3, 1, 10, 6, 4, 2, 5, 3, 1, 6, 4, 2, 7, 5, 3,
 6, 4, 9, 7, 6, 9, 4, 2, 9, 7, 5, 3, 1, 10, 2, 9, 7, 3, 1, 8, 4, 2, 9, 7, 5, 3,
 10, 8, 4, 2, 9, 5, 1, 10, 4, 2, 9, 7, 3, 1, 4, 2, 5, 3, 4, 2, 7, 5, 4, 9, 9, 7,
 5, 1, 10, 8, 2, 9, 7, 5, 3, 1, 10, 6, 2, 9, 7, 3, 1, 8, 2, 9, 7, 5, 3, 10, 2,
 9, 5, 1, 2, 9, 7, 3, 2, 5, 2, 7, 9, 7, 5, 3, 1, 10, 8, 6, 9, 7, 5, 1, 10, 8, 9,
 7, 5, 3, 1, 10, 9, 7, 3, 1, 9, 7, 5, 3, 9, 5, 9, 7]

0 in r = False

Давайте попробуем это доказать. Посмотрим на частные и остатки от деления на 11:

In[]

print(divmod(1000, 11))
print(divmod(100, 11))

Out[]

(90, 10)
(9, 1)

Теперь, выполним уже знакомые нам преобразования:

$$1000a+100b+10c+d = 11\cdot90a+10a+11\cdot9b+b+10c+d=\\ =11(90a+9b)+\left \{ 10a+b+10c+d \right \}$$

Мы уже знаем что \(a=c+d-b\) и что придется работать над выражением:

$$\frac{10a+b+10c+d}{11}=k$$

Выполним подстановку и выполним все преобразования:

$$10c+10d-10b+b+10c+d=11k\;\; \Rightarrow \\ \Rightarrow \;\; 20c+11d-9b = 11k \;\; \Rightarrow \\ \Rightarrow \;\;22c-2c+11d-11b+2b = 11k \;\; \Rightarrow \\ \Rightarrow \;\;2b-2c = 11k-22c-11d+11b \;\; \Rightarrow \\ \Rightarrow \;\;2b-2c = 11(k-2c-d+b); \;\; l=k-2c-d+b \;\; \Rightarrow \\ \Rightarrow \;\;2b = 11l+2c \;\; \Rightarrow \\ \Rightarrow \;\;b = \frac{11l+2c}{2}$$

Учитывая то, что мы имеем дело с цифрами мы можем заметить, что \(l\) может быть равно только 0. Иначе \(b\) станет больеше 9. Но если \(l=0\), то в этом случае \(c\) может быть абсолютно любой цифрой и доказать неделимость вряд ли получится. Может быть \(l\) не может быть равна 0? Давайте проверим: \(l = k-2c-d+b = 0 \;\; \Rightarrow \;\; k+b=2c+d \), но легко показать, что это равенство выполняется при \(b=1\), \(c=2\), \(d=3\), \(k=6\). В общем, ничего доказать у нас так и не получилось.

Возможно, мы что-то не так выразили. Может следует всегда выражать последнюю цифру. Может это и есть что-то вроде правила, которое будет всегда 100% работать. Давайте попробуем выразить \(d\):

$$11d=11k+9b-20c \;\; \Rightarrow \\ \Rightarrow \;\; 11d = 11k+11b-2b-22c+2c \;\; \Rightarrow \\ \Rightarrow \;\; 11d = 11(k+b-2c)-2b-2c; \;\; l=k+b-2c \;\; \Rightarrow \\ \Rightarrow \;\; 11d = 11l-2b+2c \;\; \Rightarrow \\ \Rightarrow \;\; d = \frac{2(c-b)}{11}$$

А вот теперь появилось то за что можно зацепиться. Дробь \(2(c-b)/11\) тоже далжна давать целые значения. А это возможно только если \(c-b=0\) или \(c-b=11\). В первом случае \(c=b\), но это протеворечит условиям "счастливости". В втором случае \(c-b=11 \;\; \Rightarrow \;\; c = 11+b\), но \(c\) – это цифра, т.е. не может быть больше 9.

А раз дробь \(2(c-b)/11\) не дает целых допустимых значений, то, следовательно, мы не сможем найти ни одного билета, который делился бы на 11. Вот и все.