?

Log in

No account? Create an account

Популярно о науке

Previous Entry Share Next Entry
Новая задачка
ahiin
Давненько задачек не было. Исправляюсь.

Докажите, что система уравнений



где , т.е. целые, а — натуральное и , имеет только нулевое решение


Задачка не сногсшибательно сложная, сразу предупреждаю.

Ответы скринятся до пятницы.

Решение.

UPD. без ограничений.

  • 1
Это херня - домножаем на p и переносим x-ы влево - дальше получаем обычную совершенно систему линейных уравнений общего вида с целыми коэффициентами. У которой может быть какое угодно решение (втч кстати и в целых числах)

Вы видимо какое-то еще условие забыли.

Edited at 2018-03-13 08:43 am (UTC)

индекс у первого X в последнем уравнении наверное 1?

Да, спасибо.

Если есть ненулевое решение, тогда wlog x_1, x_2, ... x_n целые не имеющие общих делителей. Левая сторона целая. Тогда и правая сторона целая, ergo все иксы делятся на p. Противоречие.

Update: Более развернуто, это система линейных уравнений с рациональными коэффициентами. Если есть ненулевое решение то в решении есть свободные переменные которые можно выбрать рациональными. Очевидно что тогда всё решение будет рациональным (гауссовская элиминация если угодно). Рациональное решение можно превратить умножением на знаменатели в целое. Поделив на наибольший общий делитель, прийдем к целым иксам не имеющим общих делителей. Любое такое решение равно нулю (аргумент выше), следовательно свободных параметров нет и у системы есть уникальное решение равное нулю.



Edited at 2018-03-13 10:15 am (UTC)

В общем, да, всё просто.

Задача сводится к доказательству того, что матрица 1/p*E-А невырожденная. Определитель суммы двух матриц равен сумме определителей всех матриц, полученных комбинированием строк из первой и второй. det(1/p*E) = 1/p^n , a все остальные возможные комбинации строк матриц дадут в сумме определитель вида q/p^k , q, k - целые, k<n. Значит, итоговая сумма будет q/p^k + 1/p^n != 0.

; D J"^\-&.hN:RZ}`X1,LiP-Q}-Zޚp6hid

1. Переносим всю правую часть в лево.
Тогда [A-B] x [X] = [0], где
- [A] - матрица коэф-ов aij
- [B] - диагональная матрица из коэф-ов 1\p
- [0] -- нулевая матрица

Тогда у этого уравнения могут быть решения ровно 2х видов:

(1) [X] == 0 // просто приводим матрицу к "ступенчатому" виду методом Гаусса
(2) [X] -- любое (матрица [A-B] вырожденная (или какой там термин) матрица).

2. Рассмотрим матрицу [A-B].
В ней на главной диагонали находятся рациональные числа вида: (a[i,i]*p - 1)/p -- рациональные числа в канонической форме не являющиеся целыми (p > 1).

Тогда матрица не вырожденная, т.е. не существует такой линейной комбинации строк (с целыми коэф-ми), что c1*A[1] + c2*A[2]+ ... + Cn*A[n] = 0.
(NOTE: я не смог доказать что решения нет в иррациональных числах, но в рациональных его точно нет).
Предположим противно, что решение в рациональных числах есть (такой набор c1, c2, c3...cn) => оно есть в целых числах домножив на знаменатели (d1, d2, d3...dn) => оно есть в целых числах с НОД=1, поделив на НОД(d1..dn) -- такой набор (e1, e2,..en), что они целые и НОД(e1..en)=1.
Но:
e1 делится на p -- иначе при сумме целых с (a[i,i]*p-1)/p никак не получить 0
e2 делистя на p
...
en делится на p
Следовательно наше предположение не верно => набора c1,c2...cn в рациональных числах нет и матрица не вырожденная.

3. Но для невырожденной матрицы существует ровно одно решение методом Гаусса (док-во заняло у меня 2 страницы, я приводил матрицу к "ступенчато-единичному" виду, т.е. ступенчатая матрица с 1й на главной диагонали для определённости).

Update:
*) В пункте 2 среди коэф-ов c1, c2...cn бутед минимум 2 ненулевых (поэтому можно использовать НОД).
2 ненулевых будет по построению:
A[i] = b1*A[1] + b2*A[2]...+bn*A[n].
ненулевым будет сi, и также минимум один из остальных коэф-ов, поскольку A[i,i] != 0 => хотя бы один из коэф-ов справа также ненулевой.
**) В пункте "3" своего док-ва к сожалению нашёл ошибку.
Поэтому просто сошлюсь (по памяти): если матрица коэф-ов невырожденная (т.е. ни одна её строка не является линейной комбинацией других строк), у системы линейных уравнений ровно 1 решение.


ПС
Вот токое вот доказательство.
Вероятно для того, чтобы доказать, что решения (c1...cn) нет и в иррациональных числах надо рассмотреть транспонированную матрицу, убедиться, что она получается из исходной только операциями + - * / => иррациональных коэф-ов там появиться не должно.
Но это будет уже не честно, т.к. надо лезть в гугл.

