В некоторой компании любые два знакомых не имеют общих знакомых

2014-06-08   

В некотором обществе любые два знакомых не имеют общих знакомых, а любые два незнакомых имеют ровно двух общих знакомых. Доказать, что в этом обществе все имеют одинаковое число знакомых.

Решение:

Докажем, во-первых, что любые два знакомых имеют одинаковое число знакомых. Действительно, пусть $A$ и $B$ знакомы, а $A_{1}, A_{2}, cdots, A_{n}$ — все знакомые $A$, отличные от $B$. Тогда, согласно условию задачи, никакие двое среди $B, A_{1}, A_{2}, cdots, A_{n}$ не знакомы между собой. Рассмотрим $A_{1}$. Поскольку $A_{1}$ не знаком с $B$, то он имеет с $B$ двух общих знакомых: $A$ и, например, $B_{1}$. Так как $B_{1}$ и $A$ не знакомы друг с другом, то, кроме $B$ и $A_{1}$, у них нет общих знакомых, а значит, $B_{1}$ не знаком с $A_{2}, cdots, A_{n}$. Аналогично находим $B_{2}$ — общего знакомого $A_{2}$ и $B$ (отличного от $B_{1}$, так как $B_{1}$ не знаком с $A_{2}$) и т. д. Таким образом, всем знакомым $A$ (отличным от $B$) соответствуют разные знакомые $B$ (отличные от $A$), а значит, число знакомых $A$ не превосходит числа знакомых $B$. Аналогично доказывается, что число знакомых $B$ не превосходит числа знакомых $A$. Поэтому $A$ и $B$ имеют одинаковое число знакомых. Во-вторых, если $C$ и $D$ не знакомы, то они имеют общего знакомого $E$. Тогда по доказанному выше $C$ и $E$ имеют одинаковое число знакомых, то же имеет место и для $D$ и $E$. Следовательно, $C$ и $D$ также имеют одинаковое число знакомых, совпадающее с числом знакомых $E$.

Задачи по теории графов Основные определения и примеры графов

1. В шахматном турнире
   по круговой системе участвуют семь
   студентов. Известно, что Ваня сыграл
   шесть партий, Толя – пять, Леша и Дима
   – по три, Семен и Илья – по две, Женя –
   одну. С кем сыграл Леша?

2. Покажите, что
   следующие объекты можно рассматривать
   как графы:

 вершины и ребра
многогранника;

 план лабиринта;

 дружеские
отношения в группе студентов;

 генеалогическое
дерево;

 теннисный турнир;

 страны на карте.

1. На рисунке
   изображены молекулы этилена и бензола;
   через С и Н обозначены атомы углерода
   и водорода соответственно. Можно ли
   считать эти диаграммы графами? Если
   да, то что будет являться необходимым
   условием для того, чтобы граф представлял
   собой молекулу какого-либо углеводорода?

1. Могут ли степени
   вершины в простом графе быть равны:

 8, 6, 5, 4, 4, 3, 2, 2;

 7, 7, 6, 5, 4, 2, 2, 1;

 6, 6, 6, 5, 5, 3, 2, 2.

1. Докажите, что
   число людей, когда-либо живших на Земле
   и сделавших нечетное число рукопожатий,
   четно.

2. В городе Маленьком
   15 телефонов. Можно ли их соединить
   проводами так, чтобы каждый телефон
   был соединен ровно с пятью другими?

3. Можно ли нарисовать
   на плоскости 9 отрезков так, чтобы каждый
   пересекался ровно с тремя другими?

4. В городе Маленьком
   15 телефонов. Можно ли их соединить
   проводами так, чтобы было 4 телефона,
   каждый из которых соединен с тремя
   другими, 8 телефонов, каждый из которых
   соединен с шестью, и 3 телефона, каждый
   из которых соединен с пятью другими?

5. В группе 30 человек.
   Может ли быть так, что 9 из них имеют по
   3 друга (в этой группе), 11 – по 4 друга, а
   10 – по 5 друзей?

6. В некоторой стране
   19 регионов. Может ли оказаться так, что
   у каждого региона 1, 5 или 9 соседних
   регионов?

7. В государстве 100
   городов, и из каждого из них выходит 4
   дороги. Сколько всего дорог в государстве?

8. Может ли в
   государстве, в котором из каждого города
   выходит 3 дороги, быть ровно 100 дорог?

