WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 |   ...   | 3 | 4 || 6 | 7 |   ...   | 27 |

Докажите, что все обобщенные биномиальные коэффициенты 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 предел и найдите этот предел.

5. Цепные дроби 3.158. Юлианский календарь. Из астрономии известно, что год имеет 365,2420... = [365; 4, 7, 1, 3,... ] так называемых «календарных суток». В Юлианском стиле каждый четвертый год — високосный, то есть состоит из 366 дней. За сколько лет при таком календаре накапливается ошибка в одни сутки На сколько дней отстает Юлианский календарь за 1000 лет И вообще, почему он отстает, если юлианский год длиннее астрономического 3.159. Персидский календарь. Наиболее точный календарь ввел в Персии в 1079 году персидский астроном, математик и поэт Омар Альхайями. Восстановите этот календарный стиль, рассмотрев третью подходящую дробь [365; 4, 7, 1] к длительности астрономического года.

За сколько лет в этом календаре накапливается ошибка в одни сутки Определение. Бесконечная непрерывная дробь вида [a0; a1,..., ak, ak+1,..., ak+T, ak+1,..., ak+T,... ] = = [a0; a1,..., ak, ak+1,..., ak+T ] называется периодической с периодом ak+1,..., ak+T. Набор a0, a1,...

..., ak называется предпериодом.

Бесконечная непрерывная дробь вида [a0; a1,..., aT -1 ] называется чисто периодической.

3.160. Вычислите следующие цепные дроби:

а) [ 5; 1, 2, 1, 10]; б) [ 5; 1, 4, 1, 10]; в) [ 2; 1, 1, 3].

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

а) 2; б) 3; в) + 7.

3.162. Формат A4. Найдите наименьшее натуральное n, для которого существует такое m, что m 2 < <.

n 3.163. Числа из электрической розетки. Найдите наименьшее натуральное n, для которого существует такое m, что m 3 < <.

n (См. [185].) Определение. Число называется квадратичной иррациональностью, если оно является иррациональным корнем некоторого квадратного уравнения с целыми коэффициентами.

46 3. Алгоритм Евклида и основная теорема арифметики Если = b + c d — квадратичная иррациональность, то число = = b - c d называется сопряженным к числу.

3.164. Докажите, что значение любой периодической цепной дроби — квадратичная иррациональность.

Верно более сильное утверждение.

Теорема Лагранжа. Число разлагается в периодическую цепную дробь тогда и только тогда, когда оно является квадратичной иррациональностью. (См. [5], [28].) 3.165. Найдите рациональное число, которое отличается от не более чем на 0,0001, где а) = 2; б) = 2 + 5; в) = 3 + 7.

3.166. Докажите равенство:

(1 + 2)n+1 - (1 - 2)n+[ 2; 2,.., 2 ] =.

.

(1 + 2)n - (1 - 2)n n 3.167*. Теорема Лежандра. Докажите, что если - p <, q 2qp то — подходящая дробь к числу.

q 3.168. Теорема Валена. Докажите, что если pn/qn (n 1) — подходящая дробь к числу, то имеет место по крайней мере одно из неравенств - pn 1 pn-1 < или - <.

qn 2q2 qn-1 2qn n-Получите отсюда теорему Валена: для любого найдется бесконечно много дробей p/q таких, что - p <.

q 2q3.169*. Докажите, что для любых целых чисел p и q (q = 0), справедливо неравенство p 2 >.

- q 3q3.170. Докажите, что при k 1 выполняется равенство:

aFk+2 - k k-1 = [aF ; aF,..., aF ], aFk+1 - 5. Цепные дроби где {Fk} — последовательность чисел Фибоначчи.

3.171. Докажите, что положительный корень квадратного уравнения bx2 - abx - a = 0, где a и b — натуральные числа, разлагается в чисто периодическую цепную дробь с длиной периода, равной 2. Верно ли обратное утверждение 3.172. Докажите, что если квадратное уравнение с целыми коэффициентами имеет корень x = [a; b], то вторым корнем служит число -.

[a; b] 3.173. Докажите, что если положительная квадратичная ирра A + D циональность = разлагается в чисто периодическую цепB ную дробь, то сопряженная ей квадратичная иррациональность = A - D = принадлежит интервалу (-1; 0).

B 3.174. Докажите, что если квадратное уравнение с целыми коэффициентами имеет корень x = [a; b, c], то вторым корнем будет число a - [c, b].

Глава Арифметика остатков 1. Четность 4.1. Пусть m и n — целые числа. Докажите, что mn(m + n) — четное число.

4.2. Рукопожатия. Каждый из людей, когда-либо живших на земле, сделал определенное число рукопожатий. Докажите, что число людей, сделавших нечетное число рукопожатий — четно.

4.3. В прямоугольном треугольнике длины сторон — натуральные взаимно простые числа. Докажите, что длина гипотенузы — нечетное число, а длины катетов имеют разную четность.

4.4. На доске написано 10 плюсов и 15 минусов. Разрешается стереть любые два знака и написать вместо них плюс, если они одинаковы, и минус в противном случае. Какой знак останется на доске после выполнения 24 таких операций 4.5. Из шахматной доски вырезали две противоположные угловые клетки (a8 и h1). Можно ли оставшуюся часть доски покрыть неперекрывающимися косточками домино 4.6. Город имеет форму квадрата 5 5 (см. рисунок). Какую наименьшую длину может иметь маршрут, если нужно пройти по каждой улице этого города и вернуться в прежнее место (По каждой улице можно проходить любое число раз.) 4.7. Может ли ладья перейти из одного угла шахматной доски в противоположный угол (по диагонали), побывав по одному разу на всех 64 клетках Тот же вопрос для коня.

4.8. Вороны на деревьях. Вдоль улицы стоят деревьев и на каждом из них сидит по вороне. Раз в час две из них взлетают и каждая садится на одно из соседних деревьев.

Может ли получится так, что все вороны соберутся на одном дереве 4.9. Термит и 27 кубиков. Представим себе большой куб, склеенный из 27 меньших кубиков. Термит садится на центр грани одного 1. Четность из наружных кубиков и начинает прогрызать ход. Побывав в кубике, термит к нему уже не возвращается. Движется он при этом всегда параллельно какому-нибудь ребру большого куба. Может ли термит прогрызть все 26 внешних кубиков и закончить свой ход в центральном кубике Если возможно, покажите, каким должен быть путь термита.

4.10. На хоккейном поле лежат три шайбы A, B и C. Хоккеист бьет по одной из них так, что она пролетает между двумя другими. Так он делает 25 раз. Могут ли после этого шайбы оказаться на своих местах 4.11. Все косточки домино выложены в цепь. На одном конце оказалось 5 очков. Сколько очков на другом конце 4.12. Можно ли множество всех натуральных чисел больше 1 разбить на два непустых подмножества так, чтобы для любых двух чисел a и b из одного множества число ab - 1 принадлежало другому 4.13. Дан выпуклый 2n-угольник A1,..., A2n. Внутри него взята точка P, не принадлежащая ни одной из диагоналей. Докажите, что точка P принадлежит четному числу треугольников с вершинами в точках A1,..., A2n.

4.14. В ряд выписаны числа 1, 2,..., 10. Можно ли расставить между ними знаки «+» и «-» так, чтобы значение полученного выражения было равно нулю 4.15*. К 17-значному числу прибавили число, записанное теми же цифрами, но в обратном порядке. Докажите, что хотя бы одна цифра полученной суммы четна.

4.16. Улитка ползет по плоскости с постоянной скоростью, каждые 15 минут поворачивая под прямым углом. Докажите, что вернуться в исходную точку она может лишь через целое число часов.

4.17. Есть 101 монета, из которых 50 фальшивых, отличающихся по весу на 1 грамм от настоящих. Коля Васин взял одну монету и за одно взвешивание на весах со стрелкой, показывающей разность весов на чашках, хочет определить фальшивая ли она. Сможет ли он это сделать 4.18. 7 стаканов. На столе стоят 7 стаканов — все вверх дном.

Разрешается за один ход перевернуть любые 4 стакана. Можно ли за несколько ходов добиться того, чтобы все стаканы стояли правильно 4.19. В клетках квадратной таблицы 4 4 расставлены знаки + и -, как показано на рисунке + - + + + + + + + + + + + + + + 50 4. Арифметика остатков Разрешается одновременно менять знак во всех клетках, расположенных в одной строке, в одном столбце или на прямой, параллельной какой-нибудь диагонали (в частности, можно менять знак в любой угловой клетке). Докажите, что, сколько бы мы ни производили таких перемен знака, нам не удастся получить таблицу из одних плюсов.

