Вводный курс по математике для 8 класса.

1. Множества.

Множеством называется совокупность элементов. Два множества равны, если состоят из одних и тех же элементов.

xÎM - x является элементом множества M (x принадлежит M).

xÏM - x не принадлежит M.

Примеры множеств:

Æ - пустое множество (не содержит элементов).

{a} - множество из одного элемента a.

N={1, 2, 3, ...} - множество натуральных чисел.

Z={0, ±1, ±2, ...} - множество целых чисел.

Q={: nÎZ, mÎN} - множество рациональных чисел.

R - множество действительных чисел.

C={x+iy: x, yÎR} - множество комплексных чисел (i²=-1).

Символы N, Z, Q, R, C еще изображаются как (с двойной линией).

Описания множеств Q и C сделано следующим образом: до двоеточия стоит общий вид элемента множества, а после него даются некоторые ограничения на переменные, входящие в это выражение. Иногда вместо двоеточия пишут вертикальную черту "|".

A

Пусть A и B - два множества, тогда:

B

AUB - объединение множеств A и B - множество, состоящее из частей 1, 2, 3.

2

1

3

AIB - пересечение A и B - часть 2. Если AIB=Æ, то говорят, что A и B не пересекаются.

A\B - разность A и B - часть 1. Например, I=R\Q - множество иррациональных чисел.

На рисунке множества A и B изображены кружками. В области, где кружки пересекаются, находятся элементы, принадлежащие обоим множествам. Заметим, что какие-то из частей, обозначенных через 1, 2, 3, могут не содержать элементов.

A

B

AÌB (эквивалентно BÉA) - A вложено в B, A подмножество B.

Например, NÌZÌQÌRÌC.

на этом рисунке A может совпадать с B

1. Дать словесные определения AUB, AIB, A\B и AÌB (укажите какие элементы входят в эти множества). Такие определения более четкие, чем с помощью рисунков.

2. Сколько подмножеств имеет множество из 0, 1, 2, 3, n элементов? (Пустое множество - тоже множество.)

3. Дать определения объединения и пересечения n множеств. Обозначения: A₁UA₂U...UA_n, A₁I A₂I ... IA_n .

Тождеством называется равенство, выполняющееся при любых значениях переменных, входящих в него.

4. а) Доказать тождества: AUBUC=(AUB) UC=AU (BUC). Доказать, что если в выражении A₁UA₂U...UA_n как угодно расставить скобки, то оно равно A₁UA₂U...UA_n.

б) Аналогично, для I.

5. Сколько множеств можно получить из n множеств, используя только операцию U или только операцию I? Требуется найти максимальное количество таких множеств (в некоторых случаях оно меньше максимального, например, когда A₁=Æ или A₁=A₂). Проверить свой ответ при n=1.

6. Доказать тождества с помощью рисунков с кружками:

а) (AUB)\A=B\A;

б) (A\B)U(B\A)=(AUB)\(AIB);

в) C\(AIB)=(C\A)U(C\B).

7. Сформулировать и обосновать метод рисунков для доказательства тождеств для множеств.

8. Можно ли выразить AIB, используя только операцию разности множеств?

9. Можно ли выразить A\B, используя только U и I?

10. Можно ли выразить AUB, используя только \ и I?

11. Доказать, что из AÌB и BÌC следует AÌC.

12. Доказать что выполнение обоих вложений AÌB и BÌA эквивалентно A=B.

13. Доказать, что AÌB эквивалентно A\B=Æ и эквивалентно A=AIB.

2. Логика.

Примеры высказываний: "Идет дождь", "x²>y", "AIB=Æ", "Существует два решения уравнения x²=1". Каждое высказывание является истинным или ложным. "Высказывание", не являющееся ни истинным и ни ложным или истинным и ложным одновременно, является некорректным и не считается высказыванием.

1. Показать, что "высказывание" "Это высказывание ложно" не может быть ни истинным, ни ложным, поэтому не является высказыванием.

Пусть A и B - два высказывания, тогда:

(другое обозначение - ùA) - не A, отрицание A, утверждение о том, что A ложно.

AÚB - утверждение о том, что выполняется A или B (возможно, выполняются оба).

AÙB - утверждение о том, что выполняется и A и B.

AÞB (другое обозначение - A®B) - из A следует B. При краткой записи заменяет слово "следовательно". Примечание: из ложного высказывания следует любое высказывание.

