alfutova(алгебра и теория чисел). Сборник задач для математических школ м мцнмо, 2002. 264 с Настоящее пособие представляет собой сборник задач по математике
 Скачать 2 Mb.
|
|
25 2.103. Сколько существует целых чисел от 1 до 33 000, которые не делятся ни на 3 ни на 5, но делятся на 11? 2.104. Сколько существует целых чисел от 1 до 1 000 000, которые не являются ни полным квадратом, ни полным кубом, ни четвертой степенью. Беспорядки. В классе 30 учеников. Сколькими способами они могут пересесть так, чтобы ни один не сел на свое место. Сколькими способами можно расселить 15 гостей в четырех комнатах, если требуется чтобы ни одна из комнат не осталась пустой. В комнате площадью 6 м 2 постелили три ковра произвольной формы площадью 3 м 2 каждый. Докажите, что какие-либо два из них перекрываются по площади, не меньшей 1 мВ прямоугольнике площади 5 расположено 9 фигур площади каждая. Докажите, что найдутся две фигуры, площадь общей части которых не меньше 1/9. 2.109 * . В прямоугольнике площади 1 расположено 5 фигур площади каждая. а) Докажите, что найдутся два фигуры, площадь общей части которых не меньше б) Докажите, что найдутся две фигуры, площадь общей части которых не меньше в) Докажите, что найдутся три фигур, площадь общей части которых не меньше 1/20. 2.110. Докажите, что в условии задач 2.109 б) ив) числа 1/5 и нельзя заменить большими величинами. Числа Каталана Во многих комбинаторных задачах решением является последовательность чисел Каталана {C n } = {C 0 , C 1 , C 2 , . . . } = {1, 1, 2, 5, 14, 42, . . . Определение. Пусть имеется n + 1 переменная x 0 , x 1 , . . . , x n , и мы хотим вычислить их произведение при помощи n умножений. Определим число C n как количество способов расставить скобки в произведении так, чтобы порядок умножений был полностью определен. Например, при n = 2 существует два способа x 0 · (x 1 · x 2 ) , (x 0 · x 1 ) · x 2 , а при n = 3 уже 5: x 0 · (x 1 · (x 2 · x 3 )), x 0 · ((x 1 · x 2 ) · x 3 ), (x 0 · x 1 ) · (x 2 · x 3 ), (x 0 · (x 1 · x 2 )) · x 3 , ((x 0 · x 1 ) · x 2 ) · x 3 26 2. Комбинаторика. Сколько последовательностей, a 2 , . . . , a 2n }, состоящих из+ и − 1, обладают тем свойством, что a 1 + a 2 + . . . + a 2n = 0 , а все их частичные суммы a 1 , a 1 + a 2 , . . . , a 1 + a 2 + . . . + a 2n неотрицательны. Сколько существует способов разрезать выпуклый (n + 2)- угольник диагоналями на треугольники. Маршруты ладьи. Рассмотрим шахматные доски со сторонами. Требуется провести ладью из левого нижнего угла в правый верхний. Двигаться можно только вверх и вправо, не заходя при этом на клетки главной диагонали и ниже нее. (Ладья оказывается на главной диагонали только в начальный ив конечный моменты времени) Сколько существует таких маршрутов. Очередь в кассу. Билеты стоят 50 центов, и 2n покупателей стоят в очереди в кассу. Половина из них имеет по одному доллару, остальные — по 50 центов. Кассир начинает продажу билетов, не имея денег. Сколько существует различных порядков в очереди, таких, что кассир всегда может дать сдачу. Формула для чисел Каталана. Пусть, a 2 , . . . , a n } последовательность целых чисел, сумма которых равна + 1. Докажите, что ровно у одного из ее циклических сдвигов, a 2 , . . . , a n }, {a 2 , . . . , a n , a 1 }, . . . , {a n , , a 1 . . . , a все частичные суммы положительны. Выведите отсюда равенства C n 2n+1 1 2n + 1 = C n 2n 1 n + 1 = (4n − 2)!!!! (n + где (4n − 2)!!!! = 2 · 6 · 10 . . . (4n − 2) — произведение, в котором участвует каждое четвертое число. (См. также. Рекуррентное соотношение для чисел Каталана. Докажите, что числа Каталана удовлетворяют рекуррентному соотношению C 0 C n−1 + C 1 C n−2 + . . . + См. также Глава Алгоритм Евклида и основная теорема арифметики. Простые числа Определение. Натуральное число p называется простым, если p > и p не имеет положительных делителей, отличных от 1 и По соглашению, 1 не является простым числом. Остальные числа, имеющие три и более делителей, называются составными. Теорема Евклида. Докажите, что простых чисел бесконечно много. Найдите все простые числа, которые отличаются на 17. 3.3. Докажите, что остаток отделения простого числа на 30 — простое число. Пусть n > 2. Докажите, что между n и n! есть по крайней мере одно простое число. Найдите все такие простые числа p и q, для которых выполняется равенство p 2 − 2q 2 = 1 3.6. Докажите, что если число n! + 1 делится на n + 1, то n + 1 простое число. Докажите, что множество простых чисел вида p = 4k + 3 бесконечно. (См. также. Докажите, что множество простых чисел вида p = 6k + 5 бесконечно. (См. также. Докажите, что составное число n всегда имеет делитель d 6 √ n 3.10. Когда натуральное число n имеет нечетное количество делителей. Разложите на простые множители числа 111, 1111, 11111, 111111 , 1111111. (См. также 28 3. Алгоритм Евклида и основная теорема арифметики. Докажите, что существуют 1000 подряд идущих составных чисел. Докажите, что для любого натурального n найдутся n подряд идущих натуральных чисел, среди которых ровно одно простое. Существуют ли а) б) 6 простых чисел, образующих арифметическую прогрессию. Существуют ли арифметическая прогрессия, состоящая лишь из простых чисел. Предположим, что нашлись 15 простых чисел, образующих арифметическую прогрессию с разностью d. Докажите, что d > Определение. Два простых числа, отличающиеся на 2 называются простыми числами-близнецами. 3.17. Докажите, что 3, 5 и 7 являются единственной тройкой простых чисел-близнецов. 3.18. Найдите все простые числа, которые равны сумме двух простых чисел и разности двух простых чисел. Докажите, что при n > 2 числа 2 n − и 2 n + не могут быть простыми одновременно. При каких целых n число n 4 + 4 — составное. Верно ли, что многочлен P(n) = n 2 + n + при всех n принимает только простые значения. Пусть n } — последовательность простых чисел (p 1 = 2 , p 2 = 3 , p 3 = 5 , . . . ). Докажите, что p n > 2n при n > 5. При каких n будет выполняться неравенство p n > 3n ? 3.23. Докажите неравенство p n+1 < p 1 p 2 . . . p n 3.24. Верно ли, что все числа вида p 1 p 2 . . . p n + являются простыми. Числа Евклида. Евклидово доказательство бесконечности множества простых чисел наводит на мысль определить рекуррентно числа Евклида 2, e n = e 1 e 2 . . . e n−1 + 1 (n > Всели числа e являются простыми (См. также. Числа Ферма. Докажите, что если число a n + простое, то a ... и n = 2 k . (Простые числа вида f k = 2 2 k + называются числами Ферма. 2. Алгоритм Евклида 3.27. Докажите, что f делит 2 f n − 2 3.28. Докажите, что числа Ферма f при n > 1 не представимы в виде суммы двух простых чисел. Числа Мерсенна. Докажите, что если число a n − 1 простое, то a = 2 и n — простое. Простые числа вида q = 2 p − называются числами Мерсенна. 3.30. Пусть P n (x) = a n x n +. . .+a 1 x+a 0 — многочлен с целыми коэффициентами. Может ли быть так, что при x = 0, 1, 2, . . все числа P n (x) — простые. Алгоритм Евклида Определение. Наибольшим общим делителем (НОД) целых чисел называется такой положительный общий делитель a 1 , . . . , a n , который делится на любой другой общий делитель этих чисел. НОД чисел a 1 , . . . , a обозначается (a 1 , . . . , a Если наибольший общий делитель чисел a 1 , . . . , a равен 1, то эти числа называются взаимно простыми. Докажите, что если в наборе целых чисел a 1 , . . . , a хотя бы одно отлично от 0, то они имеют наибольший общий делитель. В прямоугольнике с целыми сторонами m и n, нарисованном на клетчатой бумаге, проведена диагональ. Через какое число узлов она проходит Насколько частей эта диагональ делится линиями сетки. Натуральные числа p и q взаимно просты. Отрезок [0; 1] разбит на p + q одинаковых отрезков. Докажите, что в каждом из этих отрезков, кроме двух крайних лежит ровно одно из p + q − 2 чисел. . . , p − 1 p , 1 q , 2 q , . . . , q − 1 q 3.34. С 1 сентября четыре школьника начали посещать кинотеатр. Первый бывал в нем каждый четвертый день, второй — каждый пятый, третий — каждый шестой и четвертый — каждый девятый. Когда второй раз все школьники встретятся в кинотеатре. В задаче 1.1 доказана возможность деления с остатком произвольного целого числа a на натуральное число b. Докажите, что из равенства a = bq + r следует соотношение (a, b) = (b, r). 3.36. Алгоритм Евклида. Пусть и m 1 — целые числа, m 1 > и m 1 - m 0 . Докажите, что при некотором k > 1 существуют целые числа 30 3. Алгоритм Евклида и основная теорема арифметики a 0 , a 1 , . . . , a и m 2 , . . . , m такие, что m 1 > m 2 > m 3 > . . . > m k > 0 , a k > 1 , m 0 = m 1 · a 0 + m 2 , m 1 = m 2 · a 1 + m 3 , m 2 = m 3 · a 2 + m 4 , m k−2 = m k−1 · a k−1 + m k , m k−1 = m k · a и (m 0 , m 1 ) = m k 3.37. Докажите, что для любого s от k − 1 до 0 существуют числа такие, что u s m s + m s+1 v s = d , где d = (m 0 , m 1 ) . В частности, для некоторых u и v выполняется равенство + m 1 v = См. также. Пусть (a, b) = 1 и a | bc. Докажите, что a | c. 3.39. Найдите (1 . . . 1 | {z } m , 1 . . . 1 | {z } n ) 3.40. Какое наибольшее значение может принимать наибольший общий делитель чисел a и b, если известно, что a · b = 600? 3.41. Натуральные числа a 1 , a 2 , . . . , удовлетворяют равенству a 1 + a 2 + . . . + a 49 = Какое наибольшее значение может принимать их наибольший общий делитель. Можно лис помощью циркуля и линейки разделить угол на 19 равных частей. Числа от 1 до 1000 выписаны подряд по кругу. Начиная с первого, вычеркивается каждое е число 1, 15, 31, . . . , причем при повторных оборотах, зачеркнутые числа считаются снова. Число оборотов не ограничено. Сколько чисел останутся незачеркнутыми? 3.44. Докажите, что (5a + 3b, 13a + 8b) = (a, b). 3.45. Может ли наибольший общий делитель двух натуральных чисел быть больше их разности. Докажите, что для нечетных чисел a, b и c имеет место равенство. Алгоритм Евклида 3.47. По окружности радиуса 40 катится колесо радиуса 18. В колесо вбит гвоздь, который ударяясь об окружность, оставляет на ней отметки. Сколько всего таких отметок оставит гвоздь на окружности? Сколько раз прокатится колесо по всей окружности, прежде чем гвоздь попадет в уже отмеченную ранее точку. Для некоторых целых x и y число 3x + 2y делится на Докажите, что число 17x + 19y также делится на 23. 3.49. Докажите, что следующие дроби несократимы при всех натуральных значениях а + 13 n + б 1 n + в n + 1 n 2 + 1 3.50. При каких целых n сократимы дроби а+ 2n + 4 n 2 + n + б n 2 − 3n n 2 − n + 3 ? 3.51. При каких целых n число а+ 1 n 2 + n + б+ n + 1 n 2 − n + также будет целым. Найдите все натуральные n > 1 для которых n 3 − делится на n − 1. 3.53. На какие натуральные числа можно сократить дробь − n 5n + если известно, что она сократима и что числа m и n взаимно просты. Докажите, что при m 6= n выполняются равенства: а) (a m − 1, a n − 1) = a (m,n) − 1 (a > б) (f n , f m ) = где f k = 2 2 k + 1 — числа Ферма. (См. также. Докажите, что число 2 2 n − имеет по крайней мере n различных простых делителей. Докажите, что для простых чисел выполняется неравенство p n+1 6 2 2 n + 1 3.57. Докажите, что равенство (a, mn) = 1 равносильно выполнению двух условий (a, m) = 1 и (a, n) = 1. 3.58. Докажите, что если (a, b) = 1, то (2a + b, a(a + b)) = 1. 3.59. Докажите, что если (a, b) = 1, то наибольший общий делитель чисел a + b и a 2 + равен 1 или 2. 3.60. Пусть a и b — натуральные числа. Докажите, что среди чисел ровно (a, b) чисел делится на b. 32 3. Алгоритм Евклида и основная теорема арифметики. Пусть (a, b) = 1 и (x 0 , y 0 ) — некоторое целочисленное решение уравнения ax + by = 1. Докажите, что все решения этого уравнения в целых числах получаются по формулам x = x 0 + kb , y = y 0 − ka , где k — произвольное целое число. Как описать все решения в целых числах уравнения ax+by = c при произвольных a, b, c? 3.63. Решите в целых числах уравнения (укажите все решения): а) 45x − 37y = г) 109x + 89y = б) 19x + 95y = две. Докажите, что число шагов в алгоритме Евклида может быть сколь угодно большим. Существует ли в сутках момент, когда расположенные на общей оси часовая, минутная и секундная стрелки правильно идущих часов образуют попарно углы в 120 ◦ ? 3.66. Найдите все взаимно простые a и b, для которых a + b a 2 − ab + b 2 = 3 13 3.67. Докажите, что если (a 1 , a 2 , . . . , a n ) = 1 , то уравнение a 1 x 1 + a 2 x 2 + . . . + a n x n = разрешимо в целых числах. Определение. Пусть a 1 , . . . , a n — отличные от 0 целые числа. Наименьшим общим кратным (НОК) этих чисел называется наименьшее положительное число, кратное всем этим числам. НОК чисел a 1 , . . . . . . , a обозначается [a 1 , . . . , a n ] 3.68. Докажите равенства а) [1, 2, . . . , 2n] = [n, n + 1, . . . , б) (a 1 , a 2 , . . . , a n ) = (a 1 , (a 2 , . . . , a в) [a 1 , a 2 , . . . , a n ] = [a 1 , [a 2 , . . . , a n ]] 3.69. На доске написано n натуральных чисел. За одну операцию вместо двух чисел, не делящих друг друга, можно написать их наибольший общий делитель и их наименьшее общее кратное. а) Докажите, что можно провести только конечное число операций. б) Финальный результат независимо от порядка действий будет одними тем же. Например, 6, 9) → (2, 12, 9) → (2, 3, 36) → (1, 6, 36), (4, 6, 9) → (4, 3, 18) → (1, 12, 18) → (1, 6, 36). 3. Мультипликативные функции 3.70. Найдите наименьшее c, при котором а) уравнение 7x + 9y = c имело бы ровно 6 целых положительных решений; б) уравнение 14x + 11y = c имело бы ровно 5 целых положительных решений. В каких пределах должно заключаться c, чтобы уравнение + 14y = c имело бы 6 целых положительных решений. Пусть a и b — натуральные взаимно простые числа. Рассмотрим точки плоскости с целыми координатами (x, y), лежащие в полосе 6 x 6 b − 1. Каждой такой точке припишем целое число N(x, y) = = ax + by а) Докажите, что для каждого натурального c существует ровно одна точка (x, y) (0 6 x 6 b − 1), чтоб) Теорема Сильвестра. Докажите, что наибольшее c, для которого уравнение ax + by = c не имеет решений в целых неотрицательных числах, имеет вид c = ab − a − b. 3.73 * . Пусть числа a и b взаимно просты. Докажите, что для того, чтобы уравнение ax + by = c имело ровно n целых положительных решений, значение c должно находиться в пределах − 1)ab + a + b 6 c 6 (n + 1)ab − a − См. также. Отметим на прямой красным цветом все точки вида 81x + + 100y , где x, y — натуральные, и синим цветом — остальные целые точки. Найдите на прямой такую точку, что любые симметричные относительно нее целые точки закрашены в разные цвета. Объясните, почему такая точка существует. Мультипликативные функции Основная теорема арифметики. Всякое натуральное число, большее 1, раскладывается и только одним способом (с точностью до порядка сомножителей) в произведение простых чисел. Докажите основную теорему арифметики при помощи утверждения из задачи 3.76. Найдите все двузначные числа, квадрат которых равен кубу суммы их цифр. На какое количество нулей заканчивается число 100! ? 34 3. Алгоритм Евклида и основная теорема арифметики. Найдите наименьшее натуральное n, для которого 1999! не делится на 34 n 3.79. Докажите, что произведение чисел от n+1 до 2n делится на ноне делится на 2 n+1 3.80. Пусть a = p α 1 1 · . . . · p α s s , b = p β 1 1 · . . . · p β s s , где p 1 , . . . , p простые, и α 1 , . . . , α s , β 1 , . . . , β s > 0. Докажите равенства: а) (a, b) = p min(α 1 ,β 1 ) 1 · . . . · p б) [a, b] = p max(α 1 ,β 1 ) 1 · . . . · p в) (a, b)[a, b] = ab. 3.81. Докажите равенства: а) [a, (a, b)] = в) abc = [a, b, c](ab, ac, б) (a, [a, b]) = г) abc = (a, b, c)[ab, bc, ac]. 3.82. Докажите, что (bc, ac, ab) ... (a, b, c) 2 3.83. Приведите пример, когда равенство (a, b, c)[a, b, c] = abc не выполнено. Каким неравенством всегда будут связаны числа (a, b, c) × × [a, b, c] и abc? 3.84. Сколько различных делителей имеют числа а) 2 · 3 · 5 · 7 · б) 2 2 · 3 3 · 5 5 · 7 7 · 11 11 ? 3.85. Для каждого k от 1 до 6 найдите наименьшее натуральное число, которое имеет ровно k различных делителей. Пусть τ(n) — количество положительных делителей натурального числа n = p α 1 1 · . . . · p α s s , а σ(n) — их сумма. Докажите равенства: а) τ(n) = (α 1 + 1) · . . . · (α s + б) σ(n) = p α 1 +1 1 − 1 p 1 − 1 · . . . · p α s +1 s − 1 p s − 1 3.87. Найдите натуральное число n, зная, что оно имеет два простых делителя и удовлетворяет условиям τ(n) = 6, σ(n) = 28. 3.88. Некоторое натуральное число n имеет два простых делителя. Его квадрат имеет а) б) 81 делителей. Сколько делителей имеет куб этого числа. Найдите натуральное число вида n = 2 x · 3 y · 5 z , зная, что половина его имеет на 30 делителей меньше, треть — на 35 и пятая часть — на 42 делителя меньше, чем само число. Определение. Функция f(n), определенная на множестве натуральных чисел называется мультипликативной, если она удовлетворяет двум условиям) f(1) = 1; 2) f(m · n) = f(m) · при (m, n) = 1. 3. Мультипликативные функции 35 Если f(1) = 1 и равенство f(m · n) = f(m) · f(n) выполнено для всех пар натуральных чисел m и n, то функция f(n) называется вполне мультипликативной. Докажите мультипликативность функций τ(n) и σ(n). 3.91. Докажите неравенство τ(n) 6 2 √ n 3.92. Пусть у двух целых положительных чисел равны суммы делителей и равны суммы всех обратных величин к делителям. Докажите, что эти числа равны. Пусть (m, n) > 1. Что больше τ(m · n) или τ(m) · τ(n)? Исследуйте тот же вопрос для функции σ(n). (См. также 4.144 .) Определение. Число n называется совершенным, если σ(n) = Например, числа 6 и 28 — совершенные + 2 + 3 + 6 = 2 · 6, 1 + 2 + 4 + 7 + 14 + 28 = 2 · 28. 3.94. Совершенные числа. Докажите, что если 2 k − 1 = некоторое простое число Мерсенна, то n = 2 k−1 (2 k − 1) — совершенное число. Теорема Эйлера. Докажите, что если n — четное совершенное число, то оно имеет вид n = 2 k−1 (2 k − 1) , и p = 2 k − 1 — простое число Мерсенна. Проблема существования нечетных совершенных чисел остается среди трудных и нерешенных задач теории чисел. Определение. Числа m и n называются дружественными, если сумма собственных делителей числа m равна n и, наоборот, сумма собственных делителей числа n равна m. Другими словами, числа m и являются дружественными, если) − m = n, σ(n) − n = или) = m + n = σ(n). 3.96. Дружественные числа. Докажите, что если все три числа p = 3 · 2 k−1 − 1 , q = 3 · 2 k − и r = 9 · 2 2k−1 − 1 — простые, то числа m = 2 k · p · q и n = 2 k · r — дружественные. Постройте примеры дружественных чисел. Может ли быть так, что а) σ(n) > б) > 100n ? 3.98. Задача Ферма. Найдите наименьшее число вида n = где и p 2 — некоторые простые числа, такое, что σ(n) = 3n. 36 3. Алгоритм Евклида и основная теорема арифметики. Пусть α — действительное положительное число, d — натуральное. Докажите, что количество натуральных чисел, не превосходящих α и делящихся на d, равно h α d i 3.100. Докажите, что для действительного положительного α и натурального всегда выполнено равенство h α d i = h [α] d i 3.101. Формула Лежандра. Число n! разложено в произведение простых чисел n! = p α 1 1 . . . p α s s . Докажите равенство n p k i + h n p 2 k i + h n p 3 k i + . . . 3.102. Докажите, что число p входит в разложение n! с показателем, не превосходящим h n p − 1 i 3.103. Пусть представление числа n в двоичной системе выглядит следующим образом = 2 e 1 + 2 e 2 + . . . + 2 e r (e 1 > e 2 > . . . > e r > Докажите, что n! делится на 2 n−r , ноне делится на 2 n−r+1 3.104. Результат предыдущей задачи допускает обобщение. Пусть p — простое число и представление числа n в p-ичной системе имеет вид = a k p k + a k−1 p k−1 + . . . + a 1 p 1 + Найдите формулу, выражающую показатель α p , с которым это число p входит в каноническое разложение n!, через n, p и коэффициенты a k 3.105. При помощи формулы Лежандра из задачи 3.101 докажите, что число + 1 C n 2n (n > 0) всегда целое. (См. также. Докажите, что число (2n)! m! n! (m + n)! (m, n > 0) всегда целое. Существует ли такое целое r, что число n! 2 |