9. В розыгрыше
   первенства по футболу участвуют 20
   команд. Какое наименьшее число игр
   должно быть сыграно, чтобы среди любых
   трех команд нашлись две, уже сыгравшие
   между собой?

10. Нарисуйте полный
    граф с n
    вершинами, если:

а) n
= 2; б) n
= 3; в) n
= 5.

1. Какова степень
   каждой вершины полного графа, у которого
   n
   вершин?

2. Спортивные
   соревнования проводятся по круговой
   системе. Это означает, что каждая пара
   игроков встречается между собой ровно
   один раз. В соревновании с двенадцатью
   участниками провели все встречи. Сколько
   было сыграно встреч?

3. Может ли полный
   граф иметь 7, 8, 9 или 10 ребер?

4. В некотором
   государстве система авиалиний устроена
   так, что любой город соединен авиалиниями
   не более чем с тремя другими и из любого
   города в любой другой можно перелететь,
   сделав не боле одной пересадки. Какое
   наибольшее число городов может быть в
   этом государстве?

5. Какие из предложенных
   графов являются регулярными?

1. В некоторой
   компании любые два знакомых не имеют
   общих знакомых, а любые два незнакомых
   имеют ровно двух общих знакомых.
   Докажите, что в этой компании все имеют
   одинаковое число знакомых.

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

3. Спортивные
   соревнования проводятся по круговой
   системе. Это означает, что каждая пара
   игроков встречается между собой ровно
   один раз. Докажите, что в любой момент
   времени найдутся хотя бы два игрока,
   проведшие одинаковое число встреч.

4. Докажите, что в
   любом графе найдутся по крайней мере
   две вершины одинаковой степени.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

задачка про знакомых

Милая задачка на решение в уме, олимпиадного типа:

На вечеринке несколько человек. Если два человека знакомы, у них нет общих знакомых. Если они не знакомы, у них ровно двое общих знакомых. Доказать, что у всех участников вечеринки одно и то же количество знакомых.

Если кому-то лень думать, то решение есть в журнале ilyavinarsky, которому спасибо за эту задачку.

Условия и решения задач к экзамену по Наимову — файл n1.doc

приобрести
Условия и решения задач к экзамену по Наимову
скачать (19904 kb.)
Доступные файлы (5):

n1.doc	522kb.	24.05.2009 20:19	скачать
n2.txt	1kb.	16.01.2011 15:09	скачать
n3.doc	75kb.	19.06.2010 01:02	скачать
n4.doc	19842kb.	19.06.2010 01:04	скачать
n5.pdf	196kb.	13.06.2009 15:16	скачать

---

Смотрите также:
• Мартинсон Л.К., Смирнов Е.В. Методические указания к решению задач по курсу общей физики. Раздел: Волновые свойства частиц, гипотеза Де Бройля (Документ)
• Решенные задачи к экзамену и просто пример решения задач (Документ)
• Ситков М.И., Трубачев О.В. Физика. 10 класс: Решение задач из учебного пособия А.П. Рымкевича Сборник задач по физике (Документ)
• Каменецкий С.Е., Орехов В.П. Методика решения задач по физике в средней школе (Документ)
• Гончаренко С.У. (ред.) Физика. Задачник-практикум (Документ)
• Волновая оптика (Документ)
• Квантовая оптика (Документ)
• Молекулярная физика (Документ)
• Петров В. Алгоритм решения изобретательских задач (Документ)
• Решения задач по физике (Иродов) (Документ)
• Рекач В.Г. Руководство к решению задач по теории упругости (Документ)
• Гуртов В.А., Ивашенков О.Н. Сборник задач по микрооптоэлектронике (Документ)

n1.doc

Сто десять задач по дискретной математике
1. Множества, бинарные отношения, отображения,

эквивалентность, группа, кольцо, поле
№ 1. Доказать, что для любых подмножеств , . . . , любого множества справедливы формулы де Моргана

,

.
№ 2. Доказать, что множество вещественных чисел эквивалентно множеству точек плоскости.
№ 3. Доказать, что множество рациональных чисел счетно.
№ 4. Найти инфимум, супремум, максимум и минимум множества

.
№ 5. Доказать, что на множестве натуральных чисел бинарное отношение

является отношением эквивалентности. Найти классы эквивалентности.
№ 6. Пусть — множество всех подмножеств множества . Найти и доказать, что частично упорядочено относительно бинарного отношения включения подмножеств. Построить диаграмму Хассе.
№ 7. Для бинарного отношения