AÛB (другое обозначение - A«B) - A эквивалентно B, заменяет выражение "тогда и только тогда".

Ú - дизъюнкция (от лат. disjunctio - разобщение, разделение, различие).

Ù - конъюнкция (от лат. conjunctio - союз, связь).

Þ - импликация (лат. implicato - сплетение от implico - тесно связываю).

2. Обозначим буквой И истинное высказывание, а буквой Л - ложное. Упростить выражения.

AÚИ	AÙИ	AÚ	AÞИ	ИÞA
AÚЛ	AÙЛ	AÙ	AÞЛ	ЛÞA

3. Дать определение операций "или" и "и" для n высказываний. Обозначения: A₁ÚA₂Ú...ÚA_n, A₁ÙA₂Ù...ÙA_n.

4. а) Доказать: AÚBÚC=(AÚB)ÚC=AÚ(BÚC). Докажите, что если в выражении A₁ÚA₂Ú...ÚA_n как угодно расставить скобки, то оно равно A₁ÚA₂Ú...ÚA_n.

б) Аналогично, для Ù.

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

а) =? б) =? в) =?

6. Выразить AÚB через Ù и ù и, наоборот, AÙB через Ú и ù.

7. В каком случае неверно AÞB?

8. Доказать:

а) AÞB = Þ = = ÚB;

б) ((AÞB)Ù(BÞC)) Þ (AÞC);

в) AÛB = (AÞB)Ù(BÞA) = (AÞB)Ù(Þ) = (BÞA)(Þ) - это различные способы доказательства эквивалентности двух утверждений;

г) AÚ(BÙC)=(AÚB)Ù(AÚC); д) AÙ(BÚC)=(AÙB)Ú(AÙC).

9. Путем преобразований, то есть цепочки равенств, используя доказанные тождества, получить: а) ; б) =Л.

Укажем на связь логических операций Ú и Ù и операций над множествами U и I:

xÎAUB Û xÎA Ú xÎB;

xÎAIB Û xÎA Ù xÎB.

10. Пользуясь логическим тождеством 8 г), доказать аналогичное тождество для множеств: AU(BIC)=(AUB)I(AUC).

11. Обосновать перевод произвольного логического тождества, содержащего только Ú и Ù, в тождество для множеств заменой Ú на U и Ù на I.

Кванторы:

" - квантор всеобщности, заменяет слово "любой".

$ - квантор существования, заменяет слово "существует".

$! - "существует и единственен".

" - перевернутое A (от англ. any - любой).

$ - перевернутое E (от англ. to exist - существовать).

12. Прочитать следующие высказывания и определить, истинны ли они.

а) "x $y: x+y=0. Это обозначает то же самое, что и

"x($y(x+y=0)) или "x: A(x), где A(x)=$y: x+y=0. Изменится ли смысл этого высказывания, если поменять кванторы местами: $y "x: x+y=0?

б) "x,y,zÎR: (x+y)+z=x+(y+z). в) "x¹0 $!y: xy=1.

13. Записать с помощью кванторов: "Для любого положительного числа y существует действительное число x такое, что x²=y".

14. Найти эквивалентную запись следующих высказываний, не содержащую общего отрицания. (A(x) - высказывание, зависящее от x.)

а) =? б) =? в) =? г) =?

15. Что обозначает знак "=" в этом параграфе?

3. Логика и множества.

1. Пусть f(x)=x², g(x,y)=x²-y². g(x,y) - функция от двух переменных, для каждой пары своих аргументов x и y она дает значение x²-y². Найти g(2,1), g(1,y), g(x,x), g(f(x),g(y,z)).

AÚB является функцией от двух логических переменных A и B, каждая из которых может принимать два значения - "истина" и "ложь", обозначим их через 0 и 1. Значение этой и других логических функций можно дать в виде таблицы:

2. Заполнить таблицу. С помощью нее доказать тождество AÞB = ÚB.

3. Дать определение логической функции от n переменных. Сколько существует таких функций при фиксированном n?

4. Существует ли общий способ проверить логическое тождество?

5. Доказать, что любую логическую функцию можно выразить через отрицание, конъюнкцию и дизъюнкцию (с учетом задачи 2.6 - через Ú и ù или через Ù и ù).

6. Какой логической функции соответствует A\B? Заполнить таблицу и объяснить, что она означает.

7. Сколько различных множеств можно получить из n множеств, используя операции U, I и \, с той же оговоркой, что и в задаче 1.5?

