Суммы цифр

[sergey1]

У двух чисел одинаковое число цифр, причем разность между суммами цифр, стоящих на четных и нечетных позициях первого числа равна соответствующей разности другого числа.
Верно ли, что с помощью операций
а) добавление к двум соседним цифрам по 1, если среди них нет 9
б) вычитание из двух соседних цифр по 1, если среди них нет 0
всегда можно из первого числа получить второе?

[Руст]

Да. Эти числа к тому же делятся на 11.

[нг]

Руст писал(а):

Эти числа к тому же делятся на 11.

Например, 13 и 24.

[Руст]

Я извиняюсь, имеют одинаковый остаток при делении на 11 (но не всякая пара чисел, имеющих одинаковый остаток при делении на 11 образуют такую пару).

[Антипка]

Из факта принадлежности чисел одному классу вычетов по модулю 11 еще не следует возможность перевести одно число в другое указанным способом. Грубо говоря, для всякого количества цифр и для всякой суммо-разности цифр, определенной в условии, надо еще доказать связность порождаемого графа (вершины графа - числа, две вершины соединены ребром тогда итолько тогда, когда из одного числа можно получить другое указанной в условии _одной_ элементарной опреацией, определенной в условии).

Эта задача на самом деле представляет собой пример, как можно "запутать" тривиальное и очевидное утверждение. Чтобы решить задачу, достаточно перейти к эквивалентной задаче: даны два числа с одинаковыми количеством и суммой цифр. За одну операцию можно "перекинуть единицу" из любой цифры в соседнюю (первая из них при этом, очевидно, должна быть не 0, а вторая - не 9). Если угодно, можно сформулировать задачу в терминах "кучек камней". Разрешимость этой задачи практически очевидна, если разбить ее на две идентичные подзадачи: из каждого из заданных чисел получить таким способом число вида 0..0N9..9 (0<=N<=9).

Ну а эквивалентность двух проблем также устанавливается элементарно, из исходной задачи можно перейти к модифицированной путем замены всех цифр на четных местах (или на нечетных местах, это без разницы) на комплементарные (i --> (9-i)).

[нг]

Антипка писал(а):

Разрешимость этой задачи практически очевидна, если разбить ее на две идентичные подзадачи: из каждого из заданных чисел получить таким способом число вида 0..0N9..9 (0<=N<=9).

Уж не эквивалентно ли это равенству суммы цифр?!

P.S. Антипка _text_ $\equiv$ text, но форум этого сам не сделает.

[i]text[/i]

[Руст]

[quote="Антипка"]0..0N9..9 (0<=N<=9).
quote]
Любое число приводится к одному из стандартных видов $k0909...09, \ k09090..90$, где k цифра. Здесь количество повторений 09 или 90 равен $[\frac{|S_e-S_o|}{9}]$, k остаток от деления.

[Антипка]

Руст писал(а):

Любое число приводится к одному из стандартных видов $k0909...09, \ k09090..90$, где k цифра. Здесь количество повторений 09 или 90 равен $[\frac{|S_e-S_o|}{9}]$, k остаток от деления.

Абсолютно согласен. Но с моей точки зрения, из двух эквивалентных задач - исходной и эквивалентной ей, намного проще решить эквивалентную задачу. Она гораздо нагляднее. Она практически устная. А затем, используя эту эквивалентность, можно сформулировать решение в терминах исходной задачи.