Книги по разным темам Pages:     | 1 |   ...   | 3 | 4 | 5 | 6 | 7 |   ...   | 30 |

3.96. Дружественные числа. Докажите, что если все три числа p = 3 2k-1 - 1, q = 3 2k - 1 и r = 9 22k-1 - 1 Ч простые, то числа m = 2k p q и n = 2k r Ч дружественные. Постройте примеры дружественных чисел.

3.97. Может ли быть так, что а) (n) > 3n; б)* (n) > 100n 3.98. Задача Ферма. Найдите наименьшее число вида n = 2p1p2, где p1 и p2 Ч некоторые простые числа, такое, что (n) = 3n.

36 3. Алгоритм Евклида и основная теорема арифметики 3.99. Пусть Ч действительное положительное число, d Ч натуральное. Докажите, что количество натуральных чисел, не превосходящих и делящихся на d, равно.

d 3.100. Докажите, что для действительного положительного и на [] турального d всегда выполнено равенство =.

d d 3.101. Формула Лежандра. Число n! разложено в произведение s простых чисел n! = p... p. Докажите равенство 1 s n n n k = + + +...

pk p2 pk k 3.102. Докажите, что число p входит в разложение n! с показателем, n не превосходящим.

p - 3.103. Пусть представление числа n в двоичной системе выглядит следующим образом:

1 2 r n = 2e + 2e +... + 2e (e1 > e2 >... > er 0).

Докажите, что n! делится на 2n-r, но не делится на 2n-r+1.

3.104. Результат предыдущей задачи допускает обобщение. Пусть p Ч простое число и представление числа n в p-ичной системе имеет вид:

n = akpk + ak-1pk-1 +... + a1p1 + a0.

Найдите формулу, выражающую показатель p, с которым это число p входит в каноническое разложение n!, через n, p и коэффициенты ak.

3.105. При помощи формулы Лежандра из задачи 3.101 докажите, что число Cn (n 0) всегда целое. (См. также 2.115.) 2n n + (2m)! (2n)! 3.106. Докажите, что число (m, n 0) всегда целое.

m! n! (m + n)! n! 3.107. Существует ли такое целое r, что число является целым 2n-r при любом n 1 4. О том, как размножаются кролики Определение. Последовательность чисел Фибоначчи {F0, F1, F2,... } = {0, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610,... } задается условиями F0 = 0, F1 = 1, Fn+2 = Fn+1 + Fn (n 0).

4. О том, как размножаются кролики Эти числа были впервые описаны в Книге абака (1202 г.) итальянского математика Леонардо Пизанского (Фибоначчи).

3.108. Задача Леонардо Пизанского. Некто приобрел пару кроликов и поместил их в огороженный со всех сторон загон. Сколько кроликов будет через год, если считать, что каждый месяц пара дает в качестве приплода новую пару кроликов, которые со второго месяца жизни также начинают приносить приплод 3.109. О том, как прыгают кузнечики. Предположим, что имеется лента, разбитая на клетки и уходящая вправо до бесконечности. На первой клетке этой ленты сидит кузнечик. Из любой клетки кузнечик может перепрыгнуть либо на одну, либо на две клетки вправо. Сколькими способами кузнечик может добраться до n-й от начала ленты клетки (См. также 3.114.) 3.110. Некоторый алфавит состоит из 6 букв, которые для передачи по телеграфу кодированы так:

- - - - - - - - - - - - - При передаче одного слова не сделали промежутков, отделяющих букву от буквы, так что получилась сплошная цепочка из точек и тире, содержащая 12 знаков. Сколькими способами можно прочитать переданное слово 3.111. Чему равны числа Фибоначчи с отрицательными номерами F-1, F-2,..., F-n,... 3.112. Тождество Кассини. Докажите равенство Fn+1Fn-1 - F2 = (-1)n (n > 0).

n Будет ли тождество Кассини справедливо для всех целых n (См.

также 12.13.) 3.113. Докажите следующие свойства чисел Фибоначчи:

а) F1 + F2 +... + Fn = Fn+2 - 1; в) F2 + F4 +... + F2n = F2n+1 - 1;

б) F1 + F3 +... + F2n-1 = F2n; г) F2 + F2 +... + F2 = FnFn+1.

1 2 n 3.114. Докажите, что при n 1 и m 0 выполняется равенство Fn+m = Fn-1Fm + FnFm+1.

Попробуйте доказать его двумя способами: при помощи метода математической индукции и при помощи интерпретации чисел Фибоначчи из задачи 3.109. Докажите также, что тождество Кассини является частным случаем этого равенства.

38 3. Алгоритм Евклида и основная теорема арифметики 3.115. Докажите равенства а) F2n+1 = F2 + F2 ;

n n+б) Fn+1Fn+2 - FnFn+3 = (-1)n+1;

в) F3n = F3 + F3 - F3.

n n+1 n-3.116. Вычислите F4 - FnFn+1Fn+3Fn+4.

n+3.117. Вычислите сумму 1 2 Fn + +... +.

1 2 1 3 Fn-1 Fn+3.118. Делимость чисел Фибоначчи. Докажите справедливость следующих утверждений:

а) 2 | Fn 3 | n; в) 4 | Fn 6 | n;

б) 3 | Fn 4 | n; г) Fm | Fn m | n.

3.119. Докажите, что для любого натурального m существует число Фибоначчи Fn (n 1), кратное m.

3.120. Пусть первое число Фибоначчи, делящееся на m есть Fk.

Докажите, что m | Fn тогда и только тогда, когда k | n.

3.121. Докажите, что два соседних числа Фибоначчи Fn-1 и Fn (n 1) всегда взаимно просты.

3.122*. Теорема Люка. Докажите равенство (Fn, Fm) = F(m,n).

(См. также 3.141.) 3.123. В последовательности чисел Фибоначчи выбрано 8 чисел, идущих подряд. Докажите, что их сумма не является числом Фибоначчи.

3.124. Рассмотрим множество последовательностей длины n, состоящих из 0 и 1, в которых не бывает двух 1 стоящих рядом. Докажите, что количество таких последовательностей равно Fn+2. Найдите взаимно однозначное соответствие между такими последовательностями и маршрутами кузнечика из задачи 3.109.

3.125. Фибоначчиева система счисления. Докажите, что произвольное натуральное число n, не превосходящее Fm, единственным образом можно представить в виде m n = bkFk, k=где все числа b2,..., bm равны 0 либо 1, причем среди этих чисел нет двух единиц стоящих рядом, то есть bkbk+1 = 0 (2 k m - 1).

4. О том, как размножаются кролики Для записи числа в фибоначчиевой системе счисления используется обозначение:

n = (bk... b2)F.

(См. также 12.14, 4.193.) 3.126. Формула Бине. Докажите по индукции формулу Бине:

n - n Fn =, 1 + 5 1 - где = Ч золотое сечение или число Фидия, а = 2 (лфи с крышкой) Ч сопряженное к нему. (См. также 11.43, 11.75.) 3.127. Докажите следующий вариант формулы Бине:

[(n-1)/2] 2n-1Fn = Cn 5k.

2k+k=(См. также 4.129.) 3.128. Докажите, что число Фибоначчи Fn совпадает с ближайшим n целым числом к, то есть n Fn = +.

3.129. Числа Фибоначчи и треугольник Паскаля. Докажите равенство:

C0 + C1 + C2 +... = Fn+1.

n n-1 n-Сумма, стоящая в левой части равенства, может быть интерпретирована, как сумма элементов треугольника Паскаля, стоящих в одной диагонали (См. приложение В, II и задачи 2.67, 3.124, 11.44 и 11.45.) 3.130. Вычислите сумму:

Sn = C0 - C1 + C2 -...

n n-1 n-(См. также 11.44, 11.45.) 3.131. Сколько существует последовательностей из 1 и 2, таких что сумма чисел в каждой такой последовательности равна n Например, если n = 4, то таких последовательностей пять:

11111, 112, 121, 211, 22.

3.132. Решите в целых числах уравнение x n+1 + y n = 1.

40 3. Алгоритм Евклида и основная теорема арифметики Определение. Последовательность чисел Люка {L0, L1, L2,... } = {2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521,... } задается равенствами L0 = 2, L1 = 1, Ln+2 = Ln+1 + Ln (n 0).

3.133. Докажите, что числа Люка связаны с числами Фибоначчи соотношениями:

а) Ln = Fn-1 + Fn+1;

б) 5 Fn = Ln-1 + Ln+1;

в) F2n = Ln Fn;

г) L2 + L2 = 5F2n+1;

