👍 0 👎 |
Математическая задачка . Графы.Можно ли подобрать компанию , где у каждого её члена было пять друзей , а у любых двух — ровно два общих друга?
|
👍 0 👎 |
Интересная задачка. Можно либо пытаться подобрать граф для такой компании, либо найти какие-нибудь ограничения. Мне было проще работать с представлением графа в виде матриц. Обозначим за А матрицу связей графа. Поскольку из каждой вершины исходят 5 ребер, то должен быть регулярный граф, что в матричном виде записывается как АJ=5J (матрица J — матрица из одних единичек, произведение строки А на столбец J как раз подсчитывает сколько ребер выходит из данной вершины). Тот факт что любые две вершины имеют два общих соседа записвается в виде АА=3I+2J (iая строка А умножить на jый столбец А равно 2, а если i=j, то 5). Получается два матричных уравнения.Если мы первое уравнение умножим слева на А, получим ААJ=25J. Умножим второе уравнение справа на J получим AAJ=3J+2vJ. Вычитая первое уравнение из второго найдем что 2vJ=22J. То есть число вершин v=11. C другой стороны, для регулярного графа, произведение числа вершин на кратность вершины должно быть четным, но 55 нечетное. Значит такой граф не возможен. Подобрать такую компанию нельзя! |
👍 0 👎 |
Математическая задача, принцип Дирихле
|
👍 0 👎 |
Уравнение
|
👍 +1 👎 |
Связь слова с числом
|
👍 0 👎 |
Принцип Дирихле
|
👍 0 👎 |
В классе 25 учеников
|
👍 0 👎 |
Могут ли две бесконечных арифметических прогрессии положительных чисел
|