2014 dxdy logo

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

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




 
 Итерируем НОД и НОК
Сообщение05.04.2007, 18:06 
Дано несколько натуральных чисел.За одну операцию можно любые два на их НОД и НОК.Докажите,что сначмная с некорого момента числа перестанут изменяться,при этом окончательный результат не зависит от порядка действий

 
 
 
 
Сообщение05.04.2007, 18:32 
Цитата:
За одну операцию можно любые два на их НОД и НОК

что именно можно? :)

 
 
 
 
Сообщение05.04.2007, 18:39 
Аватара пользователя
Надо просто разложить все числа в произведение простых и вспомнить, как вычисляются НОД и НОК.

 
 
 
 
Сообщение05.04.2007, 18:48 
Аватара пользователя
Задача действительно очень простая, так, для начинающих телепатов: пропущено слово "заменить".
А к чему скатятся числа (к общему НОДу и общему НОКу), это вообще банально.

 
 
 
 
Сообщение05.04.2007, 18:58 
Аватара пользователя
ИСН писал(а):
Задача действительно очень простая

Я бы не назвал задачу очень простой. Конечно, более-менее понятно, что числа в конце концов перестанут меняться, но строго доказать это не так-то легко. Я не смог придумать ничего лучше, чем такое: Можно проверить, что после каждой замены (если числа действительно меняются) величина $\prod_{1\leqslant i<j\leqslant n}\min\{a_i;a_j\}$, где $a_1,\ldots,a_n~-$ наши числа, уменьшается, но бесконечно она убывать не может...

ИСН писал(а):
А к чему скатятся числа (к общему НОДу и общему НОКу), это вообще банально.

Количество-то чисел не изменится, там ещё кое-какие числа возникнут (вообще говоря). Но понять, каков будет финал, несложно (ведь для каждого простого $p$ набор степеней, в которых это $p$ делит наши числа, не меняется на каждом шаге...)

 
 
 
 
Сообщение05.04.2007, 20:17 
Аватара пользователя
Вставлю свои пять копеек: утверждение задачи, так как оно сформулировано, вообще говоря, неверно (в части "смачкная (я правильно процитировал? Не уверен) с некорого момента..."). Надо подумать над правильной формулировкой...

 
 
 
 
Сообщение06.04.2007, 00:31 
Аватара пользователя
Я бы сформулировал задачу как-нить вроде такого:
Есть несколько натуральных чисел, с ними разрешено проделывать следующую операцию. Выбираем любые два из них, не делящиеся друг на друга, скажем $a$ и $b$, и заменяем их на $lcd(a;b)$ и $lcm(a;b)$. Доказать, что после конечного числа операций следующую операцию уже нельзя будет выполнить, причём конечный результат...

 
 
 
 
Сообщение06.04.2007, 01:22 
Это можно проще доказать. Назовем пару чисел $(a,b)$ сравнимой, если одно делит другое, т.е. либо $a|b$ либо $b|a$. Тогда после каждого шага количество сравнимых пар будет увеличиваться (если мы будем действовать только на несравнимых)

 
 
 
 Не согласен с RIP
Сообщение15.04.2007, 19:57 
А если взять числа 210,105,770 то в результате получится210,35,2310

 
 
 
 
Сообщение15.04.2007, 20:05 
Аватара пользователя
В чём же Вы со мной не согласны? :?

 
 
 [ Сообщений: 10 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group