ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ. Задача 1.Дама имеет 8 платьев, 5 пар туфель и 7 шляпок, причем она считает, что все это сочетается одно с другим

Задача 1.Дама имеет 8 платьев, 5 пар туфель и 7 шляпок, причем она считает, что все это сочетается одно с другим. Сколькими способами дама может одеться?

Задача 2. Известно, что в троичной системе только три цифры: 0,1,2. Сколько всего существует четырехзначных троичных чисел?

Задача 3.Мобильный номер Билайн – это десятизначное число, начинающееся с девятки, а вторая цифра 0 или 6. Сколько всего существует мобильных номеров Билайн? Хватит ли их для всего населения России?

Задача 4. Мама приготовила на обед салат, суп, второе и компот. Капризная дочь любит менять порядок этих блюд. Сколькими способами дочь может пообедать, если все блюда она обязана съесть? А если она может съесть лишь часть блюд?

Задача 5.Требуется составить пятибуквенное слово русского языка из букв А,Д,К,С,О. Студент перебирает всевозможные варианты (ОКАДС, АКОДС и т.д.). Сколько всего вариантов ему предстоит перебрать?

Задача 6.В финальном заплыве стартуют 8 пловцов, им приготовлены золотая, серебряная и бронзовая медали. Сколько вариантов распределения медалей теоретически существует?

Задача 7.Вася помнит, что номер домашнего телефона у Маши шестизначный, начинается он на 56, и что все шесть цифр различны. Сколько телефонных звонков надо сделать Васе, чтобы гарантированно найти Машу?

Задача 8.Турист решил взять из своей библиотеки (в которой 30 книг) три книги с собой в отпуск. Сколькими способами он может это сделать? А если он решил взять не более трех книг?

Задача 9.В студенческой группе 10 юношей и 8 девушек. Требуется отобрать команду на спартакиаду по шахматам, в которой должно быть 3 юношей и 2 девушки. Сколькими способами это можно сделать?

Задача 10.У ребенка имеются таблички с цифрами 2,2,3,3,3,3,7,7,7. Он пытается сложить из них 9-значное число. Сколькими способами он может это сделать?

Задача 11*.1. Число 10 разбивают на сумму трех натуральных чисел, например, 3+3+4 или 5+2+3. Сколькими способами это можно сделать (перестановка слагаемых считается как разные способы, т.е. 3+3+4 и 3+4+3 мы различаем)? 2. То же, но слагаемые могут быть и нулевые: 6+0+4 (по-прежнему мы отличаем это от 4+6+0).

Задача 12*. Какова мощность множества всех пятизначных чисел, у которых НЕ все цифры различны?

Задача 13*.В городе М существуют всевозможные семизначные телефонные номера (начинающиеся с 1,2,3,…,9). Номер называется счастливым, если в нем содержатся три (но не четыре!) семерки подряд, например, 1777277. Сколько всего существует счастливых номеров?

Задача 14*.Автобусный билет – это число а₁ а₂ а₃ а₄ а₅ а₆, где все цифры а_k от 0 до 9. Билет называется строго возрастающим, если а₁ <а₂ <а₃ <а₄ <а₅ <а₆. Какова мощность множества всех строго возрастающих билетов?

Отношение на множестве

Всякое множество ГÌАхА декартово произведение множества А самого на себя называется отношением на множестве А.

Отношение Г называется рефлексивным, если для всех аÎА верно аГа. Отношение Г называется симметричным, если для всех а, bÎА, верно аГbÞ bГа.

Отношение Г называется транзитивным, если для любого а,b, сÎА, аГb, bГс ÞаГс.

Отношение Г называется антирефлексивным, если для любого аÎА аГа никогда не выполняется.

Отношение Г называется антисимметричным, если для любого аÎА и bÎА аГb и bГа одновременно невозможно.

Отношение Г называется асимметричным, если для любых а, bÎА из аГb и bГа Þа=b.

Если отношение Г рефлексивно, симметрично и транзитивно, то оно называется отношением эквивалентности.

Теорема. Если на множестве А задано отношение эквивалентности Г, то множество А распадается на объединение непересекающихся классов эквивалентности.

Отношение Г называется отношением нестрогого порядка, если оно рефлексивно, асимметрично, транзитивно.

Отношение Г называется отношением строгого порядка, если оно антирефлексивно, антисимметрично и транзитивно.

Множество с заданным на нем отношением порядка называют упорядоченным множеством.

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ

Задача 1. На множестве людей L задано отношение Г – «жить на одной улице». Проверить, является ли оно отношением эквивалентности.

Решение. Для того чтобы отношение Г было отношением эквивалентности, необходимо, чтобы оно было рефлексивным, симметричным, транзитивным.

1. Так как каждый человек живет сам с собой на одной улице, то lГl выполняется, а значит отношение Г – рефлексивно.

2. Так как из того, что человек l₁ живет на одной улице с человеком l₂ следует, что и l₂ живет на одной улице с l₁, т.е. из l₁Гl₂ Þ l₂Гl₁, то значит отношение Г – симметрично.

3. Очевидно, что из l₁Гl₂ и l₂Гl₃ следует l₁Гl₃.

Таким образом, отношение Г – отношение эквивалентности.

Задача 2.Пусть А=R – множество действительных чисел. Введем на R отношение Г: хГу, если х£у. Проверить, является ли отношение Г отношением порядка.

Решение. 1. Проверим на рефлексивность. Так как хГх выполняется , т.е. х£х, то Г – рефлексивно. 2. Проверим на симметричность. Так как из хГуÞуГх только в случае, когда х=у (х£у, у£х Þх=у), то отношение Г – асимметрично. 3. Проверим на транзитивность. Так как из хГу, уГzÞхГz (х£у, у£zÞх£z), то отношение Г – транзитивно.

Из 1.-3. следует, что Г – отношение нестрогого порядка, а значит, отношение Г является отношением порядка.