2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Суммы цифр
Сообщение07.10.2007, 09:42 


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

 Профиль  
                  
 
 
Сообщение07.10.2007, 11:07 
Заслуженный участник


09/02/06
4401
Москва
Да. Эти числа к тому же делятся на 11.

 Профиль  
                  
 
 
Сообщение08.10.2007, 05:02 
Экс-модератор
Аватара пользователя


30/11/06
1265
Руст писал(а):
Эти числа к тому же делятся на 11.

Например, 13 и 24. 8-)

 Профиль  
                  
 
 
Сообщение08.10.2007, 07:11 
Заслуженный участник


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

 Профиль  
                  
 
 Но решения так и не дано
Сообщение12.10.2007, 09:35 


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

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

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

 Профиль  
                  
 
 
Сообщение12.10.2007, 19:40 
Экс-модератор
Аватара пользователя


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

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

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

 Профиль  
                  
 
 
Сообщение12.10.2007, 20:18 
Заслуженный участник


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

 Профиль  
                  
 
 
Сообщение12.10.2007, 20:31 


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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: YandexBot [bot]


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group