8. Существует ли общий способ проверить тождество для множеств?

9. Пусть есть логическое тождество, использующее только операции Ú, Ù и ù и знаки И и Л. Доказать, что оно останется тождеством, если заменить Ú на Ù, Ù на Ú, И на Л и Л на И. Для доказательства рассмотреть замену 0 на 1 и 1 на 0.

10. Пусть есть какое-то равенство, содержащее три множества: A, B и C. Если вместо C в этом равенстве всюду подставить A, то оно станет тождеством (то есть будет выполняться при любых A и B). Так же оно станет тождеством, если вместо C подставить B. Доказать, что оно станет тождеством, если вместо C подставить AUB или вместо C подставить AIB. Сформулировать и доказать логический аналог этой задачи.

Итак, существует пять методов доказательства логических тождеств и тождеств для множеств: 1) с помощью рисунков с кружками (задача 1.6); 2) таблиц (3.3, 3.5); 3) рассуждений (1.4, 2.4, 2.5, 2.8, 3.10); 4) преобразований (2.9, 2.14 в, г); 5) перевода из логики в множества и наоборот (2.10, 2.11, 3.11).

4. Векторы.

Вектор задается длиной и, в случае если она не равна нулю, - направлением. Можно рассматривать векторы на плоскости и в пространстве. Варианты обозначения вектора: a, , ; а его длины: a, |a|. Нулевой вектор (a=0) - вектор с нулевой длиной.

Из любой точки A можно отложить единственным образом отрезок AB заданной длины и направления. Такой отрезок задает вектор =a. Говорят, что вектор AB отложен от точки A, A - начальная точка вектора, B - конечная. Два вектора и равны, если имеют одинаковую длину и направление. Одинаковость их направления можно определить как параллельность и сонаправленность лучей [AB) и [CD), при этом требуется иметь определение сонаправленности лучей. Определение равенства двух векторов можно еще дать следующим образом: =, если ABDC - параллелограмм или, в случае, когда точки A,B,C,D лежат на одной прямой - вырожденный параллелограмм.

Суммой двух векторов AB и BC называется вектор : +=.

1. Доказать, что сумма векторов a и b не зависит от выбора точки, от которой откладывается вектор a.

2. Построить сумму векторов и . Доказать, что +=+ (коммутативность сложения векторов). Говорят, что вектора складываются по правилу параллелограмма.

Обратным (противоположенным) вектором к a называется вектор b, удовлетворяющий условию a+b=0. Вектор b обозначается как -a.

3. Какой вектор является обратным к ? Доказать единственность обратного вектора.

Разностью векторов a и b называется вектор a-b=a+(-b).

4. Построить разность векторов и .

Произведением вектора a на число k называется вектор ka, имеющий то же или противоположенное, в случае отрицательного k, направление и длину |ka|=|k| |a|. Определение произведения вектора на число можно еще дать следующим образом. Если a=0, то ka=0. Если a¹0, то с вектором =a связана координатная ось с нулем в точке A и направлением от точки A к точке B. Возьмем точку C на этой оси с координатой k|a|. Тогда =k. Это определение лучше тем, что в нем не рассматривается два случая: k>0 и k<0.

5. Доказать: (-1)a=-a.

6. Пусть на плоскости задана система координат. Доказать, что разность координат конечной и начальной точки вектора: a₁=x_B-x_A и a₂=y_B-y_A не зависит от положения вектора.

Таким образом, каждому вектору на плоскости можно поставить в соответствие пару чисел - , аналогично, в пространстве - три числа - . Кроме того, любой паре чисел соответствует единственный вектор (см. рис.), аналогично, в пространстве любой тройке чисел соответствует единственный вектор. Числа a₁, a₂ или a₁ ,a₂ ,a₃ называются координатами вектора, а представление вектора как или - координатным представлением.

7. Доказать: +=; k=, то есть, что вектора складываются и умножаются на число покоординатно.

8. Через координатное представление доказать:

a+b=b+a - коммутативность,

(a+b)+c=a+(b+c) - ассоциативность,

k(a+b)=ka+kb, (k+r)a=ka+ra, (kr)a=k(ra).

В следующих задачах под проекцией вектора на прямую или на плоскость будем понимать вектор , где A₁ - проекция точки A, а B₁ - проекция точки B.

Часто под проекцией вектора понимают длину вектора , то есть, неотрицательное число.

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

