Question

Шестизначное натуральное число называется хорошим, если любая цифра, кроме первого и последнего, в его десятичной записи равна сумме соседних цифр в десятичной записи этого числа по mod 5. Найдите количество хороших шестизначных чисел. (Определение mod 5: равны по тod 5 означает, что они дают одинаковые остатки при делении на 5)​

Answer 1

Для начала рассмотрим только последовательности из шести цифр, каждая из которых принадлежит множеству $\{0;\ 1;\ 2;\ 3;\ 4\}$.

Заметим, что по первым двум цифрам мы можем автоматически получить последовательность удовлетворяющую условию.

Например, первые две цифры 10:

Исходное число $\mathrm{\overline{10 cde f }}$.

$0=1+c\pmod5$

$\Rightarrow c=0-1=-1=4\pmod5$

Получим число $\mathrm{\overline{104 de f }}$.

$4=0+d\pmod5$

$\Rightarrow d=4-0=4\pmod5$

Получим число $\mathrm{\overline{1044 ef }}$.

$4=4+e\pmod5$

$\Rightarrow e=4-4=0\pmod5$

Получим число $\mathrm{\overline{10440 f }}$.

$0=4+f\pmod5$

$\Rightarrow f=0-4=-4=1\pmod5$

Получим число $104401$.

Таким образом, имеются следующие последовательности, начинающиеся с цифр:

$\left(\begin{array}{c}00\\ 01\\ 02\\ 03\\ 04\end{array}\right)\left(\begin{array}{cccc}10&20&30&40\\ 11&21&31&41\\ 12&22&32&42\\ 13&23&33&43\\ 14&24&34&44\end{array}\right)$

Рассмотрим последовательности, начинающиеся не с нуля, которые уже являются шестизначными числами, названными по условию хорошими. Они указаны в правой части таблицы, и их 20 штук.

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

Рассмотрим, сколькими способами мы можем изменять таким образом цифры в одном числе. Каждую из 6 цифр мы можем либо менять, либо не менять (2 варианта). Таким образом, общее количество возможных новых чисел для одного числа равно $2^6=64$.

Общее количество хороших чисел для последовательностей из правой части таблицы:

$20\cdot64=1280$

Рассмотрим последовательности, начинающиеся с нуля. Они указаны в левой части таблицы, и их 5 штук.

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

В остальном мы можем действовать тем же способом, который рассмотрели ранее. Каждую из остальных 5 цифр мы можем увеличивать или не увеличивать на 5. Таким образом, общее количество возможных новых чисел для одного числа равно $2^5=32$.

Общее количество хороших чисел для последовательностей из левой части таблицы:

$5\cdot32=160$

Итоговое количество хороших чисел:

$1280+160=1440$

Ответ: 1440