WWW.DISSERS.RU

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

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


Pages:     | 1 | 2 || 4 | 5 |   ...   | 27 |

n-1 n n+1 n-1 n+1 n 2.79. 120 одинаковых шаров плотно уложены в виде правильной треугольной пирамиды. Сколько шаров лежит в основании 2.80. В разложении (x + y)n по формуле бинома Ньютона второй член оказался равен 240, третий — 720, а четвертый — 1080. Найдите x, y и n.

22 2. Комбинаторика 2.81. Биномиальная система счисления. Покажите, что любое целое неотрицательное число n может быть представлено в виде n = C1 + C2 + C3, x y z где x, y, z — целые числа такие, что 0 x < y < z.

2.82. В компании из 10 человек произошло 14 попарных ссор. Докажите, что все равно можно составить компанию из трех друзей.

2.83. Найдите m и n зная, что Cm+1 : Cm : Cm-1 = 5 : 5 : 3.

n+1 n+1 n+ 2.84. Какое слагаемое в разложении (1 + 3)100 по формуле бинома Ньютона будет наибольшим 2.85. Сколько четырехзначных чисел можно составить, используя цифры 1, 2, 3, 4 и 5, если:

а) никакая цифра не повторяется более одного раза;

б) повторения цифр допустимы;

в) числа должны быть нечетными и повторений цифр быть не должно 2.86. Сколько существует различных возможностей рассадить юношей и 5 девушек за круглый стол с 10-ю креслами так, чтобы они чередовались 2.87*. В выпуклом n-угольнике проведены все диагонали. Известно, что никакие три из них не пересекаются в одной точке. На сколько частей разделится при этом многоугольник Во скольких точках пересекутся диагонали 2.88. Гармонический треугольник Лейбница.

1 2 1 1 3 6 1 1 1 4 12 12 1 1 1 1 5 20 30 20 1 1 1 1 1 6 30 60 60 30 Здесь изображен фрагмент таблицы, которая называется треугольником Лейбница. Его свойства «аналогичны в смысле противоположности» свойствам треугольника Паскаля. Числа на границе треугольника обратны последовательным натуральным числам. Каждое число 4. Формула включений и исключений внутри равно сумме двух чисел, стоящих под ним. Найдите формулу, которая связывает числа из треугольников Паскаля и Лейбница.

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

1 1 1 1 1 а) = + + + + +... ;

1 2 6 12 20 1 1 1 1 1 б) = + + + + +... ;

2 3 12 30 60 1 1 1 1 1 в) = + + + + +...

3 4 20 60 140 2.90. Найдите сумму 1 1 1 + + + +...

12 30 60 и обобщите полученный результат.

2.91. Найдите суммы рядов 1 1 1 а) + + + +... ;

1 · 2 2 · 3 3 · 4 4 · 1 1 1 б) + + + +... ;

1 · 2 · 3 2 · 3 · 4 3 · 4 · 5 4 · 5 · 0! 1! 2! 3! в) + + + +... (r 2).

