2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Задачка на знакомства, только что придумала
Сообщение23.03.2011, 16:27 


01/10/10

2116
Израиль (племянница БизиБивера)
Каждый из 2011 жителей деревни Ксюшкино знаком по крайней мере с 670 из 2010 остальных жителей (если А знаком с Б, то и Б знаком с А).
Возможна ли ситуация, в которой двое из любых четверых ксюшкинцев не будут знакомы друг с другом?

 Профиль  
                  
 
 
Сообщение23.03.2011, 16:39 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
Что точно спрашивается?

Может ли быть так, что в любом множестве жителей деревни мощности $4$ найдётся двухэлементное подмножество, состоящее из незнакомых друг с другом жителей? Или точная формулировка другая?

 Профиль  
                  
 
 Re:
Сообщение23.03.2011, 16:42 


01/10/10

2116
Израиль (племянница БизиБивера)
Профессор Снэйп в сообщении #426628 писал(а):
Что точно спрашивается?

Может ли быть так, что в любом множестве жителей деревни мощности $4$ найдётся двухэлементное подмножество, состоящее из незнакомых друг с другом жителей? Или точная формулировка другая?

Ваша формулировка подходит.

 Профиль  
                  
 
 Re: Задачка на знакомства, только что придумала
Сообщение23.03.2011, 16:42 
Заслуженный участник
Аватара пользователя


23/07/08
10910
Crna Gora

(Оффтоп)

Жаль, что не Дарамдашкино -- красивое было бы название.

 Профиль  
                  
 
 Re: Задачка на знакомства, только что придумала
Сообщение23.03.2011, 17:33 
Заслуженный участник


08/04/08
8562
Дан произвольный граф $G:|G|=2011$, $(\forall j) deg(j) \geq 670$. Решить задачу распознавания; есть ли в графе независимое множество мощности 4.
Берем 1 вершину. Ей смежно 670 вершин. Остается 1340 вершин. Берем одну вершину из оставшихся. Максимум эти обе вершины смежны с 1342 вершинами. Остается 669 вершин. Берем оттуда третью вершину, она не смежна с 1-ми двумя. Третья вполне может быть смежна с оставшимися. Вот мы нашли независимое множество мощности 3.
И все! Граф можно разбить на 3 клики (полный подграф) мощностей 670, 670 и 671. В нем максимальная мощность независимого множества, очевидно, равна 3.
Ну можно $2011$ на $n$ заменить...

 Профиль  
                  
 
 Re: Задачка на знакомства, только что придумала
Сообщение23.03.2011, 17:38 


01/10/10

2116
Израиль (племянница БизиБивера)
Sonic86 в сообщении #426656 писал(а):
Дан произвольный граф $G:|G|=2011$, $(\forall j) deg(j) \geq 670$. Решить задачу распознавания; есть ли в графе независимое множество мощности 4.
Берем 1 вершину. Ей смежно 670 вершин. Остается 1340 вершин. Берем одну вершину из оставшихся. Максимум эти обе вершины смежны с 1342 вершинами. Остается 669 вершин. Берем оттуда третью вершину, она не смежна с 1-ми двумя. Третья вполне может быть смежна с оставшимися. Вот мы нашли независимое множество мощности 3.
И все! Граф можно разбить на 3 клики (полный подграф) мощностей 670, 670 и 671. В нем максимальная мощность независимого множества, очевидно, равна 3.
Ну можно $2011$ на $n$ заменить...

Очень красиво!

А вот моё решение:

Такая ситуация возможна. Вот пример:

Пронумеруем всех жителей от 1 до 2011. Пусть каждый знаком с теми и только теми, у кого остаток при делении на 3 не такой, как у него самого.
Поскольку среди любых четырёх найдутся как минимум два одинаковых остатка на 3, эти двое не будут знакомы.

Плин! Я вместо 670*2=1340 написала 670, во разиня!!! Уже исправляю.
Уже не позволено исправить :-(
Короче, вместо 670 следует читать 1340

 Профиль  
                  
 
 
Сообщение23.03.2011, 17:43 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
Короче, нужно определить, существует ли простой граф $\langle V, E \rangle$ без петель такой, что $|V| = 2011$, $(\forall v \in V)(|E(v)| \geqslant 670)$ и
$$
(\forall A \subseteq V)(|A| = 4 \Rightarrow (\exists B \subseteq A)(|B|=2 \mathop{\&} B \not\in E))
$$
Эк замудрила :-)

Представляем граф матрицей инцидентности, матрица $2011 \times 2011$ из нулей и единиц, симметрическая, по диагонали нули, в каждой строке $670$ единиц. Может ли при этих условиях не существовать четырёх строчек/столбцов, таких что задаваемая ими подматрица содержит нули лишь на главной диагонали?

Похоже, легче не становится... Мыслить надо!!!

-- Ср мар 23, 2011 20:48:32 --

Уже помыслили, за меня :roll:

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group