Реферат: Возвратные задачи
--PAGE_BREAK----PAGE_BREAK--Таким образом, мы показали, что соотношения (11) и (12) верные.Выше было показано, что J – рекуррентность имеет решение в двоичной записи: J((bmbm-1 … b1 b0)2) = (bm-1 … b1 b0bm)2, где bm = 1. Можно показать, что и обобщенная рекуррентность (10) имеет похожее решение.
Запишем соотношение (10) следующим образом:
f(1) = α,
f(2n + j) = 2f(n) + βj при j = 0, 1 и n ≥ 1,
если положить β0= β и β1 = γ. Тогда:
f((bmbm-1 … b1 b0)2) = 2f((bmbm-1 … b1)2) + βb<shape id="_x0000_i1085" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image105.wmz» o:><img width=«12» height=«25» src=«dopb74651.zip» v:shapes="_x0000_i1085"> = 4f((bmbm-1…b2)2)+2βb<shape id="_x0000_i1086" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image107.wmz» o:><img width=«9» height=«25» src=«dopb74652.zip» v:shapes="_x0000_i1086">+βb<shape id="_x0000_i1087" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image109.wmz» o:><img width=«12» height=«25» src=«dopb74651.zip» v:shapes="_x0000_i1087">= =…=2mf((bm)2)+2m-1βb<shape id="_x0000_i1088" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image110.wmz» o:><img width=«29» height=«25» src=«dopb74653.zip» v:shapes="_x0000_i1088">+ … + 2βb<shape id="_x0000_i1089" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image107.wmz» o:><img width=«9» height=«25» src=«dopb74652.zip» v:shapes="_x0000_i1089">+βb<shape id="_x0000_i1090" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image109.wmz» o:><img width=«12» height=«25» src=«dopb74651.zip» v:shapes="_x0000_i1090">= 2m α + 2m-1βb<shape id="_x0000_i1091" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image110.wmz» o:><img width=«29» height=«25» src=«dopb74653.zip» v:shapes="_x0000_i1091">+ … + 2βb<shape id="_x0000_i1092" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image107.wmz» o:><img width=«9» height=«25» src=«dopb74652.zip» v:shapes="_x0000_i1092">+βb<shape id="_x0000_i1093" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image109.wmz» o:><img width=«12» height=«25» src=«dopb74651.zip» v:shapes="_x0000_i1093">.
Если мы расширим систему счисления с основанием 2 таким образом, что в ней допустимы произвольные числа, а не только 0 и 1, тогда предыдущий вывод означает, что
f((bmbm-1 … b1 b0)2) = (α βb<shape id="_x0000_i1094" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image110.wmz» o:><img width=«29» height=«25» src=«dopb74653.zip» v:shapes="_x0000_i1094"> βb<shape id="_x0000_i1095" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image112.wmz» o:><img width=«32» height=«25» src=«dopb74654.zip» v:shapes="_x0000_i1095"> … βb<shape id="_x0000_i1096" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image107.wmz» o:><img width=«9» height=«25» src=«dopb74652.zip» v:shapes="_x0000_i1096"> βb<shape id="_x0000_i1097" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image109.wmz» o:><img width=«12» height=«25» src=«dopb74651.zip» v:shapes="_x0000_i1097">)2 (16)
Итак, изменение системы счисления привело нас к компактному решению (16) обобщенной рекуррентности (15).
Глава 2
Решение задач
Задача 1. То, что все лошади одной масти, можно доказать индукцией по числу лошадей в определенном табуне. Вот так:
«Если существует только одна лошадь, то она своей масти, так что база индукции тривиальна. Для индуктивного перехода предположим, что существует nлошадей (с номерами от 1 до n). По индуктивному предположению лошади с номерами от 1 до n−1 одинаковой масти, и, аналогично, лошади с номерами от 2 до nимеют одинаковую масть. Но лошади посередине с номерами от 2 до n−1 не могут изменять масть в зависимости от того, как они сгруппированы, — это лошади, а не хамелеоны. Поэтому в силу транзитивности лошади с номерами от 1 до nтакже должны быть одинаковой масти. Таким образом, все nлошадей одинаковой масти. Что и требовалось доказать».
Есть ли ошибка в приведенном рассуждении и, какая именно?
Решение. Ошибка в данном рассуждении есть, и она заключается в доказательстве по индуктивному предположению. Для доказательства того, что n лошадей имеют одинаковою масть, используется пересечение двух множеств от 1 до n−1 и от 2 до n, но для n = 2 этого пересечения нет. Поэтому, если есть две лошади, имеющие разную масть, то утверждение неверно. Если же любые две лошади имеют одинаковую масть, то доказательство будет верным для любого n.
Задача 2. Найдите кратчайшую последовательность перекладываний, перемещающих башню из nдисков с левого колышка А на правый колышек B, если прямой обмен между А и Bзапрещен. (Каждое перекладывание должно производиться через средний колышек. Как обычно, больший диск нельзя класть на меньший.)
<img width=«2» height=«49» src=«dopb74655.zip» v:shapes="_x0000_s1127"><img width=«2» height=«49» src=«dopb74655.zip» v:shapes="_x0000_s1128"> <img width=«26» height=«8» src=«dopb74656.zip» v:shapes="_x0000_s1130"><img width=«2» height=«48» src=«dopb74657.zip» v:shapes="_x0000_s1131">Решение.
<img width=«91» height=«18» src=«dopb74658.zip» v:shapes="_x0000_s1132 _x0000_s1134 _x0000_s1133"> <img width=«89» height=«2» src=«dopb74659.zip» v:shapes="_x0000_s1136"> <img width=«90» height=«2» src=«dopb74660.zip» v:shapes="_x0000_s1135">
Пусть Fn — минимальное число перекладываний, необходимых для перемещения n дисков с одного колышка на другой через колышек С.
Рассмотрим крайние случаи: F0=0, F1=2, F2=8, F3=26. Эксперимент с тремя дисками дает ключ к общему правилу перемещения n дисков: сначала мы перемещаем (n−1) меньших дисков на колышек B (что требует Fn-1 перекладываний), затем перекладываем самый большой диск на колышек С (одно перекладывание), потом помещаем (n−1) меньших дисков на колышек А (еще Fn-1 перекладываний), затем перекладываем самый большой диск на колышек B (одно перекладывание), и, наконец, помещаем (n−1) меньших дисков на колышек B (еще Fn-1 перекладываний). Таким образом, n дисков (при n>0) можно переместить самое большое за 3Fn-1+2 перекладываний (т.е. достаточно перекладываний): Fn≤ 3Fn-1+2.
Сейчас покажем, что необходимо 3Fn-1+2 перекладываний. На двух этапах мы обязаны переместить самый большой диск. Когда мы это делаем, (n−1) меньших дисков должны находиться на одном колышке (А или B), а для того чтобы собрать их вместе, потребуется, по меньшей мере, Fn-1 перекладываний. Самый большой диск можно перекладывать и более одного раза. Следовательно, Fn≥ 3Fn-1+2.
Эти два неравенства вместе с тривиальным решением при n=0 дают рекуррентное соотношение:
F0=0
Fn= 3Fn-1+2 при n>0
Решим данное соотношение.
Первый способ решения (угадывание правильного решения с последующим доказательством, что наша догадка верна). Вычислим: F1=2=31 −1, F2=32 −1, F3=33 −1. Из этого можно сделать предположение, что
Fn= 3n−1 при n≥0.
Докажем методом математической индукции по числу n:
1) База: n=0, F0=30–1=1–1=0 (верно);
2) Индуктивный переход: пусть доказано для всех чисел t ≤ (n–1). Докажем для t=n: Fn= 3Fn-1+2 <shape id="_x0000_i1098" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image020.wmz» o:><img width=«44» height=«36» src=«dopb74605.zip» v:shapes="_x0000_i1098"> 3(3n-1−1)+2 = 3n − 1.
Из пунктов 1 и 2 следует: при n≥0 Fn= 3n − 1.
Второй способ решения.
К обеим частям соотношения (1) прибавим 1:
F0+1 = 1,
Fn+1 = 3Fn-1+3 при n>0.
Обозначим Un= Fn+1, тогда получим: U0 = 1, Un= 3Un-1 при n>0.
Решением этой рекурсии есть Un=<shape id="_x0000_i1099" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image120.wmz» o:><img width=«21» height=«25» src=«dopb74661.zip» v:shapes="_x0000_i1099">; следовательно, Fn = <shape id="_x0000_i1100" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image122.wmz» o:><img width=«21» height=«25» src=«dopb74661.zip» v:shapes="_x0000_i1100">−1.
В дальнейшем мы не будем показывать достаточное и необходимое условие в решении подобных задач, а сразу будем описывать получение нужного равенства. Это связано, во-первых, с тем, что достаточное и необходимое условие показывается аналогично тому, как это сделано в данной задаче, а во-вторых, в виду ограниченности объема дипломной работы.
Задача 3. Покажите, что в процессе перемещения башни при ограничениях из предыдущего упражнения нам встретятся все допустимые варианты размещения nдисков на трех колышках.
<img width=«2» height=«84» src=«dopb74662.zip» v:shapes="_x0000_s1137"> <img width=«38» height=«8» src=«dopb74663.zip» v:shapes="_x0000_s1140"><img width=«56» height=«8» src=«dopb74664.zip» v:shapes="_x0000_s1141">Решение. Занумеруем диски
<img width=«50» height=«36» src=«dopb74665.zip» v:shapes="_x0000_s1143 _x0000_s1142">
<img width=«3» height=«19» src=«dopb74666.zip» v:shapes="_x0000_s1144"><img width=«195» height=«3» src=«dopb74667.zip» v:shapes="_x0000_s1145"><img width=«169» height=«9» src=«dopb74668.zip» v:shapes="_x0000_s1146"> SHAPE \* MERGEFORMAT <lock v:ext=«edit» aspectratio=«t»><shape id="_x0000_s1148" type="#_x0000_t75" o:divferrelative=«f»><fill o:detectmouseclick=«t»><path o:extrusionok=«t» o:connecttype=«none»><lock v:ext=«edit» text=«t»><img width=«624» height=«28» src=«dopb74669.zip» v:shapes="_x0000_s1147 _x0000_s1148 _x0000_s1149 _x0000_s1150 _x0000_s1151 _x0000_s1152"><lock v:ext=«edit» rotation=«t» position=«t»>
Существует (в соответствии с условиями задачи) только три возможных расположения каждого диска на одном из колышков: либо на первом колышке (А), либо на втором колышке (B), либо на третьем колышке (С). Это будут перестановки длины n из трех элементов. Например, <shape id="_x0000_i1102" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image131.wmz» o:><img width=«163» height=«39» src=«dopb74670.zip» v:shapes="_x0000_i1102">.
<shape id="_x0000_i1103" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image133.wmz» o:><img width=«13» height=«25» src=«dopb74671.zip» v:shapes="_x0000_i1103">Число перестановок длины k из n элементов: <shape id="_x0000_i1104" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image135.wmz» o:><img width=«64» height=«29» src=«dopb74672.zip» v:shapes="_x0000_i1104">. Следовательно, для нашего случая <shape id="_x0000_i1105" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image137.wmz» o:><img width=«63» height=«29» src=«dopb74673.zip» v:shapes="_x0000_i1105">, т.е. <shape id="_x0000_i1106" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image139.wmz» o:><img width=«21» height=«25» src=«dopb74661.zip» v:shapes="_x0000_i1106"> – это все возможные различные расположения n дисков на трех колышках.
В предыдущей задаче было показано, что наименьшее число перекладываний с колышка А на колышек B через колышек С равно <shape id="_x0000_i1107" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image140.wmz» o:><img width=«21» height=«25» src=«dopb74661.zip» v:shapes="_x0000_i1107">−1. Таким образом, каждый раз перекладывая диск с одного колышка на другой, мы получаем все допустимые расположения n дисков на трех колышках (т.к. мы не перекладываем один диск с одного колышка на другой по несколько раз)
Задача 4. Имеются ли какие-нибудь начальная и конечная конфигурации из nдисков на трех колышках, которые требуют более чем <shape id="_x0000_i1108" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image141.wmz» o:><img width=«23» height=«24» src=«dopb74674.zip» v:shapes="_x0000_i1108">−1 перекладываний, чтобы получить одну из другой по исходным правилам Люка?
Решение. Докажем методом математической индукции, что любая начальная и конечная конфигурации из n дисков на трех колышках требуют не более чем <shape id="_x0000_i1109" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image141.wmz» o:><img width=«23» height=«24» src=«dopb74674.zip» v:shapes="_x0000_i1109">−1 перекладываний, чтобы получить одну из другой по исходным правилам Люка.
1) База: если n=1, то требуется одно перекладывание, тогда 1 ≤ 20−1 (верно);
2) Индуктивный переход: пусть для любой начальной и конечной конфигурации из n−1 дисков на трех колышках требуется не более чем <shape id="_x0000_i1110" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image143.wmz» o:><img width=«36» height=«24» src=«dopb74675.zip» v:shapes="_x0000_i1110">−1 перекладываний. Докажем для n дисков:
· если начальная и конечная конфигурации не предполагают перекладывание самого большого нижнего диска, тогда мы перекладываем только n−1 верхних дисков, а по индуктивному предположению для этого потребуется не более чем <shape id="_x0000_i1111" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image143.wmz» o:><img width=«36» height=«24» src=«dopb74675.zip» v:shapes="_x0000_i1111">−1 перекладываний;
· если начальная и конечная конфигурации предполагают перекладывание самого большого нижнего диска, тогда мы перекладываем n−1 верхних дисков, а по индуктивному предположению для этого будет достаточно <shape id="_x0000_i1112" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image143.wmz» o:><img width=«36» height=«24» src=«dopb74675.zip» v:shapes="_x0000_i1112">−1 перекладываний (т.е. n−1 верхних дисков разместили на одном колышке), затем перекладываем самый большой диск (одно перекладывание), и снова перекладываем n−1 верхних дисков, как требует конечная конфигурация (достаточно <shape id="_x0000_i1113" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image143.wmz» o:><img width=«36» height=«24» src=«dopb74675.zip» v:shapes="_x0000_i1113">−1 перекладываний). Таким образом, получили, что потребуется не более чем <shape id="_x0000_i1114" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image143.wmz» o:><img width=«36» height=«24» src=«dopb74675.zip» v:shapes="_x0000_i1114">−1 + 1+<shape id="_x0000_i1115" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image143.wmz» o:><img width=«36» height=«24» src=«dopb74675.zip» v:shapes="_x0000_i1115">−1=<shape id="_x0000_i1116" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image145.wmz» o:><img width=«48» height=«24» src=«dopb74676.zip» v:shapes="_x0000_i1116"> перекладываний.
Из всего этого следует, что не существует начальной и конечной конфигурации из n дисков на трех колышках требующей более чем <shape id="_x0000_i1117" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image141.wmz» o:><img width=«23» height=«24» src=«dopb74674.zip» v:shapes="_x0000_i1117">−1 перекладываний, чтобы получить одну из другой по исходным правилам Люка.
Задача 5. Так называемая «диаграмма Венна» с тремя пересекающимися окружностями часто приводится для иллюстрации восьми возможных подмножеств, связанных с тремя заданными множествами:
<img width=«106» height=«84» src=«dopb74677.zip» v:shapes="_x0000_s1153 _x0000_s1154 _x0000_s1155 _x0000_s1156 _x0000_s1157 _x0000_s1158 _x0000_s1159">Можно ли проиллюстрировать четырьмя пересекающимися окружностями шестнадцать возможностей, которые возникают в связи с четырьмя заданными множествами?
<img width=«151» height=«128» src=«dopb74678.zip» v:shapes="_x0000_s1160 _x0000_s1161 _x0000_s1162 _x0000_s1163 _x0000_s1164 _x0000_s1165 _x0000_s1166">Решение. Так как три пересекающиеся окружности иллюстрируют восемь различных подмножеств, то для того чтобы получить шестнадцать возможных подмножеств надо, чтобы четвертая окружность пересекала все восемь множеств. Но такого быть не может. Две произвольные окружности могут иметь не более двух точек пересечения, поэтому, проводя четвертую окружность, мы сможем получить максимум шесть дополнительных подмножеств. Так как возможно только два расположения четвертой окружности относительно трех данных окружностей: 1) четвертая окружность пересекает внешнее подмножество (рис. 1); 2) четвертая окружность лежит внутри трех пересекающихся окружностей (рис.2).
<img width=«126» height=«119» src=«dopb74679.zip» v:shapes="_x0000_s1167 _x0000_s1168 _x0000_s1169 _x0000_s1170 _x0000_s1171 _x0000_s1172 _x0000_s1173 _x0000_s1174">рис.1 рис.2
<img width=«64» height=«64» src=«dopb74680.zip» v:shapes="_x0000_s1175">
Если добавленная окружность пересекает внешнее множество, то она не сможет пересечь как минимум два внутренних множества (зависит от радиуса окружности).
Если добавленная окружность лежит внутри трех пересекающихся окружностей, то она не пересекает внешнее множество и как минимум одно внутреннее множество.
Таким образом, получили, что четырьмя окружностями можно проиллюстрировать максимум 14 (8+6=14) возможных подмножеств.
Задача 6. Некоторые из областей, очерчиваемых nпрямыми на плоскости, бесконечны, в то время как другие конечны. Какое максимально возможное число конечных областей?
Решение. Пусть <shape id="_x0000_i1118" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image151.wmz» o:><img width=«21» height=«25» src=«dopb74681.zip» v:shapes="_x0000_i1118"> - максимальное число возможных конечных областей, очерчиваемых n прямыми.
<img width=«37» height=«89» src=«dopb74682.zip» v:shapes="_x0000_s1176"><img width=«52» height=«79» src=«dopb74683.zip» v:shapes="_x0000_s1177"><img width=«49» height=«96» src=«dopb74684.zip» v:shapes="_x0000_s1178"><img width=«48» height=«88» src=«dopb74685.zip» v:shapes="_x0000_s1179">Рассмотрим частные случаи (при условии, что n-я прямая не параллельна никакой другой прямой (следовательно, она пересекает каждую из них), и не проходит ни через одну из имеющихся точек пересечения (следовательно, она пересекает каждую из прямых в различных местах)):
<img width=«154» height=«75» src=«dopb74686.zip» v:shapes="_x0000_s1190 _x0000_s1191 _x0000_s1180"> <img width=«86» height=«61» src=«dopb74687.zip» v:shapes="_x0000_s1182 _x0000_s1183 _x0000_s1184 _x0000_s1185"> <img width=«49» height=«55» src=«dopb74688.zip» v:shapes="_x0000_s1186 _x0000_s1187 _x0000_s1188"> <img width=«114» height=«53» src=«dopb74689.zip» v:shapes="_x0000_s1181 _x0000_s1192"> <img width=«59» height=«40» src=«dopb74690.zip» v:shapes="_x0000_s1189"> <img width=«414» height=«72» src=«dopb74691.zip» v:shapes="_x0000_s1195 _x0000_s1194 _x0000_s1193">
<img width=«119» height=«39» src=«dopb74693.zip» hspace=«12» alt=«Подпись: » v:shapes="_x0000_s1197">
<imagedata src=«15305.files/image170.wmz» o:><img width=«50» height=«25» src=«dopb74694.zip» hspace=«12» v:shapes="_x0000_s1198">
Обобщая, приходим к следующему выводу: новая n-я прямая (при n≥3) пересекает n–1 старых прямых в n−1 различных точках, следовательно, получаем n областей и две крайние из которых бесконечны. Таким образом, получили следующее рекуррентное соотношение:
<shape id="_x0000_i1119" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image172.wmz» o:><img width=«143» height=«55» src=«dopb74695.zip» v:shapes="_x0000_i1119">
Решим данное соотношение.
<shape id="_x0000_i1120" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image174.wmz» o:><img width=«583» height=«25» src=«dopb74696.zip» v:shapes="_x0000_i1120">
<shape id="_x0000_i1121" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image176.wmz» o:><img width=«551» height=«100» src=«dopb74697.zip» v:shapes="_x0000_i1121">
(Здесь Ln = <shape id="_x0000_i1122" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image026.wmz» o:><img width=«56» height=«41» src=«dopb74608.zip» v:shapes="_x0000_i1122"> + 1 — максимальное число областей, на которые плоскость делится n прямыми).
Докажем полученное равенство методом математической индукции по числу n:
1) База: n=0, <shape id="_x0000_i1123" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image178.wmz» o:><img width=«187» height=«25» src=«dopb74698.zip» v:shapes="_x0000_i1123"> (верно);
2) Индуктивный переход: пусть доказано для всех чисел t ≤ (n–1). Докажем для t=n: <shape id="_x0000_i1124" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image180.wmz» o:><img width=«139» height=«25» src=«dopb74699.zip» v:shapes="_x0000_i1124"><shape id="_x0000_i1125" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image029.wmz» o:><img width=«41» height=«36» src=«dopb74610.zip» v:shapes="_x0000_i1125"> <shape id="_x0000_i1126" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image182.wmz» o:><img width=«175» height=«25» src=«dopb74700.zip» v:shapes="_x0000_i1126"> = <shape id="_x0000_i1127" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image184.wmz» o:><img width=«64» height=«25» src=«dopb74701.zip» v:shapes="_x0000_i1127">=
=<shape id="_x0000_i1128" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image186.wmz» o:><img width=«547» height=«51» src=«dopb74702.zip» v:shapes="_x0000_i1128">
Из пунктов 1 и 2 следует: при n ≥ 0 <shape id="_x0000_i1129" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image188.wmz» o:><img width=«100» height=«25» src=«dopb74703.zip» v:shapes="_x0000_i1129">
Задача 7. Пусть H(n) = J(n+1)−J(n). В силу уравнения (7) (см. теорию) H(2n) = J(2n+1)− J(2n)<shape id="_x0000_i1130" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image190.wmz» o:><img width=«21» height=«36» src=«dopb74704.zip» v:shapes="_x0000_i1130">(2J(n)+1) − (2J(n)−1) = 2, aH(2n+1) = J(2n+2)− −J(2n+1) = (2J(n+1)−1)−(2J(n)+1) = 2H(n)−2 при всех n≥1. Поэтому представляется возможным доказать индукцией по n, что H(n)=2 при всех n. Что здесь не верно?
Решение. Ошибка заключается в том, что в данном рассуждении хотят доказать по индукции, что H(n)=2 при всех n (показали, что данное равенство выполняется для чисел вида 2n и 2n+1, т.к. любое натуральное число можно представить в таком виде), но при этом не проверили базу индукции (т.е. когда n принимает свое наименьшее значение: n = 1).
H(1) = J(2) − J(1) = 2J(1) −1 − J(1) = 2∙1−1−1 = 0 <shape id="_x0000_i1131" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image192.wmz» o:><img width=«23» height=«17» src=«dopb74650.zip» v:shapes="_x0000_i1131">H(1)<shape id="_x0000_i1132" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image193.wmz» o:><img width=«16» height=«16» src=«dopb74705.zip» v:shapes="_x0000_i1132">2<shape id="_x0000_i1133" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image195.wmz» o:><img width=«23» height=«17» src=«dopb74650.zip» v:shapes="_x0000_i1133"> база индукции не выполняется, следовательно равенство H(n)=2 верно не при всех n.
Задача 8. Решите рекуррентное соотношение
Q= α, Q1= β,
Qn= <shape id="_x0000_i1134" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image196.wmz» o:><img width=«65» height=«52» src=«dopb74706.zip» v:shapes="_x0000_i1134"> при n>1.
Примите, что Qn≠ 0 при всех n≥ 0.
Решение. <shape id="_x0000_i1135" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image198.wmz» o:><img width=«149» height=«52» src=«dopb74707.zip» v:shapes="_x0000_i1135">; <shape id="_x0000_i1136" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image200.wmz» o:><img width=«267» height=«73» src=«dopb74708.zip» v:shapes="_x0000_i1136">;
<shape id="_x0000_i1137" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image202.wmz» o:><img width=«436» height=«96» src=«dopb74709.zip» v:shapes="_x0000_i1137">;
<shape id="_x0000_i1138" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image204.wmz» o:><img width=«364» height=«100» src=«dopb74710.zip» v:shapes="_x0000_i1138">;
<shape id="_x0000_i1139" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image206.wmz» o:><img width=«124» height=«52» src=«dopb74711.zip» v:shapes="_x0000_i1139">; <shape id="_x0000_i1140" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image208.wmz» o:><img width=«151» height=«52» src=«dopb74712.zip» v:shapes="_x0000_i1140">;
<shape id="_x0000_i1141" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image210.wmz» o:><img width=«40» height=«25» src=«dopb74713.zip» v:shapes="_x0000_i1141"><shape id="_x0000_i1142" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image212.wmz» o:><img width=«223» height=«73» src=«dopb74714.zip» v:shapes="_x0000_i1142">; <shape id="_x0000_i1143" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image214.wmz» o:><img width=«260» height=«96» src=«dopb74715.zip» v:shapes="_x0000_i1143">.
Получили: <shape id="_x0000_i1144" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image216.wmz» o:><img width=«96» height=«25» src=«dopb74716.zip» v:shapes="_x0000_i1144">; <shape id="_x0000_i1145" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image218.wmz» o:><img width=«95» height=«25» src=«dopb74717.zip» v:shapes="_x0000_i1145">; <shape id="_x0000_i1146" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image220.wmz» o:><img width=«124» height=«48» src=«dopb74718.zip» v:shapes="_x0000_i1146">; <shape id="_x0000_i1147" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image222.wmz» o:><img width=«151» height=«51» src=«dopb74719.zip» v:shapes="_x0000_i1147">; <shape id="_x0000_i1148" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image224.wmz» o:><img width=«123» height=«51» src=«dopb74720.zip» v:shapes="_x0000_i1148">.
Обобщая, приходим к выводу, что данная последовательность периодическая: если n = 5k+r (<shape id="_x0000_i1149" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image226.wmz» o:><img width=«64» height=«24» src=«dopb74721.zip» v:shapes="_x0000_i1149">), тогда <shape id="_x0000_i1150" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image228.wmz» o:><img width=«137» height=«28» src=«dopb74722.zip» v:shapes="_x0000_i1150">(для n ≥ 5)
Докажем методом математической индукции:
1) База: n=5 <shape id="_x0000_i1151" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image133.wmz» o:><img width=«13» height=«25» src=«dopb74671.zip» v:shapes="_x0000_i1151"><shape id="_x0000_i1152" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image230.wmz» o:><img width=«128» height=«25» src=«dopb74723.zip» v:shapes="_x0000_i1152"> (верно, показано выше);
n=6 <shape id="_x0000_i1153" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image133.wmz» o:><img width=«13» height=«25» src=«dopb74671.zip» v:shapes="_x0000_i1153"><shape id="_x0000_i1154" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image232.wmz» o:><img width=«123» height=«25» src=«dopb74724.zip» v:shapes="_x0000_i1154"> (верно, показано выше);
n=7 <shape id="_x0000_i1155" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image133.wmz» o:><img width=«13» height=«25» src=«dopb74671.zip» v:shapes="_x0000_i1155"><shape id="_x0000_i1156" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image234.wmz» o:><img width=«128» height=«25» src=«dopb74725.zip» v:shapes="_x0000_i1156"> (верно, показано выше);
n=8 <shape id="_x0000_i1157" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image133.wmz» o:><img width=«13» height=«25» src=«dopb74671.zip» v:shapes="_x0000_i1157"><shape id="_x0000_i1158" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image236.wmz» o:><img width=«125» height=«25» src=«dopb74726.zip» v:shapes="_x0000_i1158"> (верно, показано выше);
n=9 <shape id="_x0000_i1159" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image133.wmz» o:><img width=«13» height=«25» src=«dopb74671.zip» v:shapes="_x0000_i1159"><shape id="_x0000_i1160" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image238.wmz» o:><img width=«127» height=«25» src=«dopb74727.zip» v:shapes="_x0000_i1160"> (верно, показано выше);
2) Индуктивный переход: пусть верно для всех чисел t ≤(n−1). Докажем для t=n: n = 5k + 0, тогда <shape id="_x0000_i1161" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image240.wmz» o:><img width=«339» height=«56» src=«dopb74728.zip» v:shapes="_x0000_i1161">;
· n = 5k + 1, тогда <shape id="_x0000_i1162" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image242.wmz» o:><img width=«335» height=«56» src=«dopb74729.zip» v:shapes="_x0000_i1162">;
· n = 5k + 2, тогда <shape id="_x0000_i1163" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image244.wmz» o:><img width=«299» height=«56» src=«dopb74730.zip» v:shapes="_x0000_i1163">;
· n = 5k + 3, тогда <shape id="_x0000_i1164" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image246.wmz» o:><img width=«299» height=«56» src=«dopb74731.zip» v:shapes="_x0000_i1164">;
· n = 5k + 4, тогда <shape id="_x0000_i1165" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image248.wmz» o:><img width=«300» height=«56» src=«dopb74732.zip» v:shapes="_x0000_i1165">.
Из пунктов 1 и 2 следует: для n ≥ 5 <shape id="_x0000_i1166" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image228.wmz» o:><img width=«137» height=«28» src=«dopb74722.zip» v:shapes="_x0000_i1166">.
Ответ: <shape id="_x0000_i1167" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image228.wmz» o:><img width=«137» height=«28» src=«dopb74722.zip» v:shapes="_x0000_i1167"> при всех n ≥ 0 и k, r <shape id="_x0000_i1168" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image250.wmz» o:><img width=«15» height=«15» src=«dopb74733.zip» v:shapes="_x0000_i1168">Z+.
Задача 9. Иногда возможно использование «обратной индукции», т.е. доказательства от nк n−1, а не наоборот. К примеру, рассмотрим утверждение
P(n): <shape id="_x0000_i1169" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image252.wmz» o:><img width=«100» height=«25» src=«dopb74734.zip» v:shapes="_x0000_i1169"> ≤ <shape id="_x0000_i1170" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image254.wmz» o:><img width=«148» height=«57» src=«dopb74735.zip» v:shapes="_x0000_i1170">, если x1,x2,…,xn≥ 0
продолжение
--PAGE_BREAK--Оно справедливо для n=2, так как <shape id="_x0000_i1171" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image256.wmz» o:><img width=«149» height=«68» src=«dopb74736.zip» v:shapes="_x0000_i1171">
(x1+x2)2 − 4x1x2= (x1−x2)2 ≥ 0.
a) Полагая <shape id="_x0000_i1172" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image258.wmz» o:><img width=«173» height=«48» src=«dopb74737.zip» v:shapes="_x0000_i1172">, докажите, что P(n) влечет P(n−1) при всяком n> 1.
b) Покажите, что P(n) и P(2) влекут P(2n).
c) Объясните, почему отсюда следует справедливость P(n) при всех n.
Решение. а) подставим <shape id="_x0000_i1173" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image260.wmz» o:><img width=«21» height=«25» src=«dopb74738.zip» v:shapes="_x0000_i1173"> в P(n):
P(n): <shape id="_x0000_i1174" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image262.wmz» o:><img width=«281» height=«52» src=«dopb74739.zip» v:shapes="_x0000_i1174">≤<shape id="_x0000_i1175" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image264.wmz» o:><img width=«285» height=«101» src=«dopb74740.zip» v:shapes="_x0000_i1175">
преобразуем правую скобку: <shape id="_x0000_i1176" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image266.wmz» o:><img width=«285» height=«101» src=«dopb74740.zip» v:shapes="_x0000_i1176">= <shape id="_x0000_i1177" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image267.wmz» o:><img width=«607» height=«60» src=«dopb74741.zip» v:shapes="_x0000_i1177">
получили: <shape id="_x0000_i1178" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image269.wmz» o:><img width=«281» height=«52» src=«dopb74739.zip» v:shapes="_x0000_i1178"> ≤ <shape id="_x0000_i1179" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image270.wmz» o:><img width=«167» height=«57» src=«dopb74742.zip» v:shapes="_x0000_i1179">
разделим левую и правую части неравенства на <shape id="_x0000_i1180" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image272.wmz» o:><img width=«167» height=«57» src=«dopb74743.zip» v:shapes="_x0000_i1180">(эта скобка не равна нулю, т.к. x1,x2,…,xn >0 и n > 1, т.к. случай всех хi=0 тривиальный, поэтому мы его не рассматриваем<shape id="_x0000_i1181" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image274.wmz» o:><img width=«99» height=«25» src=«dopb74744.zip» v:shapes="_x0000_i1181">)
получим P(n−1): <shape id="_x0000_i1182" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image276.wmz» o:><img width=«115» height=«25» src=«dopb74745.zip» v:shapes="_x0000_i1182"> ≤ <shape id="_x0000_i1183" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image278.wmz» o:><img width=«181» height=«57» src=«dopb74746.zip» v:shapes="_x0000_i1183">.
Следовательно, при <shape id="_x0000_i1184" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image258.wmz» o:><img width=«173» height=«48» src=«dopb74737.zip» v:shapes="_x0000_i1184"> P(n) влечет P(n−1) при всяком n>1.
b) запишем P(n) для двух конечных последовательностей чисел.
P(n): <shape id="_x0000_i1185" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image252.wmz» o:><img width=«100» height=«25» src=«dopb74734.zip» v:shapes="_x0000_i1185"> ≤ <shape id="_x0000_i1186" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image254.wmz» o:><img width=«148» height=«57» src=«dopb74735.zip» v:shapes="_x0000_i1186"> (для n первых членов)
<shape id="_x0000_i1187" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image280.wmz» o:><img width=«141» height=«25» src=«dopb74747.zip» v:shapes="_x0000_i1187"> ≤ <shape id="_x0000_i1188" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image282.wmz» o:><img width=«195» height=«57» src=«dopb74748.zip» v:shapes="_x0000_i1188"> (для n членов начиная с <shape id="_x0000_i1189" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image284.wmz» o:><img width=«36» height=«25» src=«dopb74749.zip» v:shapes="_x0000_i1189">)
перемножим эти два неравенства, используя свойство неравенств: если 0<a<b и 0<c<d, то ac<bd. Получим:
<shape id="_x0000_i1190" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image286.wmz» o:><img width=«204» height=«25» src=«dopb74750.zip» v:shapes="_x0000_i1190"> ≤ <shape id="_x0000_i1191" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image288.wmz» o:><img width=«363» height=«60» src=«dopb74751.zip» v:shapes="_x0000_i1191">.
Преобразуем правую скобку неравенства, используя утверждение Р(2)
P(2): <shape id="_x0000_i1192" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image256.wmz» o:><img width=«149» height=«68» src=«dopb74736.zip» v:shapes="_x0000_i1192">
<shape id="_x0000_i1193" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image290.wmz» o:><img width=«508» height=«101» src=«dopb74752.zip» v:shapes="_x0000_i1193">,
возведем левую и правую части неравенства в n-ую степень, получим
<shape id="_x0000_i1194" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image292.wmz» o:><img width=«272» height=«60» src=«dopb74753.zip» v:shapes="_x0000_i1194">≤ <shape id="_x0000_i1195" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image294.wmz» o:><img width=«287» height=«57» src=«dopb74754.zip» v:shapes="_x0000_i1195">
Таким образом, получили:
P(2n): <shape id="_x0000_i1196" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image286.wmz» o:><img width=«204» height=«25» src=«dopb74750.zip» v:shapes="_x0000_i1196"> ≤ <shape id="_x0000_i1197" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image294.wmz» o:><img width=«287» height=«57» src=«dopb74754.zip» v:shapes="_x0000_i1197">.
Следовательно, P(n) и P(2) влекут P(2n).
c) Выше было показано, что из P(n) следует P(n−1), а из P(n) и P(2) следует P(2n). Следовательно, мы можем утверждать, что P(n) выполняется для любого n > 1, т.к. P(от нечетного числа n) следует из P(от четного числа (n−1)), а P(от четного числа) следует из P(2) и P(от четного или нечетного числа) и т.д., в конечном итоге приходим к P(2), а оно выполняется.
Например, P(9) следует из P(8), а P(8) следует из P(2) и P(4), P(4) следует из P(2) и P(2), а P(2) выполняется.
Задача 10. Пусть Qn— минимальное число перекладываний, необходимых для перемещения башни из nдисков с колышка А на колышек B, если все перекладывания осуществляются по часовой стрелке – т.е. с А на B, или с Bна другой колышек, и с другого колышка на А. Кроме того, пусть Rn– минимальное число перекладываний, необходимых для перемещения башни с В обратно на А при том же ограничении. Докажите, что
<shape id="_x0000_i1198" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image296.wmz» o:><img width=«125» height=«57» src=«dopb74755.zip» v:shapes="_x0000_i1198"><shape id="_x0000_i1199" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image133.wmz» o:><img width=«13» height=«25» src=«dopb74671.zip» v:shapes="_x0000_i1199">
<shape id="_x0000_i1200" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image298.wmz» o:><img width=«155» height=«57» src=«dopb74756.zip» v:shapes="_x0000_i1200">
<img width=«298» height=«93» src=«dopb74757.zip» v:shapes="_x0000_s1207 _x0000_s1208 _x0000_s1209 _x0000_s1210 _x0000_s1211 _x0000_s1212 _x0000_s1213 _x0000_s1214 _x0000_s1215 _x0000_s1216 _x0000_s1217 _x0000_s1218 _x0000_s1219 _x0000_s1220 _x0000_s1221 _x0000_s1222 _x0000_s1223">Решение.
Рассмотрим частные случаи: Q0=0, R0=0; Q1=1, R1=2; Q2=5, R2=7; Q3=15= =R2+1+R2, R3=21= Q3+1+Q2.
Эксперимент с тремя дисками дает ключ к общему правилу перемещения n дисков c колышка А на колышек B по часовой стрелке: сначала мы перемещаем (n−1) меньших дисков с колышка А на C, через колышек B (для этого потребуется <shape id="_x0000_i1201" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image301.wmz» o:><img width=«37» height=«25» src=«dopb74758.zip» v:shapes="_x0000_i1201"> перекладываний, т.к. это тоже самое если бы мы перекладывали диски с колышка B на колышек А через колышек С), затем перекладываем самый большой диск c колышка A на колышек B (одно перекладывание), потом помещаем (n−1) меньших дисков с колышка C на B (что требует <shape id="_x0000_i1202" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image301.wmz» o:><img width=«37» height=«25» src=«dopb74758.zip» v:shapes="_x0000_i1202"> перекладываний, по тем же соображениям). Таким образом, n дисков (при n>0) c колышка A на колышек B можно переместить за <shape id="_x0000_i1203" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image303.wmz» o:><img width=«112» height=«25» src=«dopb74759.zip» v:shapes="_x0000_i1203"> перекладываний. Получили соотношение:
<shape id="_x0000_i1204" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image296.wmz» o:><img width=«125» height=«57» src=«dopb74755.zip» v:shapes="_x0000_i1204">
Эксперимент с тремя дисками дает ключ и к общему правилу перемещения n дисков c колышка B на колышек A по часовой стрелке: сначала мы перемещаем (n−1) меньших дисков с колышка B на А (что требует Rn-1 перекладываний), затем перекладываем самый большой диск c колышка B на колышек С (одно перекладывание), потом помещаем (n−1) меньших дисков с колышка А на B (что требует Qn-1 перекладываний), затем перекладываем самый большой диск c колышек С на колышек А (одно перекладывание), и, наконец, помещаем (n−1) меньших дисков с колышка B на колышек А (еще Rn-1 перекладываний). Таким образом, n дисков (при n>0) c колышка B на колышек А можно переместить за <shape id="_x0000_i1205" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image305.wmz» o:><img width=«368» height=«25» src=«dopb74760.zip» v:shapes="_x0000_i1205"> перекладываний. Получили соотношение: <shape id="_x0000_i1206" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image307.wmz» o:><img width=«167» height=«55» src=«dopb74761.zip» v:shapes="_x0000_i1206">
И если мы вместо <shape id="_x0000_i1207" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image309.wmz» o:><img width=«47» height=«25» src=«dopb74762.zip» v:shapes="_x0000_i1207"> подставим <shape id="_x0000_i1208" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image311.wmz» o:><img width=«49» height=«25» src=«dopb74763.zip» v:shapes="_x0000_i1208"> (т.к. <shape id="_x0000_i1209" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image313.wmz» o:><img width=«112» height=«25» src=«dopb74759.zip» v:shapes="_x0000_i1209">, показали выше), то получим нужную нам систему: <shape id="_x0000_i1210" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image298.wmz» o:><img width=«155» height=«57» src=«dopb74756.zip» v:shapes="_x0000_i1210">
Таким образом, получили, что системы (1) и (2) справедливы.
Задача 11. Двойная ханойская башня состоит из 2nдисков nразличных размеров – по два диска каждого размера. Как и в случае обычной башни, за один раз разрешается перекладывать только один диск и нельзя класть больший диск на меньший.
a) Сколько перекладываний необходимо для перемещения двойной башни с одного колышка на другой, если диски одинаковых размеров неотличимы друг от друга?
b) Что если в окончательном расположении дисков требуется воспроизвести исходный порядок всех одинаковых дисков сверху донизу?
Решение. a) Пусть <shape id="_x0000_i1211" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image314.wmz» o:><img width=«28» height=«25» src=«dopb74764.zip» v:shapes="_x0000_i1211"> - минимальное число перекладываний башни 2n дисков с одного колышка на другой. Рассмотрим частные случаи: P0=0, P2=2, P4=6, P6=14. Эксперимент с шестью дисками дает ключ к общему правилу перемещения 2n дисков: сначала переместить (2n−2) меньших дисков с одного колышка на другой (что требует <shape id="_x0000_i1212" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image316.wmz» o:><img width=«44» height=«25» src=«dopb74765.zip» v:shapes="_x0000_i1212">перекладываний), затем перекладываем 2 самых больших диска (одно перекладывание), потом помещаем (2n−2) меньших дисков на большие диски (что требует <shape id="_x0000_i1213" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image318.wmz» o:><img width=«44» height=«25» src=«dopb74765.zip» v:shapes="_x0000_i1213"> перекладываний). Таким образом, 2n дисков (при n>0) можно переместить за <shape id="_x0000_i1214" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image319.wmz» o:><img width=«83» height=«25» src=«dopb74766.zip» v:shapes="_x0000_i1214"> перекладываний.
Получили рекуррентное соотношение:
<shape id="_x0000_i1215" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image321.wmz» o:><img width=«127» height=«55» src=«dopb74767.zip» v:shapes="_x0000_i1215">
Решим данное соотношение. P0 =0=<shape id="_x0000_i1216" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image323.wmz» o:><img width=«41» height=«25» src=«dopb74768.zip» v:shapes="_x0000_i1216">, P2 =2=<shape id="_x0000_i1217" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image325.wmz» o:><img width=«39» height=«25» src=«dopb74769.zip» v:shapes="_x0000_i1217">, P4 =6 = <shape id="_x0000_i1218" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image327.wmz» o:><img width=«41» height=«25» src=«dopb74770.zip» v:shapes="_x0000_i1218">, P6== 14=<shape id="_x0000_i1219" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image329.wmz» o:><img width=«40» height=«25» src=«dopb74771.zip» v:shapes="_x0000_i1219"> (Здесь Tn = 2n−1 — минимальное число перекладываний, необходимых для перемещения n дисков с одного колышка на другой по правилам Люка) <shape id="_x0000_i1220" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image331.wmz» o:><img width=«23» height=«17» src=«dopb74650.zip» v:shapes="_x0000_i1220"> гипотеза: <shape id="_x0000_i1221" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image332.wmz» o:><img width=«245» height=«29» src=«dopb74772.zip» v:shapes="_x0000_i1221"> при n ≥ 0
Докажем методом математической индукции по числу n, что <shape id="_x0000_i1222" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image334.wmz» o:><img width=«108» height=«29» src=«dopb74773.zip» v:shapes="_x0000_i1222"> при n ≥ 0.
1) База: n=1 <shape id="_x0000_i1223" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image133.wmz» o:><img width=«13» height=«25» src=«dopb74671.zip» v:shapes="_x0000_i1223"><shape id="_x0000_i1224" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image336.wmz» o:><img width=«115» height=«29» src=«dopb74774.zip» v:shapes="_x0000_i1224"> (верно);
2) Индуктивный переход: пусть верно для всех чисел t ≤(2n−2). Докажем для 2n дисков: <shape id="_x0000_i1225" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image338.wmz» o:><img width=«345» height=«40» src=«dopb74775.zip» v:shapes="_x0000_i1225">
Из пунктов 1 и 2 следует, что <shape id="_x0000_i1226" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image334.wmz» o:><img width=«108» height=«29» src=«dopb74773.zip» v:shapes="_x0000_i1226"> при n ≥ 0.
b) Пусть <shape id="_x0000_i1227" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image340.wmz» o:><img width=«31» height=«25» src=«dopb74776.zip» v:shapes="_x0000_i1227"> — минимальное число перекладываний башни из 2n дисков с одного колышка на другой в исходном порядке всех одинаковых дисков сверху донизу.
Рассмотрим частные случаи: R0=0, R2=3, R4=11. Эксперимент с четырьмя дисками дает ключ к общему правилу перемещения 2n дисков в исходном порядке: сначала переместить (2n−2) меньших дисков с одного колышка на другой (что требует <shape id="_x0000_i1228" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image316.wmz» o:><img width=«44» height=«25» src=«dopb74765.zip» v:shapes="_x0000_i1228">перекладываний), затем перекладываем два самых больших диска на свободный колышек (два перекладывания; эти диски будут положены неправильно), потом перекладываем (2n−2) меньших дисков на свободный колышек (что требует <shape id="_x0000_i1229" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image318.wmz» o:><img width=«44» height=«25» src=«dopb74765.zip» v:shapes="_x0000_i1229"> перекладываний), затем снова перекладываем два самых больших диска (два перекладывания; эти диски будут положены правильно), и, наконец, перекладываем (2n−2) меньших дисков на большие диски в исходном порядке (потребуется <shape id="_x0000_i1230" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image342.wmz» o:><img width=«47» height=«25» src=«dopb74777.zip» v:shapes="_x0000_i1230"> перекладываний). Таким образом, 2n дисков (при n>0) можно переместить с одного колышка на другой в исходном порядке всех одинаковых дисков сверху донизу за <shape id="_x0000_i1231" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image344.wmz» o:><img width=«144» height=«25» src=«dopb74778.zip» v:shapes="_x0000_i1231"> перекладываний.
Получили рекуррентное соотношение:
<shape id="_x0000_i1232" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image346.wmz» o:><img width=«189» height=«55» src=«dopb74779.zip» v:shapes="_x0000_i1232"> (*)
Решим данное соотношение. R2 = 3 = 2P2−1, R4 = 11 = 2P4−1, R6 = 27 = 2P6−1 <shape id="_x0000_i1233" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image348.wmz» o:><img width=«23» height=«17» src=«dopb74650.zip» v:shapes="_x0000_i1233">гипотеза: <shape id="_x0000_i1234" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image349.wmz» o:><img width=«320» height=«29» src=«dopb74780.zip» v:shapes="_x0000_i1234"> при n > 0.
Докажем методом математической индукции по числу n, что <shape id="_x0000_i1235" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image351.wmz» o:><img width=«112» height=«29» src=«dopb74781.zip» v:shapes="_x0000_i1235"> при n > 0.
1) База: n=1 <shape id="_x0000_i1236" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image133.wmz» o:><img width=«13» height=«25» src=«dopb74671.zip» v:shapes="_x0000_i1236"><shape id="_x0000_i1237" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image353.wmz» o:><img width=«113» height=«29» src=«dopb74782.zip» v:shapes="_x0000_i1237"> (верно);
2) Индуктивный переход: пусть верно для всех чисел t ≤(2n−2). Докажем для 2n дисков: <shape id="_x0000_i1238" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image355.wmz» o:><img width=«487» height=«40» src=«dopb74783.zip» v:shapes="_x0000_i1238">
Из пунктов 1 и 2 следует, что <shape id="_x0000_i1239" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image357.wmz» o:><img width=«112» height=«29» src=«dopb74781.zip» v:shapes="_x0000_i1239"> при n > 0.
Еще можно заметить следующее: т.к. <shape id="_x0000_i1240" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image358.wmz» o:><img width=«119» height=«25» src=«dopb74784.zip» v:shapes="_x0000_i1240">, следовательно <shape id="_x0000_i1241" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image360.wmz» o:><img width=«151» height=«25» src=«dopb74785.zip» v:shapes="_x0000_i1241">, то, подставляя данное равенство в соотношение (*) получим рекуррентное соотношение: <shape id="_x0000_i1242" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image362.wmz» o:><img width=«132» height=«55» src=«dopb74786.zip» v:shapes="_x0000_i1242">
имеющее то же самое решение <shape id="_x0000_i1243" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image133.wmz» o:><img width=«13» height=«25» src=«dopb74671.zip» v:shapes="_x0000_i1243"><shape id="_x0000_i1244" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image364.wmz» o:><img width=«227» height=«29» src=«dopb74787.zip» v:shapes="_x0000_i1244">
Задача 12. Давайте еще обобщим задачу 11а, предполагая, что имеется nразличных размеров дисков и ровно mkдисков размера k. Определите наименьшее число A(m1, m2, …,mn) перекладываний дисков, необходимых для перемещения такой башни, если считать диски одинаковых размеров неразличимыми.
Решение. Для того, что переложить башню, состоящую из n различных размеров дисков, среди которых ровно mk дисков размера k, потребуется следующее число перекладываний:
<shape id="_x0000_i1245" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image366.wmz» o:><img width=«357» height=«52» src=«dopb74788.zip» v:shapes="_x0000_i1245">
где mn – это количество самых больших нижних дисков.
Решим данное рекуррентное соотношение.
A(m1)=2A(0)+m1=m1;
A(m1,m2)=2A(m1)+m2=21∙m1+m2;
A(m1,m2,m3)=2A(m1,m2)+m3=22∙m1+21∙m2+m3;
A(m1,m2,m3,m4)=2A(m1,m2,m3)+m4=23∙m1+22∙m2+21∙m3+m4.
Отсюда можно выдвинуть гипотезу, что
A(m1,m2,…,mn)=<shape id="_x0000_i1246" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image368.wmz» o:><img width=«288» height=«29» src=«dopb74789.zip» v:shapes="_x0000_i1246">
Докажем методом математической индукции по числу n.
1) База: n=1 A(m1)=20∙m1=m1 (верно);
2) Индуктивный переход: пусть верно для всех чисел t ≤(n−1). Докажем для t=n: <shape id="_x0000_i1247" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image370.wmz» o:><img width=«357» height=«25» src=«dopb74790.zip» v:shapes="_x0000_i1247"><shape id="_x0000_i1248" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image372.wmz» o:><img width=«44» height=«35» src=«dopb74648.zip» v:shapes="_x0000_i1248"> =2∙(<shape id="_x0000_i1249" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image373.wmz» o:><img width=«307» height=«29» src=«dopb74791.zip» v:shapes="_x0000_i1249">)<shape id="_x0000_i1250" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image375.wmz» o:><img width=«56» height=«25» src=«dopb74792.zip» v:shapes="_x0000_i1250">
=<shape id="_x0000_i1251" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image368.wmz» o:><img width=«288» height=«29» src=«dopb74789.zip» v:shapes="_x0000_i1251">
Из 1 и 2 следует, что A(m1,m2,…,mn)=<shape id="_x0000_i1252" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image368.wmz» o:><img width=«288» height=«29» src=«dopb74789.zip» v:shapes="_x0000_i1252">
при n > 0.
Задача 13. На какое максимально возможное число областей плоскость делится nзигзагообразными линиями, каждая из которых состоит из двух параллельных полубесконечных прямых, соединенных прямолинейным отрезком?
<img width=«359» height=«85» src=«dopb74793.zip» v:shapes="_x0000_s1233 _x0000_s1234 _x0000_s1235 _x0000_s1236 _x0000_s1237 _x0000_s1238 _x0000_s1239">Решение. Пусть <shape id="_x0000_i1253" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image378.wmz» o:><img width=«27» height=«25» src=«dopb74794.zip» v:shapes="_x0000_i1253"> — это максимальное число областей, на которые плоскость делится n зигзагообразными линиями. Рассмотрим частные случаи: <shape id="_x0000_i1254" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image380.wmz» o:><img width=«52» height=«25» src=«dopb74795.zip» v:shapes="_x0000_i1254">
<img width=«142» height=«36» src=«dopb74796.zip» v:shapes="_x0000_s1240 _x0000_s1241 _x0000_s1242 _x0000_s1243">
<shape id="_x0000_i1255" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image383.wmz» o:><img width=«116» height=«25» src=«dopb74797.zip» v:shapes="_x0000_i1255"> <shape id="_x0000_i1256" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image385.wmz» o:><img width=«145» height=«25» src=«dopb74798.zip» v:shapes="_x0000_i1256">
(Здесь Ln = <shape id="_x0000_i1257" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image026.wmz» o:><img width=«56» height=«41» src=«dopb74608.zip» v:shapes="_x0000_i1257"> + 1- максимальное число областей, на которые плоскость делится n прямыми)
<img width=«232» height=«102» src=«dopb74799.zip» v:shapes="_x0000_s1244 _x0000_s1245 _x0000_s1246 _x0000_s1247 _x0000_s1248 _x0000_s1249 _x0000_s1250 _x0000_s1251 _x0000_s1252 _x0000_s1253 _x0000_s1254 _x0000_s1255 _x0000_s1256 _x0000_s1257">Из этих частных случаев можно видеть, что зигзагообразная линия подобна трем прямым с тем лишь отличием, что области сливаются, если «три» прямые не продолжать после их пересечения:
Области 1, 2, 6 и 3, 4, 5, которые были бы разделены при наличии трех прямых, превращаются в единую область в случае одной зигзагообразной линии, т.е. мы теряем четыре области. Так же у нас имеется две параллельные прямые, следовательно, мы теряем еще одну область. Таким образом, если привести все в надлежащий порядок, то все зигзагообразные линии должны пересекаться между собой и точки изломов должны лежать «по ту сторону» пересечений с другими линиями, и мы теряем только пять областей на одну линию. Таким образом,
<shape id="_x0000_i1258" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image388.wmz» o:><img width=«523» height=«51» src=«dopb74800.zip» v:shapes="_x0000_i1258">.
Данную задачу можно решить и по другому, если заметить, что зигзаг можно рассматривать как «прямую», и отрезок, соединяющий две полупрямые, может быть сколь угодно длинным. Тогда данная задача аналогична задаче о нахождении максимального числа Ln областей, на которые плоскость делится n прямыми (две прямые имеют одну точку пересечения). В нашем случае две зигзагообразные линии имеют девять точек пересечения.
<img width=«359» height=«122» src=«dopb74801.zip» v:shapes="_x0000_s1258 _x0000_s1259 _x0000_s1260 _x0000_s1261 _x0000_s1262 _x0000_s1263 _x0000_s1264 _x0000_s1265 _x0000_s1266 _x0000_s1267 _x0000_s1268 _x0000_s1269 _x0000_s1270 _x0000_s1271"><img width=«113» height=«70» src=«dopb74802.zip» v:shapes="_x0000_s1272">С другой стороны, две зигзагообразные линии подобны шести прямым с тем лишь отличием, что области сливаются, если «шесть» прямых не продолжать после их пересечения,
Эти шесть прямых образуют 20 областей, следовательно, при пересечении двух зигзагообразных линий мы теряем восемь областей.
Таким образом, получаем рекуррентное соотношение:
<shape id="_x0000_i1259" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image392.wmz» o:><img width=«145» height=«55» src=«dopb74803.zip» v:shapes="_x0000_i1259">
Решим данное соотношение. <shape id="_x0000_i1260" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image394.wmz» o:><img width=«299» height=«25» src=«dopb74804.zip» v:shapes="_x0000_i1260">+9n−
−8=<shape id="_x0000_i1261" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image396.wmz» o:><img width=«535» height=«25» src=«dopb74805.zip» v:shapes="_x0000_i1261">
+9∙(n−1)−8+9n−8=<shape id="_x0000_i1262" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image398.wmz» o:><img width=«396» height=«47» src=«dopb74806.zip» v:shapes="_x0000_i1262">
=<shape id="_x0000_i1263" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image400.wmz» o:><img width=«97» height=«51» src=«dopb74807.zip» v:shapes="_x0000_i1263"> <shape id="_x0000_i1264" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image402.wmz» o:><img width=«161» height=«51» src=«dopb74808.zip» v:shapes="_x0000_i1264"> при n ≥ 0.
Докажем полученное равенство методом математической индукции.
1) База: n=0, <shape id="_x0000_i1265" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image404.wmz» o:><img width=«181» height=«51» src=«dopb74809.zip» v:shapes="_x0000_i1265"> (верно);
2) Индуктивный переход: пусть верно для всех чисел t ≤ (n–1). Докажем для t=n: <shape id="_x0000_i1266" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image406.wmz» o:><img width=«144» height=«25» src=«dopb74810.zip» v:shapes="_x0000_i1266"><shape id="_x0000_i1267" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image029.wmz» o:><img width=«41» height=«36» src=«dopb74610.zip» v:shapes="_x0000_i1267"> <shape id="_x0000_i1268" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image408.wmz» o:><img width=«229» height=«51» src=«dopb74811.zip» v:shapes="_x0000_i1268"> = <shape id="_x0000_i1269" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image410.wmz» o:><img width=«167» height=«51» src=«dopb74812.zip» v:shapes="_x0000_i1269">+9n−7=<shape id="_x0000_i1270" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image400.wmz» o:><img width=«97» height=«51» src=«dopb74807.zip» v:shapes="_x0000_i1270">.
Из пунктов 1 и 2 следует: при n > 0 <shape id="_x0000_i1271" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image412.wmz» o:><img width=«140» height=«51» src=«dopb74813.zip» v:shapes="_x0000_i1271">.
Задача 14. На какое максимальное число частей можно разделить головку сыра с помощью пяти плоских разрезов? (Головка сыра должна оставаться в исходном положении, пока вы ее режете, и каждому разрезу должна соответствовать некоторая плоскость в трехмерном пространстве.) Найдите рекуррентное соотношение для Рn— максимального числа трехмерных областей, на которое может быть разбито пространство nпроизвольно расположенными плоскостями.
Решение. Сначала найдем рекуррентное соотношение для Рn, а потом с помощью этого соотношения определим, на сколько частей можно разделить головку сыра с помощью пяти плоских разрезов (головка сыра является ограниченным пространством).
Итак, рассмотрим частные случаи: Р1=2, Р2=4, Р3=4+4=8, Р4=8+7=15. Эксперимент показывает, что данная задача аналогична задаче о нахождении максимального числа Ln областей, на которые плоскость делится n прямыми (Ln=Ln-1+n), но только с тем отличием, что дело обстоит в пространстве. Две произвольные плоскости пересекаются по единственной прямой, и для того, чтобы получить максимальное число трехмерных областей надо, чтобы каждая новая проведенная плоскость не была параллельна никакой другой плоскости (следовательно, она пересекает каждую из них), и не проходила ни через одну из имеющихся прямых пересечения (следовательно, она пересекает каждую из плоскостей по различным прямым). Таким образом, проводя новую n-ую плоскость, мы к старым <shape id="_x0000_i1272" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image414.wmz» o:><img width=«35» height=«25» src=«dopb74814.zip» v:shapes="_x0000_i1272"> областям добавляем столько трехмерных областей, сколько образуется областей на n-ой плоскости образованных <shape id="_x0000_i1273" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image416.wmz» o:><img width=«37» height=«20» src=«dopb74815.zip» v:shapes="_x0000_i1273"> прямой пересечения этой плоскости со всеми остальными плоскостями. Поэтому рекуррентное соотношение имеет вид:
<shape id="_x0000_i1274" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image418.wmz» o:><img width=«124» height=«55» src=«dopb74816.zip» v:shapes="_x0000_i1274">
<shape id="_x0000_i1275" type="#_x0000_t75" o:ole=""><imagedata src=«15305.files/image420.wmz» o:><img width=«237» height=«47» src=«dopb74817.zip» v:shapes="_x0000_i1275">
Следовательно, головку сыра можно разделить с помощью пяти плоских разрезов не более чем на 26 частей.
Задача 15. У Иосифа был друг, которого он спас, поставив на предпоследнее спасительное место. Чему равен F(n) — номер предпоследнего выжившего, если экзекуции подлежит каждый второй?
Решение. Допустим, что первоначально имеется 2n людей. После первого обхода мы остаемся с номерами: 1, 3, 5, 7, …, 2n−3, 2n−1. Следующий обход будет начинаться с номера 3. Это то же самое, если бы мы начинали с n людей, за исключением того, что номер каждого уцелевшего удваивается и уменьшается на 1. Тем самым
F(2n) = 2∙F(n) − 1 при n > 1
Теперь посмотрим, что будет в случае, когда имеется 2n+1 людей. После первого обхода жертва с номером 1 уничтожается сразу после жертвы с номером 2n, и мы остаемся с номерами: 3, 5, 7, …, 2n−1,2n+1. Получили почти первоначальную ситуацию с n людьми, но на этот раз номера уцелевших удваиваются и увеличиваются на 1. Таким образом,
F(2n+1) = 2∙F(n) + 1 при n > 1
Объединение полученных равенств дает рекуррентное соотношение, которое определяет F(n) для n>3, т.к. F(1) не определено:
продолжение
--PAGE_BREAK--
еще рефераты
Еще работы по математике
Реферат по математике
Строение конечной группы 24-го порядка, заданной образующими и определяющими соотношениями G
20 Июня 2015
Реферат по математике
Дискретная математика 3
20 Июня 2015
Реферат по математике
Теория Графов в химии и нерешённые задачи
20 Июня 2015
Реферат по математике
Пузыри. Условия существования. Пузырится ли российский фондовый рынок
2 Сентября 2013