Processing math: 100%

М2010. Зв’язна клітинна фігура

Задача із журналу «Квант» (2006 рік, №4)

Умова

Для натуральних чисел m і n позначимо через F(m,n) кількість всіх зв’язних клітинних фігур прямокутнику m×n. Доведіть, що парність числа F(m,n) збігається з парність числа n(n+1)2m(m+1)2. (Зв’язна клітинна фігура – це така непорожня множина клітин, що з будь-якої клітини цієї множини можна пройти в будь-яку іншу клітину цієї множини по клітинах цієї множини, переходячи щоразу в сусідню по стороні клітину.)

А.Бадзян

Рішення

Припустимо, що F(m,0)=0. Зв’язні фігури в прямокутнику m×1 – це m фігур з однієї клітини та смужки із двох або більше клітин. Кожна смужка визначається парою клітин – першою та останньою, тому F(m,1)=m+m(m1)2=m(m+1)2.

Нехай у прямокутнику m рядків та n>1 стовпців. Позначимо через l вертикальну вісь симетрії. Кожній зв’язній фігурі відповідає фігура, симетрична щодо l, тому несиметричні щодо l фігури розбиваються на пари, і парність F(m,n) збігається з парністю кількості зв’язних фігур, симетричних щодо l.

Розглянемо деяку фігуру T, симетричну щодо l.

Нехай n непарне, n=2k1, k2. Фігура T містить хоча б одну клітину k-го стовпця, інакше з клітини фігури T неможливо пройти по клітинам T в симетричну відносно l клітину, переходячи кожен раз в сусідню клітину. Зауважимо, що частина T1 фігури T, що розташована в k найлівіших стовпцях, зв’язна. Дійсно, розглянемо дві клітини x та y фігури T1. Нехай x – клітина, що симетрична x відносно l, a x,z1,z2,,zt,y – послідовність клітин, що утворює шлях з x в y по сусідніх клітинах фігури T. Тоді, замінюючи в цьому шляху клітини, що лежать правіше k-го стовпця, на симетричні щодо l, ми отримаємо шлях з x в y по сусідніх клітинах фігури T1 (див. малюнок). Навпаки, якщо фігура T1 розташована у прямокутнику, що складається з k найлівіших



стовпців, зв’язна і містить хоча б одну клітину k-го стовпця, можна однозначно продовжити фігуру T1 до зв’язної фігури T, симетричної відносно l. Кількість зв’язних фігур у прямокутнику m×k дорівнює F(m,k), серед них F(m,k1) фігур лежать у перших k1 стовпцях (тобто не містить клітин k-го стовпця). Отже, кількість зв’язних симетричних щодо l фігур у прямокутнику m×(2k1) дорівнює F(m,k)F(m,k1).

Для парного n=2k, k1, міркуючи аналогічно, встановимо взаємно однозначну відповідність між зв’язними симетричними щодо l фігурами та зв’язними фігурами, що розташовані в перших k стовпцях і що містять хоча б одну клітинку k-го стовпця. Звідси випливає, що кількість зв’язних симетричних щодо l фігур у прямокутнику m×2k дорівнює F(m,k)F(m,k1).

Отже, для n=2k1 и n=2k парність F(m,n) збігається з парністю числа F(m,k)F(m,k1).

Доведемо індукцією по n, що F(m,n) непарно тоді і лише тоді, коли m і n дають залишок 1 або 2 при діленні на 4; звідси відразу випливає твердження задачі. Твердження вірне при n=0 і n=1.

Нехай m дає залишок 0 або 3 при діленні на 4. Припустимо, що це твердження вірне для F(m,0),F(m,1),,F(m,n1), тобто ці числа парні. Якщо n=2k1, k2, або n=2k, k1, то n>k, тому F(m,n) парне, так як F(m,k)F(m,k1) парне. Нехай m дає залишок 1 або 2 при діленні на 4. Припустимо, що твердження вірно для чисел F(m,0),F(m,1),,F(m,n1), тобто F(m,s) непарне тоді і лише тоді, коли s дає залишок від ділення 1 або 2 при діленні на 4. Тоді F(m,s)F(m,s1) непарне тоді і лише тоді, коли s непарне. Звідси випливає, що F(m,n) непарне тоді і тільки тоді, коли n=2(2l+1)1=4l+1 або n=2(2l+1)=4l+2.

А.Бадзян

Базис и размерность линейного пространства. Переход к новому базису


