Задачи для самостоятельного решения

1. На железнодорожной станции есть 5 светофоров. Сколько может быть дано различных комбинаций их сигналов, если каждый светофор имеет два состояния?

2. Сколькими способами 10 человек могут встать в очередь друг за другом?

3. Сколько хорд можно провести через 6 точек, лежащих на одной окружности?

4. В классе 30 учеников. Ежедневно двое из них дежурят. Можно ли составить расписание дежурства так, чтобы никакие два ученика не дежурили вместе дважды в течение года?

5. У хозяйки имеется 4 чашки, 5 блюдец и 6 чайных ложек. Сколькими способами может быть накрыт стол для чаепития на трех человек?

6. В НИИ работают 67 человек. Из них 47 человек знают английский язык, 35 – немецкий язык, 23 человека знают оба языка. Сколько человек не знают ни английского, ни немецкого языка?

7. В состав сборной включены: 2 вратаря, 5 защитников, 6 полузащитников, 6 нападающих. Сколькими способами тренер может выставить команду: 1 вратарь, 3 защитника, 4 полузащитника, 3 нападающих?

8. Сколько различных «слов» можно составить, переставляя буквы слова «МИССИСИПИ»?

9. Группа шахматистов сыграла между собой 28 партий. Каждые два из них встречались между собой один раз. Сколько шахматистов участвовало в соревновании?

10. В магазине имеется 7 видов тортов. Сколькими способами можно составить набор, содержащий три торта?

11. Сколькими различными способами можно распределить поровну 12 различных учебников между четырьмя студентами?

12. Сколько имеется пятизначных чисел, все цифры у которых различны?

13. Группа туристов из 12 юношей и 7 девушек выбирает по жребию 5 человек для приготовления ужина. Сколько существует способов, при которых в эту «пятерку» попадут: а) одни девушки, б) 1 юноша и 4 девушки?

14. Сколько различных комбинаций из 6 карт содержат 3 дамы, 2 короля и 1 туза?

15. Сколько различных «слов», состоящих из трех букв, можно образовать из букв слов: а) лето, б) шалун?

Ответы

1. комбинации, 2. способов, 3. хорд, 4. Можно, т. к. существует 435 способов назначения дежурных 5. способов, 6. 8 человек, 7. 6000 способов, 8. 2520 слов, 9. 8 шахматистов, 10. 84 возможности, 11. 369600 способов, 12. 27216 чисел, 13. а) 21, б) 420, 14. 96 комбинаций, 15. а) 24, б) 60.

Раздел 6. Алгебраические структуры Теоретические сведения

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

Бинарную операцию на M обозначают каким-нибудь специальным символом: , , или .

Примеры: Какие из арифметических действий - сложение, вычитание, умножение, деление – являются бинарными операциями на следующих множествах: 1) N – множество натуральных чисел; 2) Z - множество целых чисел?

Решение: 1) N – множество натуральных чисел

сложение: N выполняется N , следовательно, сложение является бинарной операцией на N

вычитание: N N (например, N), следовательно, вычитание не является бинарной операцией на N

умножение: N имеет место N, следовательно, умножение – бинарная операция

деление: ( N) N (например, N), следовательно, деление – не бинарная операция.

2)Z – множество целых чисел:

Z имеет место Z, Z, Z, сложение, вычитание и умножение являются бинарными операциями на множестве целых чисел. Но Z, следовательно, деление не является бинарной операцией.

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

Так, например, на множестве Z целых чисел помимо естественных операций +, · (сложение и умножение) легко указать получающиеся при помощи +, -, · «операции»: , и т.д. Таким образом, мы приходим к различным алгебраическим структурам (Z, +), (Z,·), ( Z, ), ( Z, ).

Бинарная операция на множестве A называется коммутативной, если для любых двух элементов выполняется .

Операция определенная на множестве A называется ассоциативной, если для любых трех элементов из множества A выполнено .

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

Если нейтральный элемент существует, то он единственный.

Элемент b из множества A называется обратным к элементу a из того же самого множества, если и .

Обратные элементы используются для построения обратных операций.

Пусть на множестве задана операция . Эта операция называется обратимой, если для любых элементов a,b из множества A каждое из уравнений , имеет единственное решение в множестве A.

Примеры:

I алгебраическая система (R, +, 0), здесь 0 – нейтральный элемент

II алгебраическая система (R₊, ·,1), 1 – нейтральный элемент.

Множество G элементов произвольной природы с заданной на нем бинарной операцией : (ее чаще всего называют умножением), называется группой, если выполнены следующие аксиомы:

1. ассоциативность: для любых ;

2. наличие нейтрального элемента: в G существует элемент e , такой что для всех x из G справедливо ;

3. обратный элемент: для каждого x из G найдется элемент x^-1 из G , называемый обратным, такой, что .

Часто используют одну из двух терминологий:

1. – умножение. Тогда группу называют мультипликативной группой. В этом случае e – единица, g^-1- обратный элемент

2. - сложение. Тогда группу называют аддитивной группой. Здесь e =0, (-g) – противоположный элемент.

Если для любых выполняется , то группа называется коммутативной или абелевой.

Группу, состоящую из конечного числа элементов, называют конечной, а число элементов в ней – порядком группы и обозначают , и бесконечной, если множество элементов бесконечно.

Подмножество называется подгруппой в группе G, если это подмножество само является группой относительно той же бинарной операции:

1. ;

2. ;

3. /

Подгруппа – собственная, если и

Примеры: Выясните, какие из нижеприведенных множеств являются группами относительно указанных операций:

1. (R, +, 0)

Проверяем является ли эта система группой: выполняется . Следовательно, сложение является бинарной операцией на . Проверяем аксиомы:

1. ассоциативность: выполняется;

2. 0- нейтральный элемент: - выполняется

3. Обратный элемент: существует так что – выполняется.

Следовательно, (R, +, 0) является группой.

2. М – множество невырожденных матриц второго порядка относительно операции умножения: , где

Для любых матриц А,В имеет место . Проверяем аксиомы:

1. ассоциативность: произведение матриц ассоциативно, т.е. для любых матриц выполняется

2. в качестве нейтрального элемента возьмем - единичную матрицу. В самом деле имеет место

3. наличие обратного элемента: для любой невырожденной матрицы (detA=ad-bc ) существует обратная матрица: , где А_11, А_12, А_21, А₂₂ – алгебраические дополнения. Следовательно, множество невырожденных матриц второго порядка относительно операции умножения является группой. Однако операция умножения матриц не является коммутативной ( ). Поэтому данная группа не является коммутативной.

3. Множество целых чисел Z относительно вычитания./

Проверим, что операция «вычитание» является бинарной: Z имеет место Z. Проверяем выполнимость аксиом:

1. Ассоциативность: . Видим, что первая аксиома ассоциативности не выполняется.

Следовательно, множество целых чисел с заданной операцией «вычитание» не является группой.

4. Множество четных чисел относительно операции умножения.

Произведение четных чисел является четным числом: (2k₁k₂=2·2k₁k₂). Поэтому проверим выполнимость аксиом:

1. Ассоциативность: - выполняется;

2. Наличие нейтрального элемента: . При операции «умножение» этому условию удовлетворяет нейтральный элемент . Но 1 не принадлежит множеству четных чисел. Следовательно, аксиома о наличии нейтрального элемента не выполняется.

Поэтому, множество четных чисел с операцией «умножение» не является группой.