9. Проекция вектора не зависит от выбора начальной точки вектора и одинакова при проектировании на две параллельные прямые и на две параллельные плоскости. Доказать только случай проектирования на прямую для векторов на плоскости.

10. Доказать для того же случая, что и в предыдущей задаче:

а) проекция суммы векторов равна сумме проекций;

б) проекция произведения вектора на число равна произведению проекции этого вектора на это число.

11. Доказать, что вектор на плоскости равен сумме своих проекций на две перпендикулярные прямые.

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

12. Разложить вектор на проекции на оси координат X, Y, Z и на проекции на ось X и плоскость YZ.

5. Скалярное произведение векторов.

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

1. Как выглядит координатное представление вектора в n-мерном пространстве?

Скалярным произведением двух векторов a и b называется действительное число (a,b)=|a||b|cosa, где a - угол между векторами a и b. Угол между двумя векторами однозначно определен в пространстве любой размерности: в плоскости, содержащей оба вектора, берется тот угол между ними, который меньше или равен 180.

Скалярное произведение можно обозначать как ab. Это обозначение более краткое, но в сложных выражениях оно может привести к трудности чтения, например: a(bc)d=(a,(b,c)d).

2. При каких a и b (a,b)=0, (a,b)>0, (a,b)<0 ? Когда (a,b) достигает максимума, минимума при фиксированных |a| и |b|?

3. Пусть b¹0. Доказать, что (a,b)=(a_b,b)=a_bb, где a_b - проекция a на b, понимаемая как вектор (см. рис.), а a_b - проекция a на b, понимаемая, как число, положительное, в случае, когда a и b сонаправлены, и отрицательное, когда a и b противоположено направлены.

4. Доказать:

а) (a,b)=(b,a) - коммутативность скалярного произведения;

б) (ka,b)=k(a,b);

в) (a+b,c)=(a,c)+(b+c) (через задачу 3).

5. Обозначим через e_i вектор, у которого все координаты, кроме i-ой равны нулю, а i-ая равна 1. Такой вектор называется i-ым координатным вектором. Найти (e_i,e_j) в случаях, когда i=j и когда i¹j.

6. Пусть a=, b=. Найдите (a,b), используя задачи 4б),в) и 5.

7. Выразить |a|, используя скалярное произведение.

8. Выразить a_b и a_^b через a и b, используя скалярное произведение (см. рис.).

9. Доказать теорему косинусов, используя векторы и скалярное произведение.

6. Преобразование формул.

Введем обозначения суммы и произведения n чисел a₁,a₂,...a_n:

=a₁+a₂+...+a_n, =a₁+a₂+...+a_n.

Например: ²+=1²+2²+3²+...+n², =1×2×3×...×n=n! ("n факториал", 0!=1).

1. Показать, что: =, =c+, =.

2. Выразить через факториал:

а) m(m+1)(m+2)...n; б) 2×4×6×...×2n; в) 1×3×5×...× (2n-1).

Произведение четных чисел от 2 до n при четном n и произведение нечетных чисел от 1 до n при нечетном n обозначается как n!! (n!!¹(n!)!).

3. Найти . Указание: .

4. Представить в виде , где a и b не зависят от x.

5. Найти: . (Воспользоваться предыдущей задачей.)

6. Доказать, что "x: ax²+bx+c=a₁x+b₁x+c₁ Û a=a₁, b=b₁, c=c₁.

7. Доказать, что "a,b,c $d,h: ax²+bx+c=a(x-d)²+h. Выразить d и h через a, b и c. При каком x достигается максимум или минимум (в зависимости от знака a) ax²+bx+c и чему он равен?

8. x+y=c. При каких x и y достигается максимум xy и чему он равен?

9. При каком x достигается минимум ?

10. Доказать: |x-a|<b Û a-b<x<a+b.

11. Доказать: а) |x+y|<|x|+|y|; б) |x₁+x₂ +...+x_n|<|x₁|+|x₂|+...+|x_n|.

12. Освободиться от радикалов в знаменателе: . Рассмотреть случаи x=y и x¹y.

13. Решить уравнение: .

14. Доказать: (x³1).

15. "xÎR: f(2x+6)=4x+5. f(3x+1)=?

7. Графики.

Графиком называется некоторое множество точек на координатной плоскости. В виде графика можно изобразить любое множество пар чисел (x,y), например, множество пар (x,y), удовлетворяющих уравнению y=2x+1, в общем случае - множество пар (x,y), для которых истинно высказывание A(x,y), зависящее от x и y.

