Вопросы о делимости

Может ли хоть одно счастливое число делиться на 21? Как вы поняли - это уже более сложный уровень. Если бы речь шла всего об одном числе, то мы бы легко проверили делимость на 21 просто выполнив его деление на 21 в столбик, а наличие или отсутствие остатка и стало бы тем самым индикатором делимости. Но здесь речь идет о 386 счастливых числах. Неужели придется опять их все проверять?

Их можно проверить все, но сама проверка может быть ускорена с помощью алгебры и парочки "грязных трюков".


Алгебраическая теория чисел

Звучит немного страшно. Но на самом деле суть заключается в том, что нам нужно расширить понятие числа, с помощью букв и буквенных выражений. Такое расширение снимает необходимость в переборе всех 386 чисел, а позволяет с помощью нескольких примеров показать, что среди них либо есть числа, которые делятся на 7 либо нет делятся.

Давайте вспомним, наши билеты обозначаются как \(\overline{abcd}\), удовлетворяют следующим равенствам: \(a+b=c+d;\;\;a \neq b \neq d \neq c;\;\; 0\leq a,b,c,d\leq9\) и могут быть записаны как:

$$N = \overline{abcd} = a\cdot 1000 \;+\;b\cdot100\;+\;c\cdot10\;+\;d$$

Что бы понять суть алгебраического расширения чисел, давайте зададимся тривиальным вопросом - "Какие счастливые числа делятся на 2 ???" Естественно, делятся только те, что оканчиваются четной цифрой. Но как это продемонстрировать с помощью алгебры? На самом деле, все довольно просто. Вот развернутая запись нашего счастливого числа:

$$1000a+100b+10c+d$$

Очевидно, что если какое-то счастливое число делится на 2, то результат деления должен быть целым числом. Обозначим результат деления буквой \(k\):

$$\frac{1000a+100b+10c+d}{2}=k$$

Теперь мы можем заметить, что \(1000 = 2\cdot500\), \(100 = 2\cdot50\), \(10 = 2\cdot5\), а значит можем переписать выражение вот так:

$$\frac{2\cdot500a+2\cdot50b+2\cdot5c+d}{2}=k$$

Выносим все двойки за скобку:

$$\frac{2(500a+50b+5c)+d}{2}=k$$

Дробь можем представить суммой дробей:

$$\frac{2(500a+50b+5c)}{2}+\frac{d}{2}=k$$

А после сокращения, мы наконец получим вот такой результат:

$$(500a+50b+5c)+\frac{d}{2}=k$$

Полученное выражение, еще не является доказательством того, что существуют счастливые числа, которые могут делиться на два. Но это выражение, позволяет нам делать обоснованные умозаключения, которые и станут аргументированным доказательством.

Например, мы можем сразу заметить, что \(k\) будет целым числом, только в том случае если \(d\) делится на 2. Учитывая, что \(d\) это последняя цифра в числе, которая может принимать значения 0, 2, 4, 6, 8, то мы можем с полной уверенностью утверждать, что счастливые числа делящиеся на 2 существуют, например число \(1542\), которое при делении на 2 даст \(k = 771\).

Более того, если выразить \(d\) и подставить все цифры числа \(1542\) и \(k\) в полученное выражение, мы получим верное равенство:

$$d = 2(k-(500a+50b+5c)) = \\ =2(771-(500\cdot1+50\cdot5+5\cdot4)) = 2(771-(500+250+20))=\\ =2(771-770)=2$$

Следуя, такому принципу построения доказательств, мы можем делать выводы о делимости чисел (и не только счастливых), вообще не выполняя никакого перебора этих самых чисел.


Делимость на 5

Вопрос о делимости счастливых чисел на 5, так же прост как и вопрос о делимости на 2. Мы прекрасно знаем, что число делится на 5, только в том случае, если его последняя цифра либо 0 либо 5. Давайте, снова докажем это с помощью алгебры.

И так, вот исходная запись нашего числа:

$$1000a+100b+10c+d$$

Представляем числа 1000, 100 и 10 в виде произведений \(5\cdot200\), \(5\cdot20\) и \(5\cdot2\) соответственно, тогда:

$$1000a+100b+10c+d = 5\cdot200a+5\cdot20b+5\cdot2c+d = \\ =5(200a+20b+2c)+d$$

При делении на 5 выражениие \(5(200a+20b+2c)+d\) должно давать какое-то целое число \(k\):

$$\frac{5(200a+20b+2c)}{5}+\frac{d}{5}=k$$

И опять становится совершенно очевидно, что это возможно, только если \(d\) будет либо 0 либо 5. А учитывая, что это допустимые значения для цифры (т.е. \(0\leq d\leq 9\)), то мы снова можем утверждать, что счастливые числа, делящиеся на 5 могут существовать, например: \(8145\).


Делимость на 4

Чтож, признак делимости на 4 нам тоже знаком: число должно оканчиваться либо двумя нулями, либо две его последние цифры должны образовывать число, которое делится на 4. Но если, в предыдущих двух примерах речь шла только о последней цифре, то здесь она идет уже о двух цифрах. Давайте посмотрим, что у нас может получится, если мы будем пользоваться уже знакомой концепцией подобных доказательств.

Вот наше число:

$$1000a+100b+10c+d$$