найти , .
№ 8. Привести пример бинарного отношения, которое

а) рефлексивно, симметрично, нетранзитивно;

б) рефлексивно, несимметрично, транзитивно.
№ 9. Привести пример бинарного отношения, которое

а) рефлексивно, антисимметрично, нетранзитивно;

б) нерефлексивно, симметрично, транзитивно.
№ 10. На множестве определить отношение строгого порядка.
№ 11. На множестве построить неассоциативную бинарную операцию.
№ 12. На множестве построить ассоциативную, некоммутативную бинарную операцию.
№ 13. На множестве построить ассоциативную, коммутативную бинарную операцию.

№ 14. На множестве четных натуральных чисел определена бинарная операция . Найти решение уравнения .
№ 15. При каком натуральном верно равенство , если бинарная операция * определена формулой .
№ 16. Построить пример отображения которое

а) биективно;

б) инъективно, несюръективно.
№ 17. Построить пример отображения которое

а) неинъективно, сюръективно;

б) неинъективно, несюръективно.
№ 18. Привести пример двух таблиц, к которым применимы все операции реляционной алгебры.
№ 19. На множестве определить бинарную операцию, относительно которой будет полугруппой, но не группой.
№ 20. Привести пример неабелевой группы из шести элементов.
№ 21. Доказать, что группа подстановок четвертого порядка неабелева.
№ 22. Привести пример циклической группы порядка 4.
№ 23. Привести пример группы и ее собственной подгруппы . Найти левые и правые смежные классы по подгруппе .
№ 24. На множестве определить групповую операцию и привести пример фактор-группы.
№ 25. Доказать, что множество является полем относительно операций сложения и умножения по модулю 7.
2. Комбинаторика
№ 26. Доказать формулу бинома Ньютона

.
№ 27. Найти число целых неотрицательных решений уравнения .
№ 28. Сколькими способами можно распределять 30 студентов на производственную практику в три города, так чтобы два определенных студента оказались в одном городе, если в первый город необходимо отправить 15 выпускников, во второй – 8, в третий – 7.
№ 29. Десять книг сколькими способами можно расставить в один ряд, так чтобы три определенные книги оказались рядом.
№ 30. Сколькими способами можно составить букет из семи цветов, используя четыре сорта цветов.
№ 31. В группе из 25 студентов любящих математику – 15, физику – 10, нелюбящих ни математику, ни физику – 8. Сколько студентов любят и математику, и физику.
№ 32. Из 100 студентов знают английский – 28, немецкий – 30, французский – 42, английский и немецкий – 8, английский и французский -10, немецкий и французский – 5, все языки – 3. Сколько студентов не знают ни одного из этих языков.
№ 33. писем сколькими способами можно вложить в конвертов с адресами, так чтобы

а) хотя бы одно письмо попало в свой конверт;

б) ни одно письмо не попало в свой конверт.
№ 34. Найти решение рекуррентного соотношения , , .
№ 35. Найти решение рекуррентного соотношения , , .
№ 36. Вывести общую формулу для чисел Фибоначчи.
№ 37. Найти последовательность чисел по производящей функции .
№ 38. Составить рекурсивный алгоритм вычисления суммы

№ 39. Найти производящую функцию последовательности чисел , .
№ 40. Доказать формулу для числа сочетаний с повторениями .

3. Графы
№ 41. Построить геометрическую реализацию ориентированного графа с множеством вершин и множеством дуг . Найти матрицу смежности графа.
№ 42. Найти граф по его геометрической реализации

№ 43. Найти граф по матрицу смежности

.

№ 44. Найти орграф, если известна его матрица смежности

.
№ 45. Найти граф, если известна его матрица инцидентности

.
№ 46. Найти орграф, если известна его матрица инцидентности

.
№ 47. Найти число всевозможных графов с двадцатью вершинами.

№ 48. Доказать, что если в графе степени всех вершин не меньше двух, то в таком графе существует цикл.

№ 49. Найти число всевозможных графов с двадцатью вершинами, связные компоненты которых регулярны.

№ 50. На множестве натуральных чисел от 1917 до 1991 задать множество ребер так, чтобы получился 7-дольный граф.

№ 51. Для числа ребер связного графа доказать оценку ,

где — число вершин графа.

№ 52. Построить двоичный гиперкуб в случае , и найти его диаметр.