Графиком функции f(x) называется график, определяемый уравнением y=f(x).

Заметим, что любой график можно задать одной функцией от двух переменных f(x,y) с помощью соотношения f(x,y)=0. Для этого выберем эту функцию следующим образом: f(x,y)=.

(По определению функция должна давать значение для каждой пары x и y, но не обязана иметь выражение через известные функции.)

Если на графике на какой-то линии отсутствует точка (выколотая точка), то она изображается кружком. Сплошные области точек, принадлежащих графику, штрихуются. Если линия границы такой области не принадлежит графику, то она изображается пунктиром.

1. Построить графики функций [x] - целая часть x и {x} - дробная часть x, определяемых условиями: "xÎR: x=[x]+{x}, [x]ÎZ, {x}Î[0;1).

2. Пусть известен график, задаваемый высказыванием A(x,y) (на графике изображены точки, имеющие координаты (x,y), для которых A(x,y) истинно). Как в тех же координатных осях получить график, задаваемый высказыванием B(x,y), если:

а) B(x,y)=A(x+a,y)

B(x,y)=A(x-a,y)

B(x,y)=A(x,y+a)

B(x,y)=A(ax,y)

B(x,y)=A(,y)

B(x,y)=A()

B(x,y)=A(ax+x₀, by+y₀)

б) B(x,y)=A(|x|,y)

B(x,y)=A(|x|,|y|)

в) B(x,y)=A(y,x)

г) B(f(x,y), g(x,y))=A(x,y), где f(x,y) и g(x,y) – какие-то функции.

3. Как, зная график функции f(x), построить графики:

а) f(x+a), f(x-a), f(ax), af(x);

б) f(|x|), |f(x)|, |y|=f(|x|);

в) x=f(y); г) y³f(x).

4. Изобразить функцию f(x)+x на одном графике с функцией f(x), показанной на рисунке.

5. Построить графики:

а) y=|x|, |y|=x, |y|=|x|;

б) (см. задачу 6.10);

в) x²+y²=25.

6.

Найти соотношения, задающие следующие графики:

7. Как построить график y=a(x-d)²+h ? Построить графики y=2x²-2x-1 и y=3x²-4x+2.

8. Каким свойством обладают графики квадратных трехчленов y=ax²+bx+c в точке x=0 в следующих случаях: c=0, c<0, c>0, b=0, b<0, b>0. Определите знаки коэффициентов a, b, c для графиков квадратных трехчленов, показанных на рисунке.

8. Последовательности.

{a₁, a₂, a₃,...}={a_n} - числовая последовательность. Обозначение для последовательности {a_n} - немного нестрогое, но удобное.

Последовательность можно задать формулой ее n-ого члена: a_n=f(n) или с помощью рекуррентной формулы: a_n=f(n, a_n-1, a_n-2,..., a₁).

Рекуррентно определим следующие последовательности:

	Арифметическая прогрессия (АП). d называется разностью прогрессии.
	Геометрическая прогрессия (ГП). q называется знаменателем прогрессии.
	Числа Фибоначчи.

1. Найти формулы n-ого члена АП и ГП.

2.

n

Доказать: a_n=, b_n = , где {a_n} - АП, {b_n} - ГП.

3. Найти 1+2+3+...+n. Указание: найти количество клеточек в фигуре:

4. Найти сумму первых n членов АП.

5. Найти произведение первых n членов ГП.

6. Найти 1+x+x²+...+xⁿ. (Как разлагается xⁿ-1 на множители?)

7. Найти сумму первых n членов ГП.

8. Найти формулу n-ого члена последовательности .

9. Найти сумму 1+2x+3x²+4x³...+(n+1)xⁿ. Указание k=.

10. Найти .

11. Найти . Результат выразить одной формулой, используя целую часть - [ ].

12. а) Найти все ГП, удовлетворяющие свойству: a_n+2=a_n+1+a_n (*).

б) Показать, что если две последовательности {a_n} и {b_n} удовлетворяют свойству (*), то сумма этих последовательностей - последовательность {a_n+b_n} - тоже удовлетворяет этому свойству.

в) Представить последовательность чисел Фибоначчи в виде суммы двух ГП, удовлетворяющих свойству (*). Получить формулу для n-ого числа Фибоначчи.

9. Индукция.

1. Доказать, что длина ломаной больше длины отрезка, соединяющего ее концы.

Решая данную задачу, вы явно или не явно использовали метод математической индукции. Этот метод заключается в следующем. Пусть A₁, A₂, A₃,... - последовательность высказываний, тогда:

.

Доказательство A₁ называется базой, а доказательство A_nÞA_n+1 - шагом индукции. Решение задачи по индукции может быть кратко записано в виде: "База: ... Шаг: ...".

2. Проверить справедливость следующих рассуждений по индукции. Как исправить неверные?

а) ; б)

в)

г) (n,mÎN) - система высказываний, пронумерованных двумя индексами

д) ;

е)

3. Доказать по индукции: 1+2+3+...+n=. (Это утверждение можно принять за A_n.)

4. Доказать неравенства.

а) (1-a₁)(1-a₂)...(1-a_n)>1-a₁-a₂-...-a_n, где 0<a_i<1, n³2;

б) неравенство Бернулли: (1+a)ⁿ>1+na, где a³-1, nÎN;

в) , где nÎN, n³2;

г) .

5. При каких натуральных n справедливо неравенство 2ⁿ>10n²?

6. На сколько частей делят плоскость n прямых в общем случае? Какие варианты расположения прямых не входят в общий случай?

10. Комбинаторика и теория вероятности.

1. Сколько существует n-буквенных слов? В алфавите m букв.

2. Перестановкой называется расположение в каком-то порядке элементов конечного множества, например, (4, 1, 3, 5, 2) - перестановка чисел от 1 до 5. Сколько существует перестановок из n элементов?

3. Сколькими способами можно выбрать m предметов из n? Это число обозначается - "це из n по m".

4. Доказать: =+, . Использовать не формулу , а определение этой величины, данное в предыдущей задаче.

5. Чему равны и ? Заполните следующую таблицу числами . Эта таблица называется треугольником Паскаля.

6. Найти коэффициент при x^m после раскрытия скобок в выражении (x+1)ⁿ. Этот коэффициент называется биномиальным, а формула (x+y)ⁿ="выражение после раскрытия скобок" - биномом Ньютона. Указание: сколькими способами можно выбрать m иксов из n скобок в выражении ?

7. Сколькими способами можно разбить множество из n элементов на k групп, состоящих из n₁, n₂,...n_k элементов (n₁+n₂+...+n_k=n)?

8.

n карт | | | |

Найти коэффициент при x^my^k в (x+y+1)ⁿ после раскрытия скобок.

9. Сколько существует способов:

n шариков

m карт | | | | | |

а) слить две колоды из n и m карт так, чтобы карты каждой колоды остались в том же порядке;

m ящиков

б) разложить n одинаковых шариков по m ящикам;

в) выбрать m шариков, имеется неограниченное число шариков n цветов;

n

m

г) пройти из нижней левой вершины прямоугольника n´m клеток в верхнюю правую, двигаясь только вверх и вправо по нарисованным линиям?

10. На окружности n точек. Сколько существует различных незамкнутых самонепересекающихся ломаных, у каждой из которых вершинами являются эти n точек?

11. Сколько существует бус из 7 бусинок n цветов? Двое бус одинаковы, если они совпадают при некотором повороте (переворачивать бусы нельзя).

Вероятность какого-то события - действительное число от 0 до 1.

0 - вероятность невозможного события;

1 - вероятность обязательно происходящего события;

- вероятность события, происходящего и не происходящего с одинаковой вероятностью.

12. Чему равна вероятность того, что при 12 подбрасываниях монеты 6 раз выпадет орел и 6 раз решка?

13. Имеется n шаров, каждый из которых с вероятностью p - белый. Какова вероятность, что среди них а) хотя бы один белый; б) ровно m белых?

11. Делимость. Сравнения по модулю.

Пусть nÎZ, mÎN. Дадим следующие определения.

nm - n делится на m (m делит n, m - делитель n) Û $kÎZ: n=km.

n mod m=k - n модуль m равно k (остаток от деления n на m равен k) Û n-km, 0£k<m.

nºk (mod m) - n равно k по модулю m, (n сравнимо с k по модулю m) Û n-km.

1. ab, bc Þ ac.

2. "nÎZ "mÎN $!k: n mod m = k.

3. nºk (mod m) Û n mod m = k mod m.

4. nºkºp (mod m) Þ nºp (mod m).

5. aºb, cºd (mod m) Þ a+cºb+d, acºbd (mod m).

