Докажите, что не существует бесконечной последовательности одночленов от переменных $$x1....xn,$$ в которой каждый последующий член строго меньше предыдущего в лексикографическом порядке.

задан 8 Июн '15 23:12

изменен 9 Июн '15 10:19

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

10|600 символов нужно символов осталось
1

Вместо одночленов можно рассматривать наборы показателей степеней (векторы), упорядоченные лексикографически. Утверждение доказываем индукцией по числу переменных: всякая убывающая последовательность векторов обрывается. При $%n=1$% это очевидно, так как строго убывающая последовательность целых неотрицательных чисел обрывается.

Пусть $%n > 1$%. Первая координата, равна $%d_1$%, может уменьшаться не более, чем $%d_1$% раз. На промежутках постоянства координаты $%d_1$%, мы фактически имеем лексикографически убывающую последовательность $%(n-1)$%-мерных векторов, каждая из которых конечна по предположению. Тогда и вся последовательность окажется конечной.

ссылка

отвечен 8 Июн '15 23:32

10|600 символов нужно символов осталось
0

Можно доказать по индукции. Для $%n=1$% это очевидно. Пусть утверждение верно для $%k=n$% и докажем, что оно верно для $%k=n+1$%. Рассмотрим первый - больший одночлен вида $%x_0^{k_0}x_1^{k_1}\ldots x_n^{k_n}$%. При фиксированном $%s\leqslant k_0$% по предположению индукции существует только конечное число одночленов $%x_0^{s}x_1^{l_1}\ldots x_n^{l_n}$%, расположенных в лексикографическом порядке. Поэтому рано или поздно цепочка либо оборвется, либо $%s$% должно уменьшиться. Уменьшать $%k_0$% мы можем не более $%k_0$% раз. И при этом мы имеем в последовательности только конечное число одночленов с одинаковым показателем при $%x_0$%. Следовательно, цепочка также оборвется.

ссылка

отвечен 8 Июн '15 23:35

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×3,451
×310

задан
8 Июн '15 23:12

показан
713 раз

обновлен
9 Июн '15 17:59

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru