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

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 (укажите все возможные варианты).

4.39. Имеется много одинаковых квадратов. В вершинах каждого из них в произвольном порядке написаны числа 1, 2, 3 и 4. Квадраты сложили в стопку и написали сумму чисел, попавших в каждый из четырех углов стопки. Может ли оказаться так, что а) в каждом углу стопки сумма равна 2004 б) в каждом углу стопки сумма равна 2005 4.40. Дан многочлен с целыми коэффициентами. Если в него вместо неизвестной подставить 2 или 3, то получаются числа, делящиеся на 6.

Докажите, что если вместо неизвестной в него подставить 5, то также получится число, делящееся на 6.

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

4.42. Докажите, что если p Ч простое число и 1 k p - 1, то.

Ck. p.

.

p 4.43. Докажите утверждение обратное тому, что было в задаче 4.42:

.

если Ck. n при 1 k n - 1, то n Ч простое число.

.

n 4.44. Докажите, что если p Ч простое число и 1 k p - 2, то.

Ck - Ck-2. p. Верно ли обратное утверждение.

p-k+1 p-k-4.45. Докажите, что если p Ч простое число, то при любых целых a и b выполняется соотношение.

(a + b)p - ap - bp. p.

.

4.46*. Камни лежат в трех кучках: в одной Ч 51 камень, в другой Ч 49 камней, а в третьей Ч 5 камней. Разрешается объединять любые кучки в одну, а также разделять кучку из четного количества камней на две равные. Можно ли получить 105 кучек по одному камню в каждой В следующих задачах понадобится вспомнить принцип Дирихле из раздела 2.

4.47. Докажите, что среди любых n натуральных чисел, не делящихся на n, есть несколько чисел, сумма которых делится на n.

3. Сравнения 4.48. Докажите, что среди любых десяти последовательных натуральных чисел найдется число, взаимно простое с остальными.

4.49. На 99 карточках пишутся числа 1, 2,..., 99. Затем карточки тасуются и раскладываются чистыми сторонами вверх. На чистых сторонах карточек снова пишутся числа 1, 2,..., 99. Для каждой карточки числа, стоящие на ней, складываются и 99 полученных сумм перемножаются. Докажите, что в результате получится четное число.

3. Сравнения Определение. Пусть m 1. Два числа a и b называются сравнимыми по модулю m, если их разность делится на m. Записывается это в виде a b (mod m).

4.50. Что означают записи:

а) a b (mod 0); б) a b (mod 1) 4.51. Свойства сравнений. Докажите, что если a b (mod m) и c d (mod m), то а) a + c b + d (mod m); б) ac bd (mod m).

Определение. Классом вычетов по данному модулю m называется множество всех целых чисел сравнимых с некоторым данным целым числом a по модулю m. Такой класс обозначается.

4.52. Докажите, что класс состоит из всех чисел вида mt + a, где t Ч произвольное целое число.

4.53. Докажите, что два класса и b совпадают тогда и только тогда, когда a b (mod m).

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

4.54. Докажите, что любые m чисел x1,..., xm попарно несравнимых по модулю m, представляют собой полную систему вычетов по модулю m.

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