Число 1000 делится на 4, значит мы можем представить его как \(4\cdot250\), число 100 можем выразить как \(4\cdot25\), но число 10 при делении на 4 дает остаток 2. В этом случае мы воспользоваться представлением числа по модулю. Что это означает? Обозначим буквой \(b\) некоторое число, которое будем называть модулем, буквой \(q\) будем обозначать неполное частное, буквой \(r\) будем обозначать остаток от деления. Тогда любое число \(a\) можно представить по любому произвольному модулю следующим образом:

$$a = bq+r$$

Например, число 25 по модулю 3 будет выглядеть вот так: \(25 = 3 \cdot 8 + 1\). А число 10 по модулю 4 так: \(10 = 4 \cdot 2 + 2\). Если использовать такую запись применительно к нашему выражению то мы можем записать следующее:

$$1000a+100b+10c+d = 4\cdot250a+4\cdot25b+(4\cdot2+2)c+d=\\ = 4\cdot250a+4\cdot25b+4\cdot2c+2c+d=\\ =4(250a+25b+2c)+2c+d$$

Самое любопытное, что полученный результат – это алгебраическая форма записи числа по модулю 4. В самом деле, сравните:

$$a = bq+r\\ \overline{abcd}=4(250a+25b+2c)+2c+d$$

Выражение \((250a+25b+2c)\) можно считать неполным частным, а \(2c+d\) — остатком. Именно поэтому выражение \(4(250a+25b+2c)\) всегда делится на 4, а выражение \(2c+d\) может, как делиться так и не делиться. Можно сказать, что все наши действия в подобных доказательствах сводятся именно к таким выражениям, которые позволяют проверять выполнение некоторых гипотез. А самих гипотез, по стути, всего три:

  • Гипотеза на 100% верна?
  • При каких-то условиях гипотеза верна, а при каких-то неверна?
  • Гипотеза на 100% неверна?

Можно привести несколько примеров:

  • Гипотеза о том, что выражение \(x(x+1)\) делится на 2, верна при любых \(x\);
  • Гипотеза о том, что выражение \(2c+d\) делится на 4 верна при \(c=1\) и \(d=2\) и неверна при \(c=2\) и \(d=1\).
  • Гипотеза о том, что выражение \(x(x+1)+1\) делится на 2, неверна при любых \(x\).

Если вернуться к нашему вопросу о делимости счастливого числа на 4, то мы на него уже ответили: при \(c=1\) и \(d=2\) оно может делиться на 4. Примером такого числа может быть \(3012\). Однако, есть счастливые числа, которые могут и не делиться на 4, например \(3021\).

Теперь давайте представим, что нам необходимо найти все счастливые числа, которые делятся на 4. Вряд ли что-то такое может произойти на экзамене. Но зато мы усовершенствуем наши навыки. Давайте еще раз взглянем на ранее полученное выражение:

$$4(250a+25b+2c)+2c+d$$

При делении на 4 оно должно давать некоторое целое число, которое мы обозначим буквой \(k\):

$$\frac{4(250a+25b+2c)+2c+d}{4}=k \;\; \Rightarrow \\ \Rightarrow \;\; \frac{4(250a+25b+2c)}{4} + \frac{2c+d}{4} = k \;\; \Rightarrow \\ \Rightarrow \;\; (250a+25b+2c) + \frac{2c+d}{4} = k$$

Выражение \(250a+25b+2c\) будет целым всегда, давайте обозначим его буквой \(m\). А вот выражение \((2c+d)/4\), которое мы обозначим буквой \(l\) может быть как целым так и нет. И теперь, что бы получить все счастливые числа, делящиеся на 4, нам нужно поработать с выражением:

$$\frac{2c+d}{4} = l$$

Теперь немного преобразуем данное выражение:

$$d = 4l-2c = 2(2l-c)$$

И можем сразу отметить что последняя цифра может быть только четной. Теперь вспоминаем, что переменные \(d\) и \(c\) обозначают цифры, а значит не могут быть меньше 0 и больше 9. Предположим, что \(d = 0\), тогда:

$$2(2l-c) = 0 \;\; \Rightarrow \;\; c = 2l$$

Значит, при \(d = 0\), \(c\) может принимать только четные значения. Но здесь следует быть на чеку, так как при \(d = 0\) и \(c = 2\) мы получаем число которое будет оканчиваться цифрой 20, но в этом случае мы не сможем подобрать подходящие \(a\) и \(b\), что бы число было счастливым.

Если \(d = 2\), то

$$2(2l-c) = 2 \;\; \Rightarrow \;\; c = 2l-1$$

Видим, что при \(d = 2\), \(c\) может принимать только нечетные значения.

Таким образом, мы можем получить все счастливые числа делящиеся на 4. Ну и конечно, лучше всего весь процесс выполнять в форме таблицы, что-бы ничего не пропустить и легко ориентироваться.


Делимость на 3

Признак делимости на 3 интересен тем, что в нем участвуют все цифры числа. А именно: число делится на 3 если сумма его цифр делится на 3. Сможем ли мы доказать, что счастливые числа тоже могут делиться на 3?

$$1000a+100b+10c+d = 3\cdot333a+a+3\cdot33b+b+3\cdot3c+d = \\ =3(333a+33b+3c)+a+b+c+d$$

То что \(3(333a+33b+3c)\) делится на 3 это очевидно. Но вот то, что в "остатке" у нас получилось выражение \(a+b+c+d\) говорит о том, что признак делимости на 3 распространяется и на наши счастливые билеты, с одним лишь ограничением – счастливые числа это те, в которых \(a+b=c+d\).

В принципе, мы можем остановиться на этом. Потому что привести пример счастливого числа, которое делится на 3 теперь очень просто, например \(5142\).

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