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.

А.Бадзян

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

Теорема об умножении определителей. Определитель произведения двух квадратных матриц порядка 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

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

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

Формула Муавра

Теорема. Допустим z=r(cosϕ+isinϕ) и n принадлежит множеству целых чисел. Тогда можно считать, что zn=rn(cos(nϕ)+isin(nϕ)).

Пусть n=2, где nZ — база индукции. Тогда z2=r(cosϕ+isinϕ)r(cosϕ+isinϕ)=r2(cos(2ϕ)+isin(2ϕ)).

Допустим, что теорема верна nm,m2 и докажем, что она так же верна и для n=m+1. Тогда zm+1=zmz=rm(cos(mϕ)+isin(mϕ))r(cosϕ+isinϕ)=
=rm+1(cos(m+1)ϕ+isin(m+1)ϕ).
Для n=1 формула простая, а если n=0, то z=1, то есть z0=r0(cos(0ϕ)+isin(0ϕ))=1(cos0+isin0)=1.
Следовательно, теорема справедлива n0. Докажем, что она так же справедлива n<0. Тогда zn=1zn=1(r(cosϕ+isinϕ))n=
=1rn(cos(nϕ)+isin(nϕ))=rncos(nϕ)isin(nϕ)cos(nϕ)2+sin(nϕ)2=
=r1cos(nϕ)+isin(nϕ)1=rn(cos(nϕ)+isin(nϕ)).
Теорема доказана.

Следствие.|zn|=|z|nnZ,Arg(zn)=nArg(z)+2πk,kZ,nZ.

Примеры

Рассмотрим несколько примеров с использованием формулы Муавра.

  1. Вычислить 5(1+i)3(3+i)4i1323.
    Решение

    Найдём сначала r для (1+i)3: r=(1)2+12=2.

    Теперь найдём аргумент z для (1+i)3. Для этого нужно найти угол α: tanα=1,α=π4+kπ,kZ.
    Так как sinα<0 и cosα<0, то α=3π4.
    Теперь найдём r и z для (3+i)4: r=32+12=4=2.
    Найдём z:
    tanβ=13,β=π6+sπ,sZ.
    Так как sinβ>0 и cosβ>0, то β=π6. (1+i)3(3+i)4=(cos(9π4+4π6))+isin(9π4+4π6)=
    =cosπ12+isinπ12,
    i1323=i.
    По формуле ϕ+2πkn, где n=5, k=¯0,4 получаем:w0=52316(cos(π125)+isin(π125))=52316(cos(π60)+
    +isin(π60)),
    w1=52316(cos(π12+2π5)+isin(π12+2π5))=
    =52316(cos(25π60)+isin(25π60)),
    w2=52316(cos(π12+4π5)+isin(π12+4π5))=
    =52316(cos(49π60)+isin(49π60)),
    w3=52316(cos(π12+6π5)+isin(π12+6π5))=
    =52316(cos(73π60)+isin(73π60)),
    w4=52316(cos(π12+8π5)+isin(π12+8π5))=
    =52316(cos(97π60)+isin(97π60)).

  2. Вычислить (3+i)2020.
    Решение

    tanα=33,α=π6+kπ,kZ.

    Так как sinβ>0 и cosβ>0, то β=π6. (3+i)2020=(2(cosπ6+isinπ6))2020=
    =22020(cos(2018+26π)+isin(2018+26π))=
    =22020(cosπ3+isinπ3)=22020(12+i32).

Смотрите также

  1. А.И. Кострикин Введение в алгебру. Основы алгебры. — Москва: Физматлит, 1994. -320с. (с. 201-202).
  2. Личный конспект, основанный на лекциях Г. С. Белозёрова.

Формула Муавра

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

Критерий совместности СЛАУ Кронекера-Капелли

Теорема Кронекера-Капелли. Критерий совместности системы линейных алгебраических уравнений. СЛАУ совместна тогда и только тогда, когда ранг матрицы системы равен рангу расширенной матрицы. То есть, если в СЛАУ r=rangA=rang˜A, где rangA — обозначает ранг матрицы системы, а rang˜A — ранг расширенной матрицы, тогда данная матрица совместна, причём система имеет единственное решение, если rangA=rang˜A=n, где n — число неизвестных, и бесконечное число решений, если rangA=rang˜A<n.