n+1 n д) Fn+2 + Fn-2 = 3Fn.

(См. также 9.79, 11.41.) 3.134. В вершинах правильных многоугольников записываются числа 1 и 2. Сколько существует таких многоугольников, что сумма чисел стоящих в вершинах равна n (n 3) Две расстановки чисел, которые можно совместить поворотом не отождествляются.

3.135. Выразите Ln в замкнутой форме через и. (См. также 11.77.) 3.136. Докажите равенства 7 + 3 5 7 - 3 4 а) - = 1;

2 11 + 5 5 76 - 34 5 б) + = 1.

2 Найдите общую формулу, для которой данные равенства являются частными случаями.

3.137*. Решите в целых числах уравнения:

а) x2 - xy - y2 = 1;

б) x2 - xy - y2 = -1.

3.138. а) Докажите, что в последовательности чисел Фибоначчи при m 2 встречается не менее 4 и не более 5 m-значных чисел.

б) Докажите, что число F5t+2 (t 0) содержит в своей десятичной записи не менее t + 1 цифры.

3.139. Рассмотрим алгоритм Евклида из задачи 3.36 состоящий из k шагов. Докажите, что начальные числа m0 и m1 должны удовлетворять неравенствам m1 Fk+1, m0 Fk+2.

3.140. Теорема Ламе. Пусть число m1 в десятичной системе счисления записывается при помощи t цифр. Докажите, что при любом m5. Цепные дроби число шагов k в алгоритме Евклида для чисел m0 и m1 удовлетворяет неравенству k 5t.

3.141. Фибоначчиевы коэффициенты.

1 1 1 1 2 2 1 3 6 3 1 5 15 15 5 1 8 40 60 40 8 1 13 104 260 260 104 13 Данная таблица аналогична треугольнику Паскаля и состоит из фиk боначчиевых коэффициентов Fn, определяемых равенством Fn Fn-1 ... Fn-k+k Fn = (0 k n).

Fk Fk-1 ... Fа) Докажите, что фибоначчиевы коэффициенты обладают свойk k ством симметрии Fn = Fn-k.

k k-б) Найдите формулу, которая выражает коэффициент Fn через Fn-k и Fn-1 (аналогичную равенству б) из задачи 2.77).

в) Объясните, почему все фибоначчиевы коэффициенты являются целыми числами.

3.142*. Обобщенные биномиальные коэффициенты. Пусть A1, A2,... Ч последовательность ненулевых целых чисел, такая, что (Am, An) = A(m,n) (m, n 1).

Докажите, что все обобщенные биномиальные коэффициенты An An-1 ... An-k+Ak = n Ak Ak-1 ... Aявляются целыми числами. (См. также 8.89.) 5. Цепные дроби Определение. Пусть a0 Ч целое, a1, a2,..., an Ч натуральные и an > 1. n-членной цепной (непрерывной) дробью называется выражение a0 + (3.1) a1 +.

a2 +.

.

+ an 42 3. Алгоритм Евклида и основная теорема арифметики (обозначается [a0; a1, a2,..., an]).

Числа a1, a2,..., an называются неполными частными дроби (3.1).

147 3.143. Разложите в цепные дроби числа и.

13 Pn 3.144. Пусть = [1; 1,.., 1 ]. Чему равны Pn и Qn.

Qn n 3.145. Как связано разложение рационального числа в цепную дробь с алгоритмом Евклида 3.146. Геометрическая интерпретация алгоритма Евклида.

Работу алгоритма Евклида (см. раздел 2) можно представить следующим образом. В прямоугольник размерами m0 m1 (m1 m0) укладываем a0 квадратов размера m1 m1, в оставшийся прямоугольник размерами m1 m2 (m2 m1) укладываем a1 квадратов размера m2 m2, и т. д. до тех пор, пока весь прямоугольник не покроется квадратами. (См. также 3.157.) Выразите общее число квадратов через элементы цепной дроби числа m1/m2.

3.147. Для каждого натурального n приведите пример прямоугольника, который разрезался бы ровно на n квадратов.

3.148. Цепные дроби и электрические цепи. Для данного рационального числа a/b постройте электрическую цепь из единичных сопротивлений, общее сопротивление которой равнялось бы a/b. Как такую цепь можно получить при помощи разбиения прямоугольника a b на квадраты из задачи 3.146 3.149. Пусть a0 Ч целое, a1,..., an Ч натуральные числа. Определим две последовательности P-1 = 1, P0 = a0, Pk = akPk-1 + Pk-2 (1 k n);