r! (r - 1)! (r - 2)! (r - 3)! Определение. Вероятностью наступления какого-либо события называется отношение числа благоприятных исходов к числу всех возможных исходов, предполагаемых равновероятными. (См. [8].) 2.92. В ящике имеется 10 белых и 15 черных шаров. Из ящика вынимаются 4 шара. Какова вероятность того, что все вынутые шары будут белыми 2.93. Пишется наудачу некоторое двузначное число. Какова вероятность того, что сумма цифр этого числа равна 5 2.94. Имеется три ящика, в каждом из которых лежат шары с номерами от 0 до 9. Из каждого ящика вынимается по одному шару. Какова вероятность того, что а) вынуты три единицы; б) вынуты три равных числа 2.95. У игрока в преферанс оказалось 4 козыря, а еще 4 находятся на руках у двух его противников. Какова вероятность того, что козыри лягут а) 2 : 2; б) 3 : 1; в) 4 : 0 (См. также 2.65.) 4. Формула включений и исключений 2.96. Зоопарки. Во всех зоопарках, где есть гиппопотамы и носороги, нет жирафов. Во всех зоопарках, где есть носороги и нет жирафов, 24 2. Комбинаторика есть гиппопотамы. Наконец, во всех зоопарках, где есть гиппопотамы и жирафы, есть и носороги. Может ли существовать такой зоопарк, в котором есть гиппопотамы, но нет ни жирафов, ни носорогов 2.97. Двоечники. В классе имеется a1 учеников, получивших в течение года хотя бы одну двойку, a2 учеников, получивших не менее двух двоек, и т. д., ak учеников, получивших не менее k двоек. Сколько всего двоек в этом классе (Предполагается, что ни у кого нет более k двоек.) 2.98. Пусть имеется n подмножеств A1,..., An конечного множества E и j(x) — характеристические функции этих множеств, то есть 1, x Aj, j(x) = (j = 1,..., n).

0, x E \ Aj Докажите, что при этом (x) — характеристическая функция множества A = A1... An, связана с функциями 1(x),..., n(x) формулой 1 - (x) = (1 - 1(x))... (1 - n(x)).

2.99. Формула включений и исключений. Докажите справедливость равенства |A1 A2... An| = |A1| +... + |An| - |A1 A2| - |A1 A3| -... - |An-1 An| +... + (-1)n-1|A1 A2... An|, где через |A| обозначено количество элементов множества A. (См. также 4.138.) 2.100. Из 100 студентов университета английский язык знают студентов, немецкий — 30, французский — 42, английский и немецкий — 8, английский и французский — 10, немецкий и французский — 5, все три языка знают 3 студента. Сколько студентов не знают ни одного из трех языков 2.101. Каждая сторона в треугольнике ABC разделена на 8 равных отрезков. Сколько существует различных треугольников с вершинами в точках деления (точки A, B, C не могут быть вершинами треугольников), у которых ни одна сторона не параллельна ни одной из сторон треугольника ABC 2.102. Сколько существует целых чисел от 1 до 16 500, которые а) не делятся на 5;

б) не делятся ни на 5 ни на 3;

в) не делятся ни на 5 ни на 3, ни на 11 5. Числа Каталана 2.103. Сколько существует целых чисел от 1 до 33 000, которые не делятся ни на 3 ни на 5, но делятся на 11 2.104. Сколько существует целых чисел от 1 до 1 000 000, которые не являются ни полным квадратом, ни полным кубом, ни четвертой степенью 2.105. Беспорядки. В классе 30 учеников. Сколькими способами они могут пересесть так, чтобы ни один не сел на свое место 2.106. Сколькими способами можно расселить 15 гостей в четырех комнатах, если требуется чтобы ни одна из комнат не осталась пустой 2.107. В комнате площадью 6 м2 постелили три ковра произвольной формы площадью 3 м2 каждый. Докажите, что какие-либо два из них перекрываются по площади, не меньшей 1 м2.

2.108. В прямоугольнике площади 5 расположено 9 фигур площади 1 каждая. Докажите, что найдутся две фигуры, площадь общей части которых не меньше 1/9.

2.109*. В прямоугольнике площади 1 расположено 5 фигур площади 1/2 каждая.

а) Докажите, что найдутся два фигуры, площадь общей части которых не меньше 3/20.

б) Докажите, что найдутся две фигуры, площадь общей части которых не меньше 1/5.

в) Докажите, что найдутся три фигур, площадь общей части которых не меньше 1/20.

2.110. Докажите, что в условии задач 2.109 б) и в) числа 1/5 и 1/нельзя заменить большими величинами.

5. Числа Каталана Во многих комбинаторных задачах решением является последовательность чисел Каталана {Cn} = {C0, C1, C2,... } = {1, 1, 2, 5, 14, 42,... }.