Необходимость. Пусть задана расширенная матрица ˜A:

˜A={a11x1+a12x2++a1nxn=b1a21x1+a22x2++a2nxn=b2am1x1+am2x2++amnxn=bm

Скажем, что данная система совместна, в таком случае существуют числа (c1,c2,,cn), которые являются частным решением матрицы, при подстановке их в систему. Мы получим равенство:

b1b2bn=c1a11a21am1+c2a12a22am2++cna1na2namn

Следовательно, вектор-столбец свободных членов является линейной комбинацией столбцов (a1,a2,,an), матрицы A. Так же, мы можем заметить, что сколько бы мы раз не приписали или не вычеркнули строку(столбец), от этого не меняется ранг системы, из этого следует, что rangA=rang˜A.

Достаточность. Если rangA=rang˜A, то это означает, что у них один и тот же базисный минор. Тогда, согласно теореме о базисном миноре, последний столбец свободных членов – линейная комбинация столбцов базисного минора.

Следствие:

  1. rangA=rang˜A=n единственное решение.
  2. rangA=rang˜A<n бесконечное число решений.
  3. Количество главных переменных равно рангу системы.

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

Рассмотрим примеры задач, в которых используеться критерий совместности rangA=rang˜A.

  1. {2x1x2+5x3=43x1x2+5x3=05x12x2+3x3=2

    Решение

    Сначала, приведем матрицу к треугольному виду.

    (215431505232)(125413502532)

    (115401040177)(115401040073)

    Элементарные преобразования не меняют ранга матриц, поэтому в результате выполненных действий, получены эквивалентные исходнной матрице системы A=(115010007) и расширенная матрица системы ˜A=(115401040073)

    rangA=rang˜A=3 значит, по теореме Кронекера-Капелли система совместна.

  2. {x1+x2x3=7x1+2x23x3=12x12x3=3

    Решение

    Приведем матрицу к ступенчистому виду:

    (111412302023)(111401240245)(1114012400013)

    ˜A=(1114012400013)=rang˜A=3

    A=(111012000)=rangA=2

    rangArang˜A. По теореме Кронекера-Капелли система линейных уравнений несовместна.

  3. {5x13x2+2x3+4x4=34x12x2+3x3+7x4=18x16x2x35x4=97x13x2+7x3+17x4=λ

    Решение

    Очевидно, что от значения λ зависит, будет ли матрица совместна или нет.

    Сначала приведем матрицу к треугольному ввиду:

    ˜A=(53243423718615973717λ)(111324237102719773717λ)

    (11132027197027197041438λ14)(11132027197000000000λ)

    При λ0: rang˜A=3, rangA=2. По теореме Кронекера-Капелли система линейных уравнений несовместна.

    При λ=0: rang˜A=2, rangA=2. По теореме Кронекера-Капелли система линейных уравнений совместна.

Критерий совместности СЛАУ Кронекера-Капелли

Тест на закрепление материала «Критерий совместности СЛАУ Кронекера-Капелли».

Литература

  1. Личный конспект, составленный на основе лекций Белозерова Г.С.
  2. Фадеев Д.К. Лекции по алгебре. М.: Наука, 1984.-416 с.  стр 119.
  3. Проскуряков И.В. Сборник задач по линейной алгебре. М.: Наука, 1984.-384 с.  стр 101-103.

Простейшие сведения о непрерывных дробях и их свойствах

Пусть число \usepackageamsfontsxR. Тогда обозначим через q1 наибольшее целое число, меньшее x. Если x не целое число, то мы получим равенство вида x=q1+1x1, так как дробь 1x1<1, то x1>1, и тогда аналогично для x1 находим такое целое q2<x1, получаем x1=q2+1x2, возвращаясь к первому равенству x=q1+1q2+1x2. Продолжая этот процесс будем получать представления последующих xk: x2=q3+1x3,

x3=q4+1x4,
xi=qi+1+1xi+1,

В итоге и получим непрерывную дробь: \usepackageamsmathx=q1+1q2+1q3++1qn1+1qn+1xn.

Далее, нам стоит рассмотреть два случая: первый — \usepackageamsfontsxQ, т. е. xрациональное число и второй — \usepackageamsfontsxRQ, т. е. xиррациональное число. Почему важны именно эти случаи?

По определению, рациональное число представимо в виде несократимой дроби mn, где \usepackageamsfontsmZ,nN, а, значит, и разложение, представленное сверху, должно быть конечным и, более того, может быть получено благодаря алгоритму Евклида.

С иррациональным числом получим ситуацию обратную — процесс можно будет продолжать неограниченно долго т. к. на каждом этапе xi будет иррационально.

Пусть xi — иррационально, тогда xi=qi+1+1xi+1,

сумма qi+1+1xi+1 — иррациональна, однако qi+1 является целым по определению, которое мы дали ему выше дробь 1xi+1 должна быть иррациональной. А это означает, что и xi+1 — иррациональное число.

Т. е. получаем, что иррациональность xi влечёт за собой иррациональность xi+1, а т. к. изначальное число x — иррационально, то и все xj, при j=1,2,3 — иррациональны.

Как было упомянуто ранее, если \usepackageamsfontsxQ, то его разложение в непрерывную дробь можно получить с помощью алгоритма Евклида.

Перед описанием алгоритма стоит ввести понятие неполного частного — это целые числа вида qi,i=¯1,n.

Опишем сам алгоритм:

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

Пусть нам задано рациональное число, тогда его можно записать в виде несократимой дроби mn, где \usepackageamsfontsmZ,nN. Тогда, первый шаг: m=nq1+r1mn=q1+1mr1,

узнали значение q1, а так же получили возможность вычислить значение r1. Второй шаг: n=r1q2+r2nr1=q2+1r1r2,
узнали значение q2, а так же получили возможность вычислить значение r2. Продолжая алгоритм далее: r1=r2q3+r3r1r2=q3+1r2r3,r2=r3q4+r4r2r3=q4+1r3r4,rn2=rn1qn+rnrn2rn1=qn+1rn1rn,rn1=rnqn+1,rn1rn=qn+1.
Заканчиваем алгоритм тогда, когда получим, что очередная дробь ri1ri будет целым числом и, соответственно, qi+1 будет полным частным.

Так как найдены все неполные частные, то дробь mn можно представить в виде: \usepackageamsmathx=q1+1q2+1q3++1qn1+1qn+1qn+1.

С помощью алгоритма Евклида есть возможность найти разложение в непрерывную дробь, однако, иногда промежуточные результаты важнее конечного, а именно: δ1=q1,δ2=q1+1q2,δ3=q1+1q2+1q3,

δi называются подходящими дробями. Несложно заметить зависимость δi+1 от δi — если в записи δi число qi заменить на сумму qi+1qi+1, то мы получим δi+1.

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

Введем специальные обозначения для нахождения значений подходящих дробей: δi=PiQi. При этом положим, что P0=1,P1=q1 и Q0=0,Q1=1. Так же стоит отметить, что в силу того, что для рационального числа x=mn непрерывная дробь конечна, то и количество подходящих дробей будет конечно, а это означает что существует равенство mn=PiQi. А так как подходящие дроби так же являются несократимыми, то равенство можно упростить до m=Pi и n=Qi. Тогда получим, что: δ1=q11=P1Q1,

δ2=q1+1q2=q2q1+1q21+0=q2P1+P0q2Q1+Q0=P2Q2,
δ3=q1+1q2+1q3=q1(q2+1q3)+1q2+1q3=q1(q2q3+1)+q3q2q3+1=
=q1q2q3+q1+q3q2q3=q3(q1q2+1)+q1q3q2+1=q3P2+P1q3Q2+Q1.

Несложно заметить рекуррентное выражение для PiQi: Pi=qiPi1+Pi2Qi=qiQi1+Qi2.

Докажем это с помощью математической индукции.

База индукции: δ3=P3Q3=q3P2+P1q3Q2+Q1.

Предположим, что δk=PkQk=qkPk1+Pk2qkQk1+Qk2.

Тогда: δk+1=(qk+1qk+1)Pk1+Pk2(qk+1qk+1)Qk1+Qk2=Pk1qk+1+qkPk1+Pk2Qk1qk+1+qkQk1+Qk2=

(выполним замену по предположению индукции) =Pk1qk+1+PkQk1qk+1+Qk=Pk1+Pkqk+1Qk1+Qkqk+1=Pk+1Qk+1,
что и требовалось доказать.

Имеет место следующее свойство подходящих дробей:

Лемма. При n>0 имеет место равенство PnQn1Pn1Qn=(1)n.

Проверим значение левой части при n=1, получим: P1Q0P0Q1=1,

далее вычислим значение левой части при увеличении индекса на 1, т. е. при n+1, получим: Pn+1QnPnQn+1=(qn+1Pn+Pn1)QnPn(qn+1Qn+Qn1)==Pn1QnPnQn1,
получили выражение противоположное заданному в условии. А, значит, при изменении индекса на единицу меняется и знак выражения, а т. к. первое значение 1, то и получаем требуемое.

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

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

  1. Разложить число x=8913 в непрерывную дробь.
    Решение

    Применяя алгоритм Евклида получим: 89=136+11,q1=6;

    13=111+2,q2=1;
    11=25+1,q3=5;
    2=12,q4=2.
    Нашли все qi можем записать x как непрерывную дробь: x=6+11+15+12

  2. Найти все подходящие дроби числа x=12719.
    Решение

    Для этого используем рекуррентные формулы подходящих дробей. Воспользуемся алгоритмом Евклида для поиска всех qi: 127=196+13,q1=6;

    19=131+6,q2=1;
    13=62+1,q3=2;
    6=16,q4=6.

    Далее будем выписывать подходящие дроби в порядке возрастания индекса: δ1=q11=61
    δ2=q2P1+P0q2Q1+Q0=16+111+0=71,
    продолжая расчеты получим: δ3=27+621+1=203
    и, наконец, δ4=620+763+1=12719=x,
    как и ожидалось четвертая подходящая дробь равна заданному числу, т. к. максимальный индекс qi был равен четырём.

  3. Разложить в непрерывную дробь иррациональное число 7.
    Решение

    Для этого воспользуемся разложением, которое было представлено в теме первым. А именно
    x0=7=q1+1x1=2+(72)

    1x1=72x1=172=7+23=1+713=1+1x2,
    x2=371=3(7+1)6=7+12=1+712=1+1x3,
    x3=271=2(7+1)6=7+13=1+723=1+1x4,
    x4=372=3(7+2)3=7+2=4+(72).

    Однако, слагаемое вида 72 у нас уже было, а значит мы пришли к циклу. Выпишем все неполные частные, они же — целые части дробей. Получим: 7=[2,¯1,1,1,4] — часть чисел находятся под чертой т. к. они находятся в цикле.

  4. Восстановить по заданным qi=[10,4,3,2,4] рациональное число x.
    Решение

    Для этого воспользуемся разложением, полученным в результате алгоритма Евклида:
    Получим дробь: 10+14+13+12+14,

    её значением и будет искомым x. Посчитав значение этой дроби получим, что x=1361133.

  5. Восстановить по заданным qi=[¯2,9] иррациональное число x.
    Решение

    Так как число x — иррациональное, то его непрерывная дробь будет бесконечной, поэтому воспользоваться методом из предыдущего примера не получится. Однако, так как мы видим по данным qi, что дробь зацикливается, то можем записать следующие выражение: x=2+19+1x

    приведем дробь к квадратному уравнению: 9x218x+2=0,
    D=324+72=396,x1,2=1±39618.
    Т. к. целая часть числа равна 2, то вариант x=139618 можно отбросить. И окончательный ответ: x=1+39618

Простейшие сведения о непрерывных дробях и их свойствах

Тест на знание темы «Простейшие сведения о непрерывных дробях и их свойствах».

Смотрите также

  1. Виноградов И.М. Основы теории чисел. cтр. 14-18
  2. Арнольд В.И. Цепные дроби.
  3. Теоретические материалы основанные на конспекте и лекциях Белозерова Г.С.