Определение 1
Пусть задано линейное пространство X над полем P  (X,P). Это линейное пространство называется конечномерным, если существует такое натуральное число MN, что любая ЛНЗ система векторов пространства содержит не более M векторов, в противном случае оно называется бесконечномерным.

Определение 2
Пусть (X,P) — конечномерное пространство. Базисом пространства X называется ЛНЗ система векторов, через которую линейно выражается каждый вектор этого пространства.

Определение 3
Размерностью конечномерного пространства X называется число векторов любого его базиса. Обозначается как dimX.

Определение 4
e1,e2,,em — старый базис
g1,g2,,gm — новый базис
x=mj=1αjej=mi=1βigi
Тогда:
{g1=α11e1+α12e1++α1me1g2=α11e1+α12e1++α1me1gm=α11e1+α12e1++α1me1 — система, описывающая переход от старого базиса к новому.

Литература:

  1. Воеводин В.В. Линейная алгебра. М.: Наука, 1980 — стр.19.
  2. Белозёров Г.С. Конспект лекций.
  3. Курош А.Г. Курс высшей алгебры. М.: Наука, 1968 — стр.60-63.

Равенства для модулей произведения и частного

Теорема.
Если a и b комплексные числа, то можно утверждать, что модуль произведение равен произведению модулей. Т.е. |a||b|=|ab|.

Пусть комплексные числа a и b заданы в тригонометрической форме: a=r(cos(ϕ)+isin(ϕ)),b=r(cos(ϕ)+isin(ϕ)). Перемножим эти числа: ab=(r(cos(ϕ)+isin(ϕ)))(r(cos(ϕ)+isin(ϕ)))= =rr(cos(ϕ)cos(ϕ)+icos(ϕ)sin(ϕ)+isin(ϕ)cos(ϕ)sin(ϕ)sin(ϕ))= =rr(cos(ϕ+ϕ)+isin(ϕ+ϕ)). После сокращения мы получили запись произведения ab в тригонометрической форме. Следовательно, |ab|=|a||b|.

Теорема.
Если a и b комплексные числа, то можно утверждать, что модуль частного равен частному модулей. Т.е. |a||b|=|ab|.

Пусть комплексные числа a и b заданы в тригонометрической форме: a=r(cos(ϕ)+isin(ϕ)),b=r(cos(ϕ)+isin(ϕ)), причём b 0, т.е. r 0. Тогда ab=r(cos(ϕ)+isin(ϕ))r(cos(ϕ)+isin(ϕ))= =r(cos(ϕ)+isin(ϕ))r(cos(ϕ)+isin(ϕ))r(cos(ϕ)2+sin(ϕ)2)= =rr(cos(ϕ)cos(ϕ)+isin(ϕ)cos(ϕ)icos(ϕ)sin(ϕ)+ +sin(ϕ)sin(ϕ))=rr(cos(ϕϕ)+isin(ϕϕ)). Следовательно, |ab|=|a||b|.

Литература

  1. Личный конспект, основанный на лекциях Г. С. Белозёрова.
  2. А.Г. Курош Курс высшей алгебры — Москва: Физмалит, 1968. -431с. (с. 118-120).

Равенства для модулей произведения и частного.

Проверим как Вы усвоили материал.

Евклидово пространство

Определение 1. Пусть дано вещественное линейное пространство E. Оно называется евклидовым, если на нем задано отображение из каждой пары векторов в соответствующее ей вещественное число. Назовем это отображение скалярным произведением. Отображение должно удолетворять следующим аксиомам:

  1. (x,y)=(y,x),
  2. (λx,y)=λ(x,y),
  3. (x+y,z)=(x,z)+(y,z),
  4. (x,x)>0приx0;(x,x)=0приx=0;x,y,zE,λR.

Отсюда можно получить ряд следствий:

  1. (x,λy)=λ(x,y),
  2. (x,y+z)=(x,y)+(x,z),
  3. (xz,y)=(x,y)(z,y),
  4. (x,yz)=(x,y)(x,z),
  5. a=mj=1αjxj, b=ni=1βiyi:(x,y)=(mj=1αjxj,b=ni=1βiyi)=mj=1ni=1αjβi(xj,yi)

Любое n-мерное линейное пространство можно превратить в евклидово(с помощью определения в нем скалярного произведения). В n-мерном линейном пространстве скалярное произведение можно задать различными способами.

Например, возьмем в произвольном вещественном пространстве G его некоторый базис g=e1,e2,,en и два любых вектора x, y. Допустим, x=ni=1αieiy=ni=1βiei

Теперь можно ввести скалярное произведение: (x,y)=ni=1αiβi.

Любое подпространство из E может быть Евклидовым, если в нем сохраняется скалярное произведение, определенное в E.

Определение 2. Пусть дан вектор x, принадлежащий евклидову пространству. Если (x,x)=1, то этот вектор называется нормированным. Ненулевой вектор можно нормировать, если умножить его на произвольное число λ: (λx,λx)=λ2(x,x)=1.

Значит, нормирующий множитель (λ)=(x,x)12

Определение 3. Пусть вектор x принадлежит евклидову пространству E. Длиной вектора x назовем число x∣=+(x,x), где xR. Данное определение имеет свойства длины:

  1. 0∣=0.
  2. x∣>0,еслиx0.
  3. λx∣=λx — свойство абсолютной однородности.

Определение 4. Пусть даны векторы x,y, принадлежащие евклидову пространствую. Тогда cos(x,y)=(x,x)xy,0(x,y)π — косинус угла между этими векторами

Рассмотрим применимость школьной геометрии к геометрии евклидова пространства. Пусть заданы два вектора x,yE;x0,y0 — две стороны треугольника. Тогда разность yx — третья сторона. С помощью формулы для угла можно вычислить квадрат третьей стороны: yx2=(yx,yx)=y2+x22(y,x)=y2+x2y∣∣xcos(b,a)

Получили теорему косинусов. Разумеется, если yx, то треугольник является прямоугольным. Также, из последней формулы можно получить теорему Пифагора: yx2=y2+x2. Из той же формулы получаем отношение длин сторон треугольника, если оценивать множитель cos(ba) сверху: yx2y2+x2+2yx=(y+x)2⇒∣yx∣⩽y+x.

И снизу: yx2y2+x22yx=(yx)2⇒∣yx∣⩽yx.

Литература

  1. Электронный конспект по линейной алгебре Белозерова Г.С.
  2. Воеводин В.В. Линейная алгебра.Стр. 88-90
  3. Курош А.Г. Курс высшей алгебры.Стр. 211-212

Теорема об умножении определителей

Теорема об умножении определителей. Определитель произведения двух квадратных матриц порядка n равен произведению определителей этих матриц: det(AB)=det(A)det(B) или полная формула: det(ki=1Ai)=ki=1detAi,Ai(P),i=1,,k.

Для доказательства рассмотрим случай k=2. Допустим заданы две матрицы A=aijMn(P) и B=bijMn(P). Воспользуемся вспомогательной блочной матрицей C=A0EB размера 2n×2n, определитель которой имеет вид: Δ=|a11a12a1n000a21a22a2n000an1an2ann000100b11b12b1n010b21b22b2n001bn1bn2bnn|
Вычислим Δ используя теорему Лапласа. Замечаем, что отличным от нуля будет только det(A). Следовательно, Δ=det(A)det(B). Теперь с помощью элементарных преобразований изменим Δ так, что в итоге получим определитель вида |ACEO|. Где C является произведением матриц A и B. Первый столбец умножим на b11 и прибавим к (n+1)-му столбцу, второй на элемент b21 и вновь прибавим к (n+1)-му столбцу. Так же обнулим остальные элементы матрицы B. Записав подробнее полученный определитель имеем: Δ=|a11a12a1nc11c12c1na21a22a2nc21c22c2nan1an2anncn1cn2cnn100000010000001000| Снова вычислим определитель Δ, разложением по последним n столбцам. В этом случае отличным от нуля минором nго порядка будет определитель матрицы C. Поэтому Δ=detCdet(E)=detC(1)n(1)S1+S2, где S1=2nk=n+1k, a S2=nk=1k. В результате получаем Δ=detC(1)2n(n2+n)=detC. Теперь, подставляя имеем доказательство теоремы: Δ=detC=det(AB)=det(A)det(B).

Замечание Известно, что произведение матриц в общем случае не коммутативно, т.е. ABBA. Но определитель это действительное число, а произведение действительных чисел коммутативно. Следовательно, det(AB)=detAdetB=detBdetA=det(BA)

Теорема об умножении определителей является следствием формулы Бине-Коши. Это теорема об определителе произведения прямоугольных матриц, в случае если это произведение дает квадратную матрицу. Справедлива для матриц с элементами любого коммутативного кольца.

Теорема (формула Бине-Коши). Пусть даны две матрицы A и B размеров (m×n) и (n×m) соответственно. Определитель матрицы равен нулю, если m>n, и равен сумме произведений всех соответствующих миноров m-го порядка мaтрицы A на соответствующие миноры m-го порядка матрицы B, если mn. Миноры матриц A и B одинакового порядка, равного наименьшему из чисел n и m, называются соответствующими друг другу, если они стоят в столбцах матрицы A и строках матрицы B с одинаковыми номерами: detAB=γ1<γ2<<γmAγ1<γ2<<γmBγ1<γ2<<γm,
где Aγ1<γ2<<γm — минор матрицы A, составленный из столбцов с номерами γ1<γ2<<γm, и Bγ1<γ2<<γm — минор матрицы B, составленный из строк с номерами γ1<γ2<<γm.

Допустим C=AB, cij=mγ=1aiγbγi. Значит detC=σ(1)σγ1a1γ1bγ1σ(1)γnanγnbγnσ(n)= =mγ1,,γn=1a1γ1annσ(1)σbγ1σ(1)bγnσ(n)=γ1,,γn=1a1γ1anγnBγ1γn. Минор Bγ1γn не равен нулю только в том случае, когда γ1,,γn попарно различны, значит и суммировать можно по парно различные номера γ1,,γn. Для любой перестановки τ этих номеров справедливо Bτ(γ1)τ(γn)=(1)τBγ1γn, из чего следует γ1,,γn=1a1γ1anγnBγ1γn=γ1<γ2<<γn(1)τa1τ(1)anτ(n)Bγ1γn= =γ1<γ2<<γmAγ1<γ2<<γmBγ1<γ2<<γm.

Примеры решения задач

Рассмотрим примеры решения задач связанных с рассмотренной теоремой. Читателю рекомендовано попытаться решить задачи самостоятельно, а затем сверить свое решение с приведенным ниже.

    1. Найти определитель произведения матриц: A=3418,B=2915

      Решение

      Находим определители данных матриц второго порядка: |3416|=18+4=14 и |2715|=107=3. По теореме об определителе произведения матриц получаем: det(AB)=det(A)det(B)=(14)(3)=42. Вычислим этот же определитель, находя произведение матриц: AB=|3416||2715|=|21423| Следовательно, det(AB)=46+4=42. Результаты совпадают.

    2. Найти определитель матрицы пятого порядка: M=12uvw34xyz003210025300342

      Решение

      Разобьём данную матрицу на 4 блока, M=ABOC где A=1234,
      B=uvwxyz, O=000000, C=321253342.
      Представим блочную матрицу как произведение (в справедливости этого представления можно убедиться, найдя произведение по правилам умножения блочных матриц). D=ABCD=E2OTOCE2BOE3AOTOE3, где E2,E3 — единичные матрицы соответствующих порядков.
      |AOTOE3|=detA=|A|, |E2OTOC|=detC=|C|.
      Матрица E2BOE3 — треугольная с единицами на главной диагонали, следовательно ее определитель равен 1 По теореме об определителе произведения получаем:
      |ABOC|=|E2OTOC| |E2BOE3| |AOTOE3|=|C|1|A|=|A||C| Найдем detA и detC. |1234|=2 |321253342|=15836+30+18=3. Подставляя, получаем, detM=23=6

    3. Представьте в виде определителя произведение определителей: |2111121111211112||4114||3113|
      Решение

      По теореме об определителе ступенчатой матрицы имеем:
      |4114||3113|=|4100140000310013| Предположим A=2111121111211112,B=4100140000310013,
      тогда AB=9644274455755515, по теореме об определителе произведения получаем искомый определитель det(AB)=|9644274455755515|.

Литература

  1. Белозеров Г.С. Конспект лекций по линейной алгебре.
  2. В.А. Ильин, Э.Г. Позняк. Линейная алгебра; 5-е изд., стереотипное. ФИЗМАТЛИТ. — 2002. С. 38-39
  3. А.И. Кострикин. Введение в алгебру. Основы алгебры С.138-139
  4. Курош А.Г. Курс высшей алгебры М.: Наука, 1968, С.93-95
  5. Фаддеев Д. К. Лекции по алгебре: Учебное пособие для вузов.— M.: Наука. Главная редакция физико-математической литературы, 1984.— 416 с. C. 130-134

Теорема об умножении определителей

Тест на знание темы «Теорема об умножении определителей».