Q-1 = 0, Q0 = 1, Qk = akQk-1 + Qk-2 (1 k n).

Докажите, что построенные последовательности для k = 0, 1,..., n обладают следующими свойствами:

Pk а) = [a0; a1, a2,..., ak];

Qk б) PkQk-1 - Pk-1Qk = (-1)k+1;

в) (Pk, Qk) = 1.

Определение. Рациональные дроби Pk = [a0; a1, a2,..., ak] (k = 0, 1,..., n) Qk 5. Цепные дроби называются подходящими дробями к непрерывной дроби (3.1).

3.150. Докажите следующие свойства подходящих дробей:

а) PkQk-2 - Pk-2Qk = (-1)kak (k 2);

Pk Pk-1 (-1)k+б) - = (k 1);

Qk Qk-1 QkQk-в) Q1 < Q2 <... < Qn;

P0 P2 P4 Pn P5 P3 Pг) < <...... < < ;

Q0 Q2 Q4 Qn Q5 Q3 QP2k P2l+д) < (k, l 0).

Q2k Q2l+a 3.151. Пусть числа a и b определены равенством = [a0; a1, a2,...

b..., an]. Докажите, что уравнение ax - by = 1 c неизвестными x и y имеет решением одну из пар (Qn-1, Pn-1) или (-Qn-1, -Pn-1). Отчего зависит, какая именно из пар является решением 3.152. Разлагая число a/b в непрерывную дробь, решите в целых числах уравнения ax - by = 1, если a) a = 101, b = 13;

б) a = 79, b = 19.

3.153. Григорианский календарь. Обыкновенный год содержит 365 дней, високосный Ч 366. n-й год, номер которого не делится на 100, является високосным тогда и только тогда, когда n кратно 4. n-й год, где n делится на 100, является високосным тогда и только тогда, когда n кратно 400. Так, например, 1996-й и 2000-й годы Ч високосные, а 1997-й и 1900-й Ч нет. Эти правила были установлены папой Григорием XIII.

До сих пор мы имели ввиду гражданский год, число дней которого должно быть целым. Астрономическим же годом называется период времени, за который Земля совершает полный оборот вокруг Солнца.

Считая, что григорианский год полностью согласован с астрономическим годом, найдите продолжительность астрономического года. (См.

также 12.7.) Определение. Бесконечной непрерывной дробью называется выражение вида [a0; a1,..., an,... ] = a0 + a1 +.

a2 +.

.

+.

an +.

.

где a0 Ч целое, a1, a2,..., an,... Ч натуральные числа.

44 3. Алгоритм Евклида и основная теорема арифметики Величиной бесконечной непрерывной дроби называется предел ее подходящих дробей, то есть такое число, что Pn = lim, n Qn Pn где = [a0; a1, a2,..., an].

Qn 3.154. Докажите, что любое иррациональное число допускает представление = [a0; a1,..., an-1, n], где a0 Ч целое, a1, a2,..., an-1 Ч натуральные, n > 1 Ч иррациональное действительное числа. Отсюда следует, что каждому иррациональному действительному числу можно поставить в соответствие бесконечную цепную дробь.

3.155. Докажите, что для любой бесконечной цепной дроби [a0; a1,..., an,... ] существует предел ее подходящих дробей Ч иррациональное число.

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

Таким образом, существует взаимно-однозначное соответствие между иррациональными числами и бесконечными цепными дробями. Поэтому в дальнейшем будем отождествлять цепную дробь с ее числовым значением.

3.156. Предположим, что число задано бесконечной цепной дробью = [a0; a1,..., an,... ].

Докажите, что 1 1 1 = a0 + - + -... + (-1)n +...

q0q1 q1q2 q2q3 qnqn+3.157. Последовательности {ak} и {bk} строятся по следующему закону:

a1 = 1, b1 = 2, an+1 = min(an, bn), bn+1 = |bn - an| (n 1).

а) Докажите, что an = 0 и an стремится к 0 при n.

б) Докажите, что последовательность cn = a2 + a2 +... + a2 имеет 1 2 n предел и найдите этот предел.

Pages:     | 1 |   ...   | 3 | 4 | 5 | 6 | 7 |   ...   | 30 |    Книги по разным темам