Задача №2.
Найти ли такие два идущих подряд натуральных числа, что если их «расписать» на цифры, то все цифры от 0 до 9 окажутся поровну?
Решение:
Пусть у нас есть два идущих подряд натуральных числа. Обозначим их как \(N\) и \(N+1\).
Нам нужно «расписать» эти числа на цифры. Это означает, что мы должны посчитать, сколько раз каждая цифра (от 0 до 9) встречается в записи этих двух чисел.
Условие задачи гласит, что все цифры от 0 до 9 должны оказаться поровну. Это значит, что каждая цифра должна встретиться одинаковое количество раз.
Рассмотрим количество цифр в записи чисел.
Если числа \(N\) и \(N+1\) имеют разное количество цифр, то это возможно только в том случае, если \(N\) заканчивается на 9, а \(N+1\) начинается с 1 и имеет на одну цифру больше. Например, 9 и 10, 99 и 100, 999 и 1000 и так далее.
Случай 1: Числа \(N\) и \(N+1\) имеют одинаковое количество цифр.
Пусть \(N\) и \(N+1\) — это числа, состоящие из \(k\) цифр. Тогда общее количество цифр, которые мы будем рассматривать, равно \(2k\).
Если все цифры от 0 до 9 встречаются поровну, то каждая цифра должна встретиться \(\frac{2k}{10}\) раз. Для того чтобы это было возможно, \(\frac{2k}{10}\) должно быть целым числом. То есть \(2k\) должно делиться на 10, или \(k\) должно делиться на 5.
Рассмотрим примеры:
Если \(k=5\), то каждое число состоит из 5 цифр. Общее количество цифр \(2 \times 5 = 10\). Каждая цифра должна встретиться \(\frac{10}{10} = 1\) раз.
Это означает, что в записи чисел \(N\) и \(N+1\) должны присутствовать все цифры от 0 до 9 ровно по одному разу. Например, если \(N = 12345\), а \(N+1 = 12346\). Цифры в \(N\): 1, 2, 3, 4, 5. Цифры в \(N+1\): 1, 2, 3, 4, 6. Общий набор цифр: 1, 1, 2, 2, 3, 3, 4, 4, 5, 6. Здесь цифры не встречаются поровну (например, 0, 7, 8, 9 отсутствуют, а 1, 2, 3, 4 встречаются по два раза).
Когда мы переходим от \(N\) к \(N+1\), большинство цифр остаются неизменными, кроме тех, что меняются при увеличении на 1. Например, если \(N = \dots d_1 d_0\) и \(N+1 = \dots d_1 (d_0+1)\), то цифра \(d_0\) меняется на \(d_0+1\). Если \(N = \dots d_2 9\) и \(N+1 = \dots (d_2+1) 0\), то цифра 9 меняется на 0, а \(d_2\) меняется на \(d_2+1\). Если \(N = \dots d_k 9 \dots 9\) (где \(m\) девяток) и \(N+1 = \dots (d_k+1) 0 \dots 0\), то \(m\) девяток меняются на \(m\) нулей, а \(d_k\) меняется на \(d_k+1\).
В любом случае, при переходе от \(N\) к \(N+1\), сумма цифр меняется на 1 (если нет переносов) или на \(1 - 9m\) (если \(m\) девяток превращаются в нули, а предыдущая цифра увеличивается на 1). Например, для 9 и 10: цифры в 9 - {9}. Цифры в 10 - {1, 0}. Для 19 и 20: цифры в 19 - {1, 9}. Цифры в 20 - {2, 0}. Для 29 и 30: цифры в 29 - {2, 9}. Цифры в 30 - {3, 0}. Для 99 и 100: цифры в 99 - {9, 9}. Цифры в 100 - {1, 0, 0}.
Если все цифры от 0 до 9 встречаются поровну, то сумма всех этих цифр должна быть одинаковой. Сумма цифр от 0 до 9: \(0+1+2+3+4+5+6+7+8+9 = 45\). Если каждая цифра встречается \(x\) раз, то общая сумма всех цифр будет \(45x\).
Сумма цифр числа \(N\) обозначается как \(S(N)\). Сумма цифр числа \(N+1\) обозначается как \(S(N+1)\). Общая сумма всех цифр в записи \(N\) и \(N+1\) будет \(S(N) + S(N+1)\).
Мы знаем, что \(S(N+1)\) отличается от \(S(N)\) следующим образом: Если \(N\) не заканчивается на 9, то \(S(N+1) = S(N) + 1\). Если \(N\) заканчивается на \(m\) девяток (например, \(N = A \cdot 10^m + (10^m - 1)\)), то \(N+1 = (A+1) \cdot 10^m\). В этом случае \(S(N) = S(A) + 9m\). А \(S(N+1) = S(A+1)\). Мы знаем, что \(S(A+1) = S(A) + 1 - 9k'\), где \(k'\) - количество девяток, на которые заканчивается \(A\). Тогда \(S(N+1) = S(A) + 1 - 9k'\). Разница \(S(N+1) - S(N) = (S(A) + 1 - 9k') - (S(A) + 9m) = 1 - 9k' - 9m\). Это означает, что \(S(N+1)\) и \(S(N)\) имеют разную четность, если \(1-9k'-9m\) нечетно, что всегда так, поскольку \(9k'\) и \(9m\) всегда нечетны, если \(k'\) и \(m\) нечетны, и четны, если \(k'\) и \(m\) четны. \(1 - 9(k'+m)\). Если \(k'+m\) четно, то \(1 - \text{четное} = \text{нечетное}\). Если \(k'+m\) нечетно, то \(1 - \text{нечетное} = \text{четное}\). Таким образом, \(S(N)\) и \(S(N+1)\) всегда имеют разную четность, если \(k'+m\) нечетно, и одинаковую четность, если \(k'+m\) четно.
Однако, более простое свойство: \(S(N+1) \equiv S(N) + 1 \pmod 9\). Это означает, что \(S(N+1)\) и \(S(N)\) всегда имеют разный остаток при делении на 9, если \(S(N+1) \ne S(N)\). Или, что \(S(N+1) - S(N) \equiv 1 \pmod 9\).
Сумма всех цифр в записи \(N\) и \(N+1\) равна \(S(N) + S(N+1)\). Если все цифры от 0 до 9 встречаются поровну, то каждая цифра встречается \(x\) раз. Тогда общая сумма всех цифр будет \(x \cdot (0+1+2+3+4+5+6+7+8+9) = x \cdot 45\). Это число \(45x\) всегда делится на 9.
Значит, \(S(N) + S(N+1)\) должно делиться на 9.
Мы знаем, что \(S(N+1) \equiv S(N) + 1 \pmod 9\). Тогда \(S(N) + S(N+1) \equiv S(N) + (S(N) + 1) \pmod 9\). \(S(N) + S(N+1) \equiv 2S(N) + 1 \pmod 9\).
Для того чтобы \(S(N) + S(N+1)\) делилось на 9, должно быть \(2S(N) + 1 \equiv 0 \pmod 9\).
Решим это сравнение:
\(2S(N) \equiv -1 \pmod 9\)
\(2S(N) \equiv 8 \pmod 9\)
Разделим обе части на 2 (это возможно, так как 2 и 9 взаимно просты):
\(S(N) \equiv 4 \pmod 9\).
Это означает, что сумма цифр числа \(N\) должна давать остаток 4 при делении на 9.
Теперь вернемся к условию, что все цифры встречаются поровну. Пусть \(k\) - количество цифр в числе \(N\). Пусть \(k'\) - количество цифр в числе \(N+1\).
Общее количество цифр, которые мы рассматриваем, равно \(k+k'\).
Если все 10 цифр встречаются поровну, то каждая цифра встречается \(\frac{k+k'}{10}\) раз. Это число должно быть целым. Значит, \(k+k'\) должно делиться на 10.
Случай 1: \(k=k'\) (числа имеют одинаковое количество цифр).
Тогда \(2k\) должно делиться на 10, то есть \(k\) должно делиться на 5.
Если \(k=5\), то каждое число состоит из 5 цифр. Общее количество цифр \(2 \times 5 = 10\). Каждая цифра должна встретиться \(\frac{10}{10} = 1\) раз.
Это означает, что в записи чисел \(N\) и \(N+1\) вместе должны быть все цифры от 0 до 9 ровно по одному разу.
При этом \(S(N) \equiv 4 \pmod 9\).
Если \(N\) и \(N+1\) имеют одинаковое количество цифр, то \(N\) не может заканчиваться на 9. Значит, \(S(N+1) = S(N) + 1\).
Тогда \(S(N) + S(N+1) = S(N) + (S(N)+1) = 2S(N) + 1\).
Сумма всех цифр от 0 до 9, каждая по одному разу, равна 45. Значит, \(2S(N) + 1 = 45\).
\(2S(N) = 44\)
\(S(N) = 22\).
Проверим условие \(S(N) \equiv 4 \pmod 9\): \(22 \div 9 = 2\) с остатком \(4\). \(22 \equiv 4 \pmod 9\). Это условие выполняется.
Итак, нам нужно найти 5-значное число \(N\) такое, что \(S(N)=22\), и при этом в записи \(N\) и \(N+1\) вместе все цифры от 0 до 9 встречаются ровно по одному разу.
Пусть \(N = d_4 d_3 d_2 d_1 d_0\). Тогда \(N+1 = d_4 d_3 d_2 d_1 (d_0+1)\) (поскольку \(N\) не заканчивается на 9).
Цифры в \(N\): \(d_4, d_3, d_2, d_1, d_0\). Цифры в \(N+1\): \(d_4, d_3, d_2, d_1, d_0+1\).
Общий набор цифр: \(d_4, d_3, d_2, d_1, d_0, d_4, d_3, d_2, d_1, d_0+1\).
Мы видим, что цифры \(d_4, d_3, d_2, d_1\) встречаются по два раза. А цифры \(d_0\) и \(d_0+1\) встречаются по одному разу.
Но по условию, каждая цифра от 0 до 9 должна встретиться ровно один раз. Это противоречие. Если \(d_4, d_3, d_2, d_1\) встречаются по два раза, то они не могут встречаться по одному разу. Значит, этот случай (когда \(N\) и \(N+1\) имеют одинаковое количество цифр) невозможен.
Случай 2: Числа \(N\) и \(N+1\) имеют разное количество цифр.
Это происходит, когда \(N\) заканчивается на 9, а \(N+1\) имеет на одну цифру больше. Например, \(N=9\), \(N+1=10\). Цифры в \(N\): {9}. Цифры в \(N+1\): {1, 0}. Общий набор цифр: {0, 1, 9}. Здесь 0, 1, 9 встречаются по одному разу, а остальные цифры (2, 3, 4, 5, 6, 7, 8) отсутствуют. Не подходит.
Например, \(N=99\), \(N+1=100\). Цифры в \(N\): {9, 9}. Цифры в \(N+1\): {1, 0, 0}. Общий набор цифр: {0, 0, 1, 9, 9}. Здесь 0 и 9 встречаются по два раза, 1 по одному разу, остальные отсутствуют. Не подходит.
Пусть \(N\) имеет \(k\) цифр, а \(N+1\) имеет \(k+1\) цифру. Тогда \(N\) должно быть вида \(10^k - 1\), то есть состоять из \(k\) девяток. Например, \(N = 99\dots9\) (k девяток). Тогда \(N+1 = 10^k\), то есть 1 и \(k\) нулей.
Общее количество цифр, которые мы рассматриваем, равно \(k + (k+1) = 2k+1\).
Если все 10 цифр встречаются поровну, то каждая цифра встречается \(\frac{2k+1}{10}\) раз. Но \(2k+1\) всегда нечетно, а 10 четно. Значит, \(\frac{2k+1}{10}\) никогда не будет целым числом. Это означает, что в этом случае (когда \(N\) состоит из девяток, а \(N+1\) - это 1 и нули) невозможно, чтобы все цифры встречались поровну.
Рассмотрим более общий случай, когда \(N\) заканчивается на \(m\) девяток, но не состоит только из девяток. Пусть \(N = A \cdot 10^m + (10^m - 1)\), где \(A\) - число, не заканчивающееся на 9. Тогда \(N+1 = (A+1) \cdot 10^m\).
Пример: \(N=19\), \(N+1=20\). Цифры в \(N\): {1, 9}. Цифры в \(N+1\): {2, 0}. Общий набор цифр: {0, 1, 2, 9}. Здесь 0, 1, 2, 9 встречаются по одному разу, а остальные цифры (3, 4, 5, 6, 7,