№ 53. Найти число остовных деревьев графа с множеством вершин и множеством ребер .

№ 54. Найти число всевозможных маршрутов длины 4, соединяющих первую и третью вершины графа.

№ 55. Доказать, что связный граф эйлеров тогда и только тогда, когда все вершины графа имеют четную степень.

№ 56. Составить коды де Брейна в случае .

№ 57. Составить коды Грея в случае .

№ 58. Построить пример негамильтонового графа без точек сочленения.

№ 59. Построить пример графа, который

а) эйлеровый, гамильтоновый;

б) неэйлеровый, гамильтоновый;

в) эйлеровый, негамильтоновый.

№ 60. Доказать, что граф задачи о трех колодцах непланарный

№ 61. Доказать, что полный граф с пятью вершинами непланарный

№ 62. Доказать, что для любого связного планарного графа справедлива формула Эйлера , где — число вершин, — число ребер, — число граней графа.

№ 63. Доказать, что в любом планарном графе существует вершина, степень которой не больше пяти.

№ 64. Доказать, что любой граф укладывается в пространстве.

№ 65. Доказать теорему о пяти раскрасках.

№ 66. Найти в данном графе гамильтонову цепь.

№ 67. Найти остов, имеющий наименьшую сумму весов ребер.

№ 68. Найти кратчайший путь между вершинами 1 и 6.

№ 69. Найти максимальный поток для транспортной сети.

№ 70. Докажите, что в группе из шести человек всегда найдутся три человека, знакомые между собой, или три человека, не знакомые между собой (раскраска графа).

№ 71. Каждый из семи мальчиков имеет трех братьев. Докажите, что все мальчики – братья (связные графы).
№ 72. В некоторой компании любые два знакомых не имеют общих знакомых, а любые два незнакомых имеют ровно двух общих знакомых. Докажите, что в этой компании все имеют одинаковое число знакомых.(регулярные графы)
№ 73. Может ли в государстве, в котором из каждого города выходит ровно три дороги, быть ровно 100 дорог между городами? (лемма о рукопожатий)
№ 74. Из какого минимального числа кусков проволоки можно спаять каркас куба? (Толщина всех ребер каркаса должна быть одинаковой). (полуэйлеровы циклы)
№ 75. В информационной сети каждый центр соединен каналами связи с четным числом центров. Докажите, что после уничтожения любого канала сеть не выйдет из строя. (существование цикла в графе)

4. Булевы функции
№ 76. Для булевой функции заданной таблицей найти

а) СДНФ, СКНФ;

б) многочлен Жегалкина;

в) минимальную ДНФ.

x1	0	1	0	1	0	1	0	1
x2	0	0	1	1	0	0	1	1
x3	0	0	0	0	1	1	1	1
f	1	0	1	0	1	0	1	0

№ 77. Для булевой функции заданной таблицей найти

а) СДНФ, СКНФ;

б) многочлен Жегалкина;

в) минимальную ДНФ.

x1	0	1	0	1	0	1	0	1
x2	0	0	1	1	0	0	1	1
x3	0	0	0	0	1	1	1	1
f	0	1	0	1	0	1	0	1

№ 78. Для булевой функции заданной таблицей найти

а) СДНФ, СКНФ;

б) многочлен Жегалкина;

в) минимальную ДНФ.

x1	0	1	0	1	0	1	0	1
x2	0	0	1	1	0	0	1	1
x3	0	0	0	0	1	1	1	1
f	1	1	0	1	0	1	1	1

№ 79. Для булевой функции заданной таблицей найти

а) СДНФ, СКНФ;

б) многочлен Жегалкина;

в) минимальную ДНФ.

x1	0	1	0	1	0	1	0	1
x2	0	0	1	1	0	0	1	1
x3	0	0	0	0	1	1	1	1
f	0	1	0	1	1	0	0	1

№ 80. Для булевой функции заданной таблицей найти

а) СДНФ, СКНФ;

б) многочлен Жегалкина;

в) минимальную ДНФ.

x1	0	1	0	1	0	1	0	1
x2	0	0	1	1	0	0	1	1
x3	0	0	0	0	1	1	1	1
f	1	1	1	1	0	1	0	0

№ 81. Для булевой функции заданной таблицей найти двойственную функцию. Определить принадлежность функции классам Поста. Построить комбинаторную схему.