Определение. Пусть имеется n + 1 переменная x0, x1,..., xn, и мы хотим вычислить их произведение при помощи n умножений. Определим число Cn как количество способов расставить скобки в произведении x0 · x1 ·... · xn так, чтобы порядок умножений был полностью определен. Например, при n = 2 существует два способа: x0 · (x1 · x2), (x0 · x1) · x2, а при n = 3 уже 5:

x0 · (x1 · (x2 · x3)), x0 · ((x1 · x2) · x3), (x0 · x1) · (x2 · x3), (x0 · (x1 · x2)) · x3, ((x0 · x1) · x2) · x3.

26 2. Комбинаторика 2.111. Сколько последовательностей {a1, a2,..., a2n}, состоящих из + 1 и - 1, обладают тем свойством, что a1 + a2 +... + a2n = 0, а все их частичные суммы a1, a1 + a2,..., a1 + a2 +... + a2n неотрицательны 2.112. Сколько существует способов разрезать выпуклый (n + 2)угольник диагоналями на треугольники 2.113. Маршруты ладьи. Рассмотрим шахматные доски со сторонами 2, 3, 4,... Требуется провести ладью из левого нижнего угла в правый верхний. Двигаться можно только вверх и вправо, не заходя при этом на клетки главной диагонали и ниже нее. (Ладья оказывается на главной диагонали только в начальный и в конечный моменты времени.) Сколько существует таких маршрутов 2.114. Очередь в кассу. Билеты стоят 50 центов, и 2n покупателей стоят в очереди в кассу. Половина из них имеет по одному доллару, остальные — по 50 центов. Кассир начинает продажу билетов, не имея денег. Сколько существует различных порядков в очереди, таких, что кассир всегда может дать сдачу 2.115. Формула для чисел Каталана. Пусть {a1, a2,..., an} — последовательность целых чисел, сумма которых равна + 1. Докажите, что ровно у одного из ее циклических сдвигов {a1, a2,..., an}, {a2,..., an, a1},..., {an,, a1..., an-1}, все частичные суммы положительны. Выведите отсюда равенства:

1 1 (4n - 2)!!!! Cn = Cn = Cn =, 2n+1 2n 2n + 1 n + 1 (n + 1)! где (4n - 2)!!!! = 2 · 6 · 10... (4n - 2) — произведение, в котором участвует каждое четвертое число. (См. также 3.105.) 2.116. Рекуррентное соотношение для чисел Каталана. Докажите, что числа Каталана удовлетворяют рекуррентному соотношению Cn = C0Cn-1 + C1Cn-2 +... + Cn-1C0.

(См. также 11.92.) Глава Алгоритм Евклида и основная теорема арифметики 1. Простые числа Определение. Натуральное число p называется простым, если p > 1 и p не имеет положительных делителей, отличных от 1 и p.

По соглашению, 1 не является простым числом. Остальные числа, имеющие три и более делителей, называются составными.

3.1. Теорема Евклида. Докажите, что простых чисел бесконечно много.

3.2. Найдите все простые числа, которые отличаются на 17.

3.3. Докажите, что остаток от деления простого числа на 30 — простое число.

3.4. Пусть n > 2. Докажите, что между n и n! есть по крайней мере одно простое число.

3.5. Найдите все такие простые числа p и q, для которых выполняется равенство p2 - 2q2 = 1.

3.6. Докажите, что если число n! + 1 делится на n + 1, то n + 1 — простое число.

3.7. Докажите, что множество простых чисел вида p = 4k + 3 бесконечно. (См. также 4.127.) 3.8. Докажите, что множество простых чисел вида p = 6k + 5 бесконечно. (См. также 4.128.) 3.9. Докажите, что составное число n всегда имеет делитель d n.

3.10. Когда натуральное число n имеет нечетное количество делителей 3.11. Разложите на простые множители числа 111, 1111, 11111, 111111, 1111111. (См. также 4.25.) 28 3. Алгоритм Евклида и основная теорема арифметики 3.12. Докажите, что существуют 1000 подряд идущих составных чисел.