4.20. Марсианские амебы. В пробирке находятся марсианские амебы трех типов A, B и C. Две амебы любых двух разных типов могут слиться в одну амебу третьего типа. После нескольких таких слияний в пробирке оказалась одна амеба. Каков ее тип, если исходно амеб типа A было 20 штук, типа B — 21 штука, и типа C — 22 штуки (См. также 5.78.) 4.21. Игра «Йога». На поле для игры расставлены 32 фишки (смотрите рис. 1). При взятии одна фишка перескакивает через другую — почти как в шашках, но не по диагонали, а по горизонтали или по вертикали. Допустим, в конце игры осталась 1 фишка. Объясните, почему для ее расположения есть только 5 вариантов, изображенных на рисунке 2. (См. также 5.79.) Рис. 1. Рис. 2.

Указание: Рассадите на поле для игры марсианских амеб. Пусть в клетках A и B сидят амебы, а клетка C — пустая. Тогда амеба A, перепрыгивая через амебу B превращается в амебу C, а амеба B исчезает.

4.22. Код, исправляющий ошибку. Предположим, что требуется передать сообщение, состоящее из n2 нулей и единиц. Запишем его в виде квадратной таблицы n n. Допишем к каждой строке сумму ее элементов по модулю 2. Получится еще один столбец высоты n.

Аналогично поступим с каждым столбцом (в том числе найдем и сумму элементов дописанного столбца). Например, если требуется передать сообщение 0111, то таблица 2 2 окажется дополненной до таблицы 3 3:

0 1 0 1 1 1 1 0 2. Делимость Докажите, что если при передаче расширенной таблицы (n+1)(n+1) произойдет одна ошибка, то эту ошибку можно будет найти и исправить.

Какое наименьшее число ошибок должно произойти, чтобы об этом нельзя было узнать 2. Делимость.

.

4.23. Пусть p > 3 — простое число. Докажите, что p2 - 1. 24.

4.24. Докажите, что любое натуральное число, десятичная запись которого состоит из 3n одинаковых цифр, делится на 37.

4.25. Докажите, что число 11... 1 (1986 единиц) имеет по крайней мере а) 8; б) 32 различных делителя.

4.26. Докажите, что числа 2001 а) 23 + 1; б) 23 - 1 — составные.

4.27. Докажите следующие соотношения:

..

...

а) 241 - 1. 83; б) 270 + 370. 13; в) 215 - 1. 20801.

.

4.28. Докажите, что для любого простого числа p > 2 числитель дроби m 1 1 = + +... + n 1 2 p - делится на p.

4.29. Натуральные числа m и n таковы, что m > n, m не делится на n и имеет от деления на n тот же остаток, что и m + n от деления на m - n. Найдите отношение m : n.

.

.

4.30. Даны целые числа a, b, c такие, что a + b + c. 6. Докажите,.

что a3 + b3 + c3. 6.

.

.

.

4.31. Докажите, что 1110 - 1. 100.

4.32. Сколько имеется различных прямоугольных треугольников, длины сторон которых выражены целыми числами, если один из катетов этих треугольников равен 15 4.33. Решите уравнения:

а) 3x2 + 5y2 = 345; б) 1 + x + x2 + x3 = 2y.

4.34. Докажите, что число 11999 + 21999 +... + 161999 делится на 17.

4.35. Назовем шестизначное число счастливым, если сумма его первых трех цифр равна сумме последних трех цифр. Докажите, что сумма всех счастливых чисел делится на 13.

52 4. Арифметика остатков 4.36. Докажите, что числа от 1 до 2001 включительно нельзя выписать подряд в некотором порядке так, чтобы полученное число было точным кубом.

77.

4.37. Докажите, что 77 - 77. 10.

.

4.38. Число x таково, что x2 заканчивается на 001 (в десятичной системе счисления). Найдите три последние цифры числа x (укажите все возможные варианты).

Pages:     | 1 |   ...   | 3 | 4 || 6 | 7 |   ...   | 27 |






















© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.