6. Доказать,что f(n₁,...n_k) mod m = f(n₁ mod m,... n_k mod m) mod m, где в функции f используется только сложение, умножение и целые константы. Как можно представить n₁-n₂ в виде такой функции?

7. Таблицей умножения по модулю n называется таблица, которая для любых двух чисел i и j от 0 до n-1 дает ij mod m. Нарисуйте таблицу умножения по модулю 6. Какими симметриями она обладает? Этими же симметриями обладает таблица умножения по модулю любого числа. Почему?

8. (m-k)ⁿº(-1)ⁿkⁿ (mod m).

9. Найти все целые решения уравнения 2x³-x²º2 (mod 7).

10. Доказать, что 20ⁿ+16ⁿ-3ⁿ-1323 при четных n. Рассмотреть сравнения по модулю 17 и 19. Если число делится на 17 и на 19, то оно делится и на 17×19=323. Строго это следует из задачи 12.5.

Десятичное представление натурального числа – m=, где a_kÎ{0,1,...9} - десятичная цифра.

11. Дать определение двоичного представления натурального числа. Представить число 53 в двоичной системе счисления и число 1100100₂ (двоичная система счисления) - в десятичной.

12. Как зависит 10ⁿ mod m при m=3,9,11,7 от n? Доказать:

а) ºa_n+a_n-1+…+a₀ (mod 3);

б) ºa_n+a_n-1+…+a₀ (mod 9);

в) º(a₀+a₂+a₄+…)-(a₁+a₃+a₅+…) (mod 11);

г) найти такого же вида равенство по модулю 7.

13. Как по последней цифре и четности предпоследней определить n mod 4?

14. 7²⁰⁰⁰ mod 10 =?

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

а) a_n=f(a_n-1, a_n-2, ... a_n-k); б) a_n=f(n, a_n-1, a_n-2, ... a_n-k),

где функция f имеет такой же вид, как в задаче 6 и рассматривается не последняя десятичная цифра, а остаток от деления на m. Найти ограничение на количество чисел в периоде в зависимости от m и k.

12. Делимость. Основная теорема арифметики.

В следующих определениях все числа натуральные.

n - составное число

p - простое число Û p не составное число и не 1.

P - множество простых чисел - {2,3,5,7,11,13,17,19,...}.

n и m взаимно просты Û n и m не имеют общих делителей, кроме 1.

1. Различные простые числа взаимно просты.

Разложением на простые множители натурального числа n называется его представление в виде: n=1: 1=1.

2. Любое натуральное число имеет разложение на простые множители.

Основная теорема арифметики. У любого натурального числа разложение на простые множители единственно.

p₃

p₂

p₁

p₄

Единственность разложения на простые множители не является очевидным фактом, например, не очевидно, что не может быть , где - различные простые числа, то есть, что не может быть два прямоугольника и клеток, с одинаковым числом клеток.

3. Восстановите подробности в следующем доказательстве основной теоремы арифметики. Допустим, что некоторые числа раскладываются на простые множители не единственным образом. Возьмем из них минимальное: n=p₁a=p₂b, где p₁, p₂P, p₁>p₂, a не делится на p₂. Тогда число (p₁‑p₂)a=(b‑a)p меньше n и имеет неединственное разложение на простые множители.

4. Найти разложение на простые множители 337500.

5. na, nb, a и b взаимно просты Þ nab.

6. Как определить наибольший общий делитель (НОД) и наименьшее общее кратное (НОК) двух чисел, зная их разложение на простые множители?

7. Алгоритм Евклида. Доказать, что НОД(a, b)=НОД(a, b-a)=НОД(a-b, b). Используя это, найти эффективный алгоритм определения НОД(a, b). Разложение на простые множители более трудоемко.

8. Найти НОД(1457,1891).

9. Китайская теорема об остатках. Пусть натуральные числа m₁, m₂,… m_k попарно взаимно просты. Тогда найдется целое число n, дающее заданные остатки при делении на m₁, m₂,… m_k. Для доказательства теоремы доказать, что среди чисел 0, 1, 2,... m₁m₂...m_k-1 любая комбинация остатков встретится ровно один раз.

10. Доказать, что простых чисел бесконечно много.

11. Доказать: "k $n: n, n+1, n+2, ... n+k-1 - составные числа. Найти n(k), то есть такую функцию, которая для каждого k, дает n, удовлетворяющее написанному условию.