3.13. Докажите, что для любого натурального n найдутся n подряд идущих натуральных чисел, среди которых ровно одно простое.

3.14. Существуют ли а) 5; б) 6 простых чисел, образующих арифметическую прогрессию 3.15. Существуют ли арифметическая прогрессия, состоящая лишь из простых чисел 3.16. Предположим, что нашлись 15 простых чисел, образующих арифметическую прогрессию с разностью d. Докажите, что d > 30000.

Определение. Два простых числа, отличающиеся на 2 называются простыми числами-близнецами.

3.17. Докажите, что 3, 5 и 7 являются единственной тройкой простых чисел-близнецов.

3.18. Найдите все простые числа, которые равны сумме двух простых чисел и разности двух простых чисел.

3.19. Докажите, что при n > 2 числа 2n - 1 и 2n + 1 не могут быть простыми одновременно.

3.20. При каких целых n число n4 + 4 — составное 3.21. Верно ли, что многочлен P(n) = n2 + n + 41 при всех n принимает только простые значения 3.22. Пусть {pn} — последовательность простых чисел (p1 = 2, p2 = 3, p3 = 5,... ). Докажите, что pn > 2n при n 5. При каких n будет выполняться неравенство pn > 3n 3.23. Докажите неравенство pn+1 < p1p2... pn.

3.24. Верно ли, что все числа вида p1p2... pn + 1 являются простыми 3.25. Числа Евклида. Евклидово доказательство бесконечности множества простых чисел наводит на мысль определить рекуррентно числа Евклида:

e1 = 2, en = e1e2... en-1 + 1 (n 2).

Все ли числа en являются простыми (См. также 4.79.) 3.26. Числа Ферма. Докажите, что если число an + 1 простое, то k.

.

