СПРОСИ ПРОФИ
👍
0
👎 01

Математическая задачка . Графы.

Можно ли подобрать компанию , где у каждого её члена было пять друзей , а у любых двух — ровно два общих друга?
математика обучение     #1   02 фев 2015 20:53   Увидели: 351 клиент, 14 специалистов   Ответить
👍
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 нечетное. Значит такой граф не возможен. Подобрать такую компанию нельзя!

Задайте свой вопрос по математике
профессионалам

Сейчас онлайн 75 репетиторов по математике
Получите ответ профи быстро и бесплатно

Другие вопросы на эту тему:

👍
0
👎 03

Математическая задача, принцип Дирихле   3 ответа

математическая задача , принцип Дирихле.
У биологов Наташи , Ани , Оли есть 49 лабораторных мышей . Пытливые экспериментаторы поделили мышей между собой . Докажите , что хотя бы у одной из них найдутся или пять одинаковых мышек , или пять разных .
  17 янв 2015 12:22  
👍
0
👎 05

Уравнение   5 ответов

В задаче надо найти такое уравнение с целыми коэффицентами что число корень квадратный из двойки плюс корень кубический из двойки будет его корнем. Я пытался подобрать коэффиценты, но у меня ничего не получается ((( Как это сделать?
  18 дек 2014 22:39  
👍
+1
👎 14

Связь слова с числом   4 ответа

Добрый день!

Представлены слова с пропущенными буквами и дано числовое значение каждого слова. Вставьте пропущенные буквы (объясните связь слова и числа):
МИ_ _ =39;
МЕ_ОК=70;
Р_К_=49;
К_ _Т=45;
_ОСТ=68.

Предполагали, что буква соответствует цифре в алфавите, но смогли подобрать слова. Также пробовали и обратную нумерацию алфавита.
  23 июн 2014 10:03  
👍
0
👎 02

Принцип Дирихле   2 ответа

В классе 25 учеников. Среди любых трех из них есть двое друзей. Доказать, что есть ученик, у ктрого не менее 12друзей. Мне сказали, что задача на принцип Дирихле, прочитал, но не пойму, где клетки и где кролики.
  29 окт 2012 15:28  
👍
0
👎 01

В классе 25 учеников   1 ответ

В классе 25 учеников. Известно, что среди любых трех из них двое дружат между собой. Докажите, что есть ученик, у которого не менее 12 друзей.
👍
0
👎 00

Могут ли две бесконечных арифметических прогрессии положительных чисел   0 ответов

Могут ли две бесконечных арифметических прогрессии положительных чисел иметь ровно два общих члена?
ASK.PROFI.RU © 2020-2024