Вот такое вот решение на 1/2



Edited at 2018-03-14 08:42 am (UTC)

Re: Доказал наполовину.. Док-во окончательное (гуглить н

Ниже Ваш комментарий на мой комментарий что-то всё ещё скрыт.

Рациональные решения исключаются от противного теорией чисел (основную теорему арифметики в школе вроде бы проходят). (Исключаем нетривиальные целые решения от противного делимостью на произвольно большую степень какого-нибудь простого делителя p; рациональное решение от домножения на знаменатели становится целым.)

Сложно можно объяснить и обычное (делимость определителя) решение школьникам без слова "матрица" (подстановками и преобразованиями), но я конечно имел в виду не такое "жульническое" решение.

Так что задача, наверное, хороша для пропаганды определителей и линейной алгебры (которую традиционно не принято преподавать школьникам в том числе на мат. кружках).

Re: Доказал наполовину.. Док-во окончательное (гуглить н

Прозевал, расскиринивая. Исправлено.

Уравнение можно переписать в виде


A - матрица, x - вектор.

Нам достаточно показать, что никакое собственное значение матрицы не может равняться 1/p.

Уравнение на собственные значения:
det(A-λE)=0,

что можно изобразить как уравнение
λn + bn-1λn-1 + ... + b0 = 0

причем все коэффициенты b являются целыми числами, так как получаются из коэффициентов матрицы с помощью умножений и сложений.

Предположим, от противного, что 1/p является одним из решений этого уравнения:

p-n + bn-1p-(n-1) + ... + b0 = 0

Помножим обе части на pn:

1 + bn-1p + bn-2p2 + ... + b0pn = 0

И перепишем в виде:

1 + pC = 0, где

C = bn-1 + bn-2p + ... + b0pn-1 - целое число.

Получаем

C = -1/p

При p > 1, число C не может быть целым - мы пришли к противоречию.




Edited at 2018-03-13 12:08 pm (UTC)

напоминает задачу

про взвешивания: если в группе монет после удаления любой можно разложить оставшиеся на две равные по весу и количеству кучи, то все монеты равного веса...

А есть простое решение, доступное школьникам, допустим, восьмого класса?
(Да, задача несложная, но вряд ли стыдно давать её, например, на пятёрку на соответствующем экзамене.)

На уровне общеобразовательной школы, насколько я помню ее программу, решение мне неизвестно.

В пункте "3" моего док-ва (который по сути дублирует существующие теоремы-леммы, сделал update со ссылкой на них) я к сожалению нашёл ошибку (нерассмотренный случай).
Однако если доказать это удастся (появился новый стимул) -- вроде бы там вся математика доступная 8му классу.

ПС
Вся неэлементарность только в нотации, использованной для сокращения записи, а так-то можно раскрыть её и в понятных 8му классу терминах.

Edited at 2018-03-14 08:43 am (UTC)

собственно, и однозначность не нужна, надо сказать, что по индукции все числа в целом решении делятся на любую степень p

Spoiler
ну и вроде бы тогда нам надо решать уравнение в R (рациональных числах), а не Q.
Что решений нет в Q -- "как-бы очевидно", но вот прям строго доказать не могу.

Я знаю, что в русской традиции 0 -- не явл-ся натуральным, числом, а в зарубежной (англ. литературе) является.

Повлияла ли "каноническая форма целого числа, где в знаменателе число натуральное, на отечественное определение N?

Вообще без понятия.
За рубежом там тоже не то что бы единство. Нередко они прямо указывают N0, чтобы не было путаницы.

ну, если спрашивать только про рациональные решения, то разложение на множители в школе принято как-то стыдливо, но использовать...

Ну да, если с учителем повезло. В самой программе, по крайней мере в начале 90-х, когда я учился, разложение упоминалось без доказательства разок, и более нигде не использовалось.

я сообразил что поторопился и разложение не нужно (надо доказывать делимость на всё большие степени), но вот как перейти к рациональным решениям без стандартного рассуждения об исключении неизвестных (которое в принципе ничего нешкольного не содержит, но всё-таки...)

Ну вроде как для 8го рано.

А вот упрощённый (const == 0) метод Гаусса (нам его в 9м классе на информатике давали) + каноническая форма натурального числа (вроде 10й класс) -- для 10го класса задача (не знаю со (*) или без).

(с телефона)
Перенесём все в одну сторону. Поменяв знак (числа a_ij целые, поэтому можно), получим матрицу коэффициентов, которая поставлена из диагонали (1/p) сложенной с матрицей целых чисел.

Наверное, можно опознать какую-то известную матрицу.

Но можно показать, что в определителе будет одно слагаемое 1/p^n (и куча других слагаемых меньшей степени 1/p), и определитель никогда не обращается в ноль. Это можно показать, например, раскладывая определитель по столбцам.

А раз так, то столбцы линейно независимы, и нет нетривиального решения.

  • 1