a. 2 и n = 2k. (Простые числа вида fk = 22 + 1 называются числами Ферма.

2. Алгоритм Евклида n 3.27. Докажите, что fn делит 2f - 2.

3.28. Докажите, что числа Ферма fn при n > 1 не представимы в виде суммы двух простых чисел.

3.29. Числа Мерсенна. Докажите, что если число an - 1 простое, то a = 2 и n — простое.

Простые числа вида q = 2p - 1 называются числами Мерсенна.

3.30. Пусть Pn(x) = anxn+...+a1x+a0 — многочлен с целыми коэффициентами (n 1, an = 0). Может ли быть так, что при x = 0, 1, 2,...

все числа Pn(x) — простые 2. Алгоритм Евклида Определение. Наибольшим общим делителем (НОД) целых чисел a1,..., an называется такой положительный общий делитель a1,..., an, который делится на любой другой общий делитель этих чисел. НОД чисел a1,..., an обозначается (a1,..., an).

Если наибольший общий делитель чисел a1,..., an равен 1, то эти числа называются взаимно простыми.

3.31. Докажите, что если в наборе целых чисел a1,..., an хотя бы одно отлично от 0, то они имеют наибольший общий делитель.

3.32. В прямоугольнике с целыми сторонами m и n, нарисованном на клетчатой бумаге, проведена диагональ. Через какое число узлов она проходит На сколько частей эта диагональ делится линиями сетки 3.33. Натуральные числа p и q взаимно просты. Отрезок [0; 1] разбит на p + q одинаковых отрезков. Докажите, что в каждом из этих отрезков, кроме двух крайних лежит ровно одно из p + q - 2 чисел 1 2 p - 1 1 2 q -,,...,,,,...,.

p p p q q q 3.34. С 1 сентября четыре школьника начали посещать кинотеатр.

Первый бывал в нем каждый четвертый день, второй — каждый пятый, третий — каждый шестой и четвертый — каждый девятый. Когда второй раз все школьники встретятся в кинотеатре 3.35. В задаче 1.1 доказана возможность деления с остатком произвольного целого числа a на натуральное число b. Докажите, что из равенства a = bq + r следует соотношение (a, b) = (b, r).

3.36. Алгоритм Евклида. Пусть m0 и m1 — целые числа, m1 > и m1 m0. Докажите, что при некотором k > 1 существуют целые числа 30 3. Алгоритм Евклида и основная теорема арифметики a0, a1,..., ak-1 и m2,..., mk такие, что m1 > m2 > m3 >... > mk > 0, ak > 1, m0 = m1 · a0 + m2, m1 = m2 · a1 + m3, m2 = m3 · a2 + m4,..............

mk-2 = mk-1 · ak-1 + mk, mk-1 = mk · ak, и (m0, m1) = mk.

3.37. Докажите, что для любого s от k - 1 до 0 существуют числа us, vs такие, что usms + ms+1vs = d, где d = (m0, m1). В частности, для некоторых u и v выполняется равенство:

m0u + m1v = d.

(См. также 6.67.) 3.38. Пусть (a, b) = 1 и a | bc. Докажите, что a | c.

3.39. Найдите (1.. 1, 1.. 1).

..

m n 3.40. Какое наибольшее значение может принимать наибольший общий делитель чисел a и b, если известно, что a · b = 600 3.41. Натуральные числа a1, a2,..., a49 удовлетворяют равенству a1 + a2 +... + a49 = 540.

Какое наибольшее значение может принимать их наибольший общий делитель 3.42. Можно ли с помощью циркуля и линейки разделить угол на 19 равных частей 3.43. Числа от 1 до 1000 выписаны подряд по кругу. Начиная с первого, вычеркивается каждое 15-е число: 1, 15, 31,..., причем при повторных оборотах, зачеркнутые числа считаются снова. Число оборотов не ограничено. Сколько чисел останутся незачеркнутыми 3.44. Докажите, что (5a + 3b, 13a + 8b) = (a, b).

3.45. Может ли наибольший общий делитель двух натуральных чисел быть больше их разности 3.46. Докажите, что для нечетных чисел a, b и c имеет место равенство b + c a + c a + b,, = (a, b, c).

2 2 2. Алгоритм Евклида 3.47. По окружности радиуса 40 катится колесо радиуса 18. В колесо вбит гвоздь, который ударяясь об окружность, оставляет на ней отметки. Сколько всего таких отметок оставит гвоздь на окружности Сколько раз прокатится колесо по всей окружности, прежде чем гвоздь попадет в уже отмеченную ранее точку 3.48. Для некоторых целых x и y число 3x + 2y делится на 23.

Докажите, что число 17x + 19y также делится на 23.

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

2n + 13 2n2 - 1 n2 - n + а) ; б) ; в).

n + 7 n + n2 + 3.50. При каких целых n сократимы дроби n2 + 2n + 4 n3 - n2 - 3n а) ; б) n2 + n + 3 n2 - n + 3.51. При каких целых n число n4 + 1 n3 + n + а) ; б) n2 + n + 1 n2 - n + также будет целым 3.52. Найдите все натуральные n > 1 для которых n3 - 3 делится на n - 1.

3m - n 3.53. На какие натуральные числа можно сократить дробь, 5n + 2m если известно, что она сократима и что числа m и n взаимно просты.

3.54. Докажите, что при m = n выполняются равенства:

а) (am - 1, an - 1) = a(m,n) - 1 (a > 1); б) (fn, fm) = 1, k где fk = 22 + 1 — числа Ферма. (См. также 3.39, 3.122, 6.69.) n 3.55. Докажите, что число 22 - 1 имеет по крайней мере n различных простых делителей.

3.56. Докажите, что для простых чисел выполняется неравенство n pn+1 22 + 1.

3.57. Докажите, что равенство (a, mn) = 1 равносильно выполнению двух условий (a, m) = 1 и (a, n) = 1.

Pages:     | 1 | 2 || 4 | 5 |   ...   | 27 |






















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

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