x1	0	1	0	1	0	1	0	1
x2	0	0	1	1	0	0	1	1
x3	0	0	0	0	1	1	1	1
f	0	0	1	0	1	1	0	0

№ 82. Для булевой функции заданной таблицей найти двойственную функцию. Определить принадлежность функции классам Поста. Построить комбинаторную схему.

x1	0	1	0	1	0	1	0	1
x2	0	0	1	1	0	0	1	1
x3	0	0	0	0	1	1	1	1
f	1	1	0	1	0	0	0	1

№ 83. Для булевой функции заданной таблицей найти двойственную функцию. Определить принадлежность функции классам Поста. Построить комбинаторную схему.

x1	0	1	0	1	0	1	0	1
x2	0	0	1	1	0	0	1	1
x3	0	0	0	0	1	1	1	1
f	0	1	0	0	1	1	0	1

№ 84. Для булевой функции заданной таблицей найти двойственную функцию. Определить принадлежность функции классам Поста. Построить комбинаторную схему.

x1	0	1	0	1	0	1	0	1
x2	0	0	1	1	0	0	1	1
x3	0	0	0	0	1	1	1	1
f	1	0	1	0	1	0	1	0

№ 85. Для булевой функции заданной таблицей найти двойственную функцию. Определить принадлежность функции классам Поста. Построить комбинаторную схему.

x1	0	1	0	1	0	1	0	1
x2	0	0	1	1	0	0	1	1
x3	0	0	0	0	1	1	1	1
f	0	1	0	1	0	1	0	1

№ 86. Доказать замкнутость классов Поста.
№ 87. Найти число булевых функций зависящих от переменных и сохраняющих .

№ 88. Найти число булевых функций зависящих от переменных и сохраняющих .

№ 89. Найти число самодвойственных булевых функций зависящих от переменных.

№ 90. Найти число линейных булевых функций зависящих от переменных.
№ 91. Доказать, что булеву функцию отрицания можно выразить суперпозициями любой немонотонной булевой функции и функций 0 и 1.

№ 92. Пусть и . Доказать, что суперпозициями функций , можно выразить либо функцию отрицания, либо функции 0 и 1. (рассмотреть функцию )

№ 93. Пусть . Доказать, что суперпозициями функции и функции отрицания можно выразить 0 и 1. (рассмотреть функцию , где — точка, где нарушается условие самодвойственности)

№ 94. Пусть , , . Доказать, что суперпозициями функций , , , можно выразить функцию отрицания и функции 0, 1. (вывести из решений задач 91-93)

№ 95. Пусть . Доказать, что функцию конъюнкции можно выразить суперпозициями функции , функции отрицания и функций 0, 1. (Примечание: функция представима в виде , где функции , , , не зависят от переменных , и на каком-то наборе , поэтому для функции имеем )
№ 96. Доказать теорему Поста о полноте. (вывести из решений задач 94, 95)

5. Кодирование
№ 97. Для заданного алфавита построить разделимую схему, которая не является префиксной или постфиксной.
№ 98. Для заданного алфавита построить разделимую схему с заданными длинами элементарных кодов , , , , .
№ 99. Для заданного алфавита построить постфиксную схему с заданными длинами элементарных кодов , , , , , .
№ 100. По заданным вероятностям , , , , построить коды Хаффмана и оценить меру избыточности.
№ 101. По заданным вероятностям , , , , , построить коды Хаффмана и оценить меру избыточности.
№ 102. По заданным вероятностям , , , , построить коды Хаффмана и оценить меру избыточности.
№ 103. По заданным вероятностям , , , , , построить коды Фано-Шеннона и оценить меру избыточности.
№ 104. По заданным вероятностям , , , , построить коды Фано-Шеннона и оценить меру избыточности.
№ 105. По заданным вероятностям , , , , , построить коды Фано-Шеннона и оценить меру избыточности.
№ 106. Над заданным алфавитом привести пример неразделимой схемы с попарно различными кодами.
№ 107. Для двоичного сообщения построить код Хемминга, исправляющий одну ошибку.
№ 108. Для двоичного сообщения построить код Хемминга, исправляющий одну ошибку.
№ 109. Для двоичного сообщения , разбивая его на две части, построить коды Хемминга, в совокупности исправляющих две ошибки.
№ 110. Для двоичного сообщения , разбивая его на две части, построить коды Хемминга, в совокупности исправляющих две ошибки.

---

Сто десять задач по дискретной математике

воскресенье, 19 сентября 2010