Задачка на знакомства, только что придумала

[Xenia1996]

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

[Профессор Снэйп]

Что точно спрашивается?

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

[Xenia1996]

Профессор Снэйп в сообщении #426628 писал(а):

Что точно спрашивается?

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

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

[svv]

(Оффтоп)

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

[Sonic86]

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

[Xenia1996]

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

[Профессор Снэйп]

Короче, нужно определить, существует ли простой граф $\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 --

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