Итерируем НОД и НОК

[c57]

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

[Trius]

Цитата:

За одну операцию можно любые два на их НОД и НОК

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

[RIP]

Надо просто разложить все числа в произведение простых и вспомнить, как вычисляются НОД и НОК.

[ИСН]

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

[RIP]

ИСН писал(а):

Задача действительно очень простая

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

ИСН писал(а):

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

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

[Хорхе]

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

[RIP]

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

[Dandan]

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

[c57]

А если взять числа 210,105,770 то в результате получится210,35,2310

[RIP]

В чём же Вы со мной не согласны?