Цветной хитрый угольник

[Keter]

У выпуклого 24-угольника стороны и диагонали окрашены либо в цвет $A$, либо в цвет $B$.
Вопрос: всегда ли возможно взять 4 вершины так, чтобы все стороны и диагонали полученного 4-угольника были окрашены в один цвет?
Если нет, то приведите все случаи когда этого сделать нельзя.

[ИСН]

Число Рамсея $R(4,4)$ тупо равно 18.

[ИСН]

Если бы доказать это было просто, то мы бы и пятое знали.

[Keter]

ИСН, то есть не важно какой нам дан выпуклый многоугольник, 24 или 48?

Так а что такое это число Рамсея $R(n, k)$ ? Что такое $n$ и $k$?

[ИСН]

Ну что, что, ну. Двадцать первый век на дворе, ну.

[Keter]

ИСН, я нашел пару статей в вики.. Но мне нужна помощь, не получается нормально сформулировать теорему для данной задачи, как бы алгоритм оформления...

В случае раскраски графа в два цвета (чёрный и белый) теорема утверждает, что достаточно большой полный граф содержит либо чёрный полный подграф размера $r$, либо белый размера $s$. Минимальное число $R(r, s)$, при котором это выполняется называется числом Рамсея.

Почему мы берем $R(4, 4)$, как обосновать.. Никак не могу въехать

[ИСН]

Ну ёлки, что такое 4-угольник со всеми сторонами и диагоналями, ну? Это какой граф какого размера?

[Keter]

ИСН, ну $K_4:6$

[ИСН]

Что означает и нужно ли вообще вот это ":6"?

[Keter]

ИСН, количество отрезков - 4 стороны и две диагонали. Вроде не нужно.

[ИСН]

Ага. То есть попросту мы ищем чёрный полный подграф размера 4. Или белый, тоже 4. Чем нам могут помочь числа Рамсея, и какое конкретно из них?

[Keter]

Ну а что характеризует число $R$? Минимальный полный граф, который мы можем взять и для него будет выполняться условие задачи ?

[ИСН]

Да. Это 18. А у нас 24 - хватит за глаза.
Но видимо, это-то и надо доказать, не опираясь на инфу извне. Точно найти число Рамсея сложно, но получить для него какую-то оценку - легко.

[Keter]

ИСН, согласен с этим.. Но как можно получить оценку, каким методом? И о какой оценке идёт речь?
То есть в решении мы ставим перед собой задачу, получить оценку, при которой выполняются условия самой задачи, и если она будет в себе содержать 24, то мы решили задачу. Остаётся понять как её получить не опираясь на теорему Рамсея.
Я думал о принципе Дирихле... но он мне не особо нравится.

-- 24.06.2013, 22:21 --

ИСН, мы же можем попытаться доказать, что $R(4, 4)>17$ без ссылки на Рамсея?

[iifat]

Keter в сообщении #740070 писал(а):

мы же можем попытаться доказать, что $R(4, 4)>17$ без ссылки на Рамсея?

Как понимаю, однажды в истории это было проделано. Самим Рамсеем. Вряд ли он ссылался на Рамсея.