Тема: Элементы комбинаторики
Сколько чисел меньших, чем миллион можно написать с помощью цифр 3 и 7?
Решение:
С помощью двух различных цифр можно записать
– шестизначных чисел, ,
– пятизначных ,
- четырехзначных
трехзначных чисел
двузначных чисел,
– однозначных чисел. Просуммируем эти композиции ![](https://konspekta.net/megaobuchalkaru/imgbaza/baza7/2543683668452.files/image1283.jpg)
Тема: Неориентированные графы
Матрица смежности графа, изображенного на рисунке ![](https://konspekta.net/megaobuchalkaru/imgbaza/baza7/2543683668452.files/image1284.jpg)
имеет вид … ![](https://konspekta.net/megaobuchalkaru/imgbaza/baza7/2543683668452.files/image1285.jpg)
Решение: Матрицей смежности графа называют квадратную матрицу
размера
, строкам и столбцам которой соответствуют вершины помеченного графа (первый столбец (строка) отвечает первой вершине и т.д.), а ее элементы
равны количеству ребер, инцидентных вершинам с номерами i и j. Согласно определению составляем матрицу смежности ![](https://konspekta.net/megaobuchalkaru/imgbaza/baza7/2543683668452.files/image1289.jpg)
Тема: Операции над высказываниями
Нулевой набор у формулы
получается при следующих значениях переменных …
, ![](https://konspekta.net/megaobuchalkaru/imgbaza/baza7/2543683668452.files/image1292.jpg)
Тема: Декартово произведение множеств
Пусть заданы два множества:
, ![](https://konspekta.net/megaobuchalkaru/imgbaza/baza7/2543683668452.files/image1294.jpg)
Тогда геометрическая интерпретация множества
имеет вид … ![](https://konspekta.net/megaobuchalkaru/imgbaza/baza7/2543683668452.files/image1296.jpg)
Тема: Элементы комбинаторики
Вокруг костра сидят 12 разбойников. Каждый из них смертельно ненавидит двух ближайших соседей. С целью спрятать награбленное необходимо выделить 5 разбойников. Сколькими способами атаман может назначить пятерых так, чтобы между ними не было распрей?
Решение:
12 разбойников разбиваются на две группы по 6 не враждующих между собой человек. Атаман может выбрать 5 человек из первой группы
способами или 5 человек из второй группы тоже
способами. Тогда по правилу суммы получим:
способов выбора 5 разбойников.
Тема: Операции над высказываниями
Отрицание высказывания
равносильно высказыванию … ![](https://konspekta.net/megaobuchalkaru/imgbaza/baza7/2543683668452.files/image1300.jpg)
Решение:
Высказывание
означает: неправда что х положительно, а значит ![](https://konspekta.net/megaobuchalkaru/imgbaza/baza7/2543683668452.files/image1300.jpg)
Тема: Неориентированные графы
Эйлеровым является граф …
![](https://konspekta.net/megaobuchalkaru/imgbaza/baza7/2543683668452.files/image1302.jpg)
Решение:
Эйлеровым называют граф содержащий эйлеров цикл. Цикл называется эйлеровым, если он простой и содержит все ребра графа.
Критерий эйлеровости графа: граф называется Эйлеровым тогда и только тогда, когда степени всех его вершин четные.
Из представленных графов только этот граф имеет четные степени всех вершин.
Тема: Декартово произведение множеств
Декартово произведение отрезка
на отрезок
….является прямоугольником с вершинами ![](https://konspekta.net/megaobuchalkaru/imgbaza/baza7/2543683668452.files/image1305.jpg)
Решение:
Декартовым произведением отрезка на отрезок является прямоугольник с вершинами ![](https://konspekta.net/megaobuchalkaru/imgbaza/baza7/2543683668452.files/image1305.jpg)
Тема: Элементы комбинаторики
На 10 карточках написаны буквы так, что из этих карточек можно получить слово ИСЧИСЛЕНИЕ. Сколько существует различных 10-буквенных слов, которые можно образовать с помощью этих десяти карточек?
Решение:
Разобьем карточки на группы. Первая группа содержит букву И. Элементы ее неразличимы. Число элементов первой группы
. Вторую группу образуют карточки с буквой С. Число элементов второй группы
. Третью группу образуют карточки с буквой Ч. Число элементов этой группы
. Четвертую группу образуют карточки с буквой Л, число элементов
. Пятую группу образуют карточки с буквой Е. Число элементов
. Шестая группа состоит из карточек с буквой Н. Количество элементов этой группы
. Число различных 10-буквенных слов, образованных этими 10 карточками, совпадает с числом различных перестановок с повторениями и равно ![](https://konspekta.net/megaobuchalkaru/imgbaza/baza7/2543683668452.files/image1312.jpg)
Тема: Неориентированные графы
Из представленных графов полным является граф …
![](https://konspekta.net/megaobuchalkaru/imgbaza/baza7/2543683668452.files/image1313.jpg)
Решение:
Полным называют граф без петель и кратных ребер, в котором любые две вершины соединены ребром.
Тема: Операции над высказываниями
Из трех логических выражений:
эквивалентными являются …
и ![](https://konspekta.net/megaobuchalkaru/imgbaza/baza7/2543683668452.files/image1318.jpg)
Решение:
Составим таблицы истинности для
![](https://konspekta.net/megaobuchalkaru/imgbaza/baza7/2543683668452.files/image1320.jpg)
Сопоставляя таблицы, видим, что
не эквивалентна формулам
и
, а
и
эквивалентны.
Тема: Декартово произведение множеств
Декартово произведение
множеств
и
равно … ![](https://konspekta.net/megaobuchalkaru/imgbaza/baza7/2543683668452.files/image1328.jpg)
Тема: Декартово произведение множеств
Декартово произведение множеств
и
представляет собой …
| | | окружность , лежащую в плоскости
|
Тема: Неориентированные графы
Для графа, изображенного на рисунке,
степень вершины
равна …
Решение:
Степенью вершины называют удвоенное количество петель, инцидентных этой вершине, плюс количество остальных инцидентных ей ребер. То есть степень вершины
равна пяти.
Тема: Элементы комбинаторики
На школьном вечере присутствуют 5 девушек и 6 юношей. Выбрать из них 2 пары для танца можно ___ способом(-ами).
Решение:
Сначала в произвольном порядке выбираем двух юношей из шести
способами (сочетания 2 из 6), затем выбираем для них девушек, причем теперь порядок выбора важен. Число способов выбрать двух девушек из пяти равно
(размещения 2 из 5).
Тогда число способов для выбора двух пар по правилу произведения равно:
![](https://konspekta.net/megaobuchalkaru/imgbaza/baza7/2543683668452.files/image1336.jpg)
Тема: Операции над высказываниями
На вопрос, кто из трех учащихся изучал логику, был получен правильный ответ: если изучал первый, то изучал и второй, но неверно, что если изучал третий, то изучал и второй. Тогда логику …
| | | изучал третий учащийся
|
| | | изучал второй учащийся
|
| | | изучал первый учащийся
|
| | | никто из учащихся не изучал
|
Решение:
Обозначим через a, b, c высказывания, состоящие соответственно в том, что первый, второй, третий учащиеся изучали логику. Запишем условие задачи с помощью a, b, cи логических операций. Получим выражение
. Известно, что это высказывание истинно. Составим таблицу истинности полученного выражения:
Только в предпоследней строке получившееся выражение принимает истинное значение, а все остальные значения ложны. При этом высказывания a и b ложны, а c – истинно. Значит, логику изучал только третий учащийся.
Тема: Операции над высказываниями
Высказывание «
» означает, что …
| | | « – любое число»
|
| | | « принадлежит интервалу »
|
| | | « принадлежит промежутку »
|
| | | « не существует»
|
Решение:
Высказывание «
» – это дизъюнкция двух неравенств, и решением является объединение промежутков:
. То есть
– любое число.
Тема: Декартово произведение множеств
Даны множества
,
и
. Тогда число элементов декартова произведения множеств
равно…
Решение:
Декартово произведение множеств – это множество, состоящее из упорядоченных пар элементов, первым элементом которых являются элементы первого множества, вторым – элементы второго, то есть
Множество, состоящее из шести элементов, умножается на множество из четырех элементов, тогда по свойству декартова произведения получается множество, состоящее из 24 элементов.
Тема: Неориентированные графы
Для графа, изображенного на рисунке,
гамильтоновым циклом является маршрут …
Решение:
Цикл называется гамильтоновым, если он простой и содержит все вершины графа.
Для данного графа гамильтоновым циклом служит, например, маршрут
![](https://konspekta.net/megaobuchalkaru/imgbaza/baza7/2543683668452.files/image1349.jpg)
Тема: Неориентированные графы
Матрица смежности графа, изображенного на рисунке
имеет вид …
Решение:
Матрицей смежности графа называют квадратную матрицу
размера
, строкам и столбцам которой соответствуют вершины помеченного графа (первый столбец (строка) отвечает первой вершине и т.д.), а ее элементы
равны количеству ребер, инцидентных вершинам с номерами i и j. Согласно определению составляем матрицу смежности ![](https://konspekta.net/megaobuchalkaru/imgbaza/baza7/2543683668452.files/image1289.jpg)
Тема: Декартово произведение множеств
Даны множества
,
и
. Тогда число элементов декартова произведения множеств
равно…
Решение:
Декартово произведение множеств – это множество, состоящее из упорядоченных пар элементов, первым элементом которых являются элементы первого множества, вторым – элементы второго, то есть
Множество, состоящее из шести элементов, умножается на множество из четырех элементов, тогда по свойству декартова произведения получается множество, состоящее из 24 элементов.
Тема: Элементы комбинаторики
Сколько чисел меньших, чем миллион можно написать с помощью цифр 3 и 7?
Решение:
С помощью двух различных цифр можно записать
– шестизначных чисел,
– пятизначных чисел,
– четырехзначных чисел,
– трехзначных чисел,
– двузначных чисел,
– однозначных чисел. Просуммируем эти композиции
.
Тема: Операции над высказываниями
Формулой, равносильной формуле
, является …
Решение:
![](https://konspekta.net/megaobuchalkaru/imgbaza/baza7/2543683668452.files/image1367.jpg)
Тема: Операции над высказываниями
Таблица истинности для формулы
представляет собой …
Решение:
![](https://konspekta.net/megaobuchalkaru/imgbaza/baza7/2543683668452.files/image1373.jpg)
Тема: Неориентированные графы
Эйлеровым является граф …
Решение:
Эйлеровым называют граф содержащий эйлеров цикл. Цикл называется эйлеровым, если он простой и содержит все ребра графа.
Критерий эйлеровости графа: граф называется Эйлеровым тогда и только тогда, когда степени всех его вершин четные.
Из представленных графов только граф
имеет четные степени всех вершин.
Тема: Операции над высказываниями
Высказывание «
» означает, что …
| | | « – любое число»
|
| | | « принадлежит интервалу »
|
| | | « принадлежит промежутку »
|
| | | « не существует»
|
Решение:
Высказывание «
» – это дизъюнкция двух неравенств, и решением является объединение промежутков:
. То есть
– любое число.
Тема: Элементы комбинаторики
В урне находятся 10 белых, 15 красных, 20 голубых шаров. Все шары пронумерованы. Сколькими различными способами можно взять из урны три шара разных цветов?
Решение:
Возьмем один белый шар. Это действие можно выполнить 10 способами (по числу различных белых шаров в урне). К выбранному белому шару присоединим красный шар, который можно взять 15 различными способами (по числу различных красных шаров в урне). К выбранной присоединим голубой шар, который можно взять 20 способами (по числу различных голубых шаров в урне). Таким образом, можно образовать различные тройки разноцветных шаров. Число различных способов выбора троек разноцветных шаров совпадает с числом различных трех действий и по правилу умножения равно:
![](https://konspekta.net/megaobuchalkaru/imgbaza/baza7/2543683668452.files/image1378.jpg)
Тема: Неориентированные графы
Для графа G, изображенного на рисунке,
матрица смежности имеет вид …
Тема: Операции над высказываниями
Отрицанием высказывания «Если я сдам зачет, то пойду в кафе с друзьями или на вечеринку» является высказывание:
| | | «Я сдам зачет и не пойду ни в кафе с друзьями, ни на вечеринку»
|
| | | «Если я не сдам зачет, то не пойду в кафе с друзьями или не пойду на вечеринку»
|
| | | «Если я не сдам зачет, то, несмотря ни на что, пойду в кафе с друзьями или на вечеринку»
|
| | | «Я не сдам зачет и не пойду ни в кафе с друзьями, ни на вечеринку»
|
Решение:
Введем простые высказывания: A – «я сдам зачет», B – «пойду в кафе с друзьями», C– «пойду на вечеринку».
Тогда высказывание «Если я сдам зачет, то пойду в кафе с друзьями или на вечеринку» имеет вид
.
Отрицание этого высказывания
.
Получаем высказывание: «Я сдам зачет и не пойду ни в кафе с друзьями, ни на вечеринку».
Тема: Элементы комбинаторики
Из колоды в 36 карт наудачу без возвращения вынимают по одной карте 3 раза. Сколько существует различных способов получения трех карт, среди которых на первых двух местах – бубны, а на третьем – пики.
Решение:
В колоде 9 бубен и 9 пик. Получение тройки карт «бубны, бубны, пики» можно рассматривать как результат двух действий. Первое действие – получение на первых картах «бубны, бубны». Поскольку порядок карт существенен, то число различных способов осуществления первого действия совпадает с числом размещений из 9 элементов по 2:
.
Второе действие – взятие «пики» на третьем месте. Число способов выполнить второе действие равно 9 (по количеству «пик»). По правилу умножения, получим:
.
Тема: Декартово произведение множеств
Декартово произведение отрезка
на отрезок
…
| | | является прямоугольником с вершинами
|
| | | является отрезком
|
| | | равно 2
|
| | | равно 13
|
Решение:
Декартовым произведением отрезка
на отрезок
является прямоугольник с вершинами ![](https://konspekta.net/megaobuchalkaru/imgbaza/baza7/2543683668452.files/image1305.jpg)
Тема: Неориентированные графы
Матрица инцидентности графа, изображенного на рисунке
имеет вид …
Тема: Элементы комбинаторики
В урне находятся 5 белых, 7 красных, 6 голубых шаров. Сколько существует способов извлечь 9 шаров так, чтобы среди них оказалось 2 белых, 3 красных и 4 голубых шара?
Решение:
Всего в урне 18 шаров. Сначала выберем два белых шара из 5 белых шаров. Это действие можно выполнить
способами. Второе действие состоит в выборе трех красных шаров из 7 красных шаров. Это действие можно выполнить
способами. Третье действие состоит в выборе четырех голубых шаров. Оно может быть выполнено
способами.
По правилу умножения получим: ![](https://konspekta.net/megaobuchalkaru/imgbaza/baza7/2543683668452.files/image1399.jpg)