Файл: Дискретная математика_МУ_Реш.Задач.pdf

11 

Пример 5. Сколько существует 5-значных чисел четверичной систе-

мы счисления, в каждом из которых нет нулей и единиц, а цифры 3 в числе 

нигде рядом не стоят? 

Решение. Во всех искомых числах две цифры: 2 и 3. Рассмотрим че-

тыре случая: 

1) в числе нет троек. Так как их нет, то стоять рядом они не могут. Из 

таких чисел существует только одно: 22222; 

2) пусть в числе одна тройка. И здесь стоять рядом тройки не могут. 

С  одной  тройкой  существует  пять  чисел:  22223,  22232,  22322,  23222, 

32222; 

3) если троек две, то двоек три. Запишем двойки в ряд, отделив одну 

от другой звёздочками и поставив звёздочки слева и справа: 

222. 

Удалим две звёздочки, а оставшиеся заменим тройками. Получим 5-значное 

число, где тройки рядом не стоят. Такая замена возможна 

6

2

4



C

 способами; 

4) если троек три, то двоек две. Это единственное число: 32323. 

Всего искомых чисел 1 + 5 + 6 + 1 = 13. 

Ответ: 13. 

Пример 6. Сколько существует 4-значных десятичных чисел, в кото-

рых  цифры  идут  в  порядке  возрастания  и  каждое  число  начинается  с  не-

чётной цифры?  

Решение. Разобьём задачу на ряд более простых подзадач: 

1) если  числа начинаются с единицы, то справа от неё трёхзначные 

числа можно записать 

56

3

8



C

 вариантами; 

2)  если  числа  начинаются  с  цифры  3,  то  таких  чисел  возможно 

;

20

3

6



C

12 

3) если числа начинаются с цифры 5, то справа от неё трёхзначные 

числа можно записать 

4

3

4



C

 вариантами; 

4)  если  числа  начинаются  с  цифры  7,  то  этому  случаю  не  соответ-

ствует никакого четырёхзначного числа. 

Сложим результаты: 56 + 20 + 4 = 80. 

Ответ: 80.  

Пример  7.  Сколько  существует  6-значных  симметричных  восьме-

ричных чисел, т. е. одинаково читающихся как слева направо, так и справа 

налево, если в каждом числе только две чётные цифры (а все остальные – 

нечётные)? С нуля числа не начинаются. 

Решение.  Всё  многообразие  искомых  чисел  определяется  первыми 

тремя цифрами в каждом числе. Для второй половины числа выбора нет: 

цифры  второй  половины  должны  повторять  первые  три  цифры,  но  в  об-

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

не 6-значных чисел, а только 3-значных, в каждом из которых точно одна 

чётная цифра. 

Чётные восьмеричные цифры: 0, 2, 4, 6. Сначала предположим, что 

числа могут начинаться с нуля. Если чётная цифра стоит на первом месте, 

то на втором и третьем местах могут стоять только нечётные цифры. Со-

гласно правилу произведения, таких чисел существует 4 

 4  4 = 64. Чётная 

цифра может стоять на любом из трёх мест, следовательно, всего возмож-

но 64 

 3 = 192 числа. Но по условию числа не могут начинаться с нуля. 

Всего начинающихся с нуля чисел существует 4 

 4 = 16. Вычтем это число 

из 192, получим 176. 

Ответ: 174. 

13 

Пример  8.  Сколько  существует  7-значных  двоичных  чисел,  в  каж-

дом из которых нулей больше чем единиц? Числа могут начинаться с нуля. 

Решение. Разобьём задачу на ряд более простых подзадач: 

1) в числе нет единиц. Такое число существует только одно: 0000000; 

2) в числе одна единица и шесть нулей. Таких чисел 7; 

3) в числе две единицы и пять нулей. Количество таких чисел опре-

делим по формуле 

;

21

2

7



C

4) в числе три единицы и четыре нуля. Таких чисел существует  

3

7

7!

1 2 3 4 5 6 7

35.

3!(7 3)! 1 2 3 1 2 3 4

C

     









     

Сложим полученные результаты: 1 + 7 + 21 + 35 = 64. 

Ответ: 64. 

Пример 9. Сколько существует 4-значных десятичных чисел, в кото-

рых нечётных цифр столько же, сколько и чётных? Числа могут начинать-

ся с нуля. 

Решение. Согласно условию, в каждом числе содержится две чётные 

и две нечётные цифры. Пусть числа начинаются с чётных цифр. Тогда по-

лучим 5 

 5  5  5 = 625 чисел. Две чётные цифры могут занимать и другие 

места  в  4-значном  числе.  Число  вариантов  равно 

.

6

2

4



C

  Следовательно, 

всего искомых чисел существует 625 

 6 = 3750. 

Ответ: 3750. 

Пример  10.  В  числе  141  восьмеричной  системы  счисления  каждую 

единицу заменили цифрой, являющейся простым числом, а цифру 4 заме-

нили другой цифрой, не равной 4. Сколько получилось новых чисел, если 

повторы цифр возможны? 

14 

Решение. Цифры 2, 3, 5 и 7 восьмеричной системы счисления явля-

ются  простыми  числами.  Следовательно,  единицы  в  числе  141  можно  за-

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

из  которых  цифра  4  не  может  заменять  саму  себя.  Таким  образом,  всего 

существует 4 

 7  4 = 112 искомых чисел. 

Ответ: 112. 

Пример  11.  Сколько  существует  4-значных  шестеричных  чисел, 

в каждом  из  которых  содержится  хотя  бы  одна  цифра  3?  Числа  могут 
начинаться с нуля. Повторы цифр возможны. 

Решение. Сначала найдём количество чисел, в которых нет цифры 3. 

На  место  старшего  разряда  можно  поставить  одну  из  следующих  цифр 

(цифра 3 удалена): 0, 1, 2, 4, 5. То же самое относится и к остальным раз-

рядам. Следовательно, существует 5 

 5  5  5 = 625 4-значных шестерич-

ных чисел, в каждом из которых нет цифры 3. С учётом же цифры 3 воз-

можно 6 

 6  6  6 = 1296 чисел. Тогда существует 1296 – 625 = 671 число, 

в каждом из которых содержится хотя бы одна цифра 3. 

Ответ: 671. 

Пример  12.  К  4-значному  двоичному  числу  a  справа  приставили         

3-значное двоичное число b. Оба они могут начинаться с нуля. Получилось 

7-значное число. Сколько существует 7-значных чисел, если a 

 b? 

Решение. Если b = 0, то a может быть равным 1, 2, 3, …, 15. Всего 

15 значений.  Если  b  =  1,  то  a  может  быть  равным  2,  3,  4,  …,  15.  Всего 
14 значений.  Если  b  =  2,  то  a  может  быть  равным  3,  4,  5,  …,  15.  Всего 

13 значений. И так далее до b = 7. Число a при этом может быть равным 8, 
9, 10, …, 15. Всего 8 значений. Сложим полученные результаты: 

15 + 14 + 13 + 12 + 11 + 10 + 9 + 8 = 92. 

Ответ: 92. 

15 

ТЕМА 3. ТЕОРИЯ ГРАФОВ 

Эта теория изобилует понятиями. В зачётной задаче требуется найти 

все  простые  цепи,  соединяющие  две  заданные  вершины  неориентирован-

ного  графа.  Для  успешного  её  решения  необходимо  иметь  чёткое  пред-

ставление  о  таких  понятиях,  как  граф,  ориентированный  и  неориентиро-

ванный  графы,  помеченный  граф,  связность  графа,  цепь,  простая  цепь, 

простой  цикл,  длина  цепи,  вершинное представление цепей,  графический 

и аналитический способы задания графа. 

В данной контрольной работе граф задан множеством рёбер. Каждо-

му  ребру  поставлено  в  соответствие  множество,  состоящее  из  номеров 

двух вершин, соединённым ребром. Представление рёбер в виде множеств 

обусловлено тем, что рёбра являются неориентированными (в множествах, 

где нет специальных оговорок, элементы являются неупорядоченными). 

Как выполнять задание по данной теме, проиллюстрируем на следу-

ющем примере: 

Пример.  Найдите  все  простые  цепи,  соединяющие  вершины  1  и  6 

неориентированного графа: 

G = {{1,3}, {1,4}, {2,3}, {2,4}, {2,5}, {3,5}, {3,6}, {4,5},{4,6}}. 

Определите числа a, b, c, d, где 

a – число простых цепей, состоящих из двух рёбер; 

b – число простых цепей, состоящих из трёх рёбер; 

c – число простых цепей, состоящих из четырёх рёбер; 

d – число простых цепей, состоящих из пяти рёбер. 

Решение.  Сначала  граф  из  аналитической  формы,  представленной 

множеством неориентированных рёбер, переведём в графическую (рис. 1). 

Затем действуем поэтапно.