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

[ИСН]

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

мы же можем попытаться доказать, что $R(4, 4)>17$

Допустим. Наверное, можем. А приблизит ли это нас к решению задачи?

[Cash]

(Оффтоп)

iifat в сообщении #740146 писал(а):

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

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

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

Ну все-таки не самим Рамсеем. Насколько я понял, этот результат был получен Greenwood и Gleason в 1955 году. Числа Рамсея

[temp03]

кстати, сколько углов у хитро-угольника? Выходит 24?

[Keter]

ИСН, а разве нет? Если мы докажем, что $R(4, 4)>17,$ так, что как следствие мы получим результат $R(4, 4)=18,$ то это и будет решением данной задачи. У меня есть идеи как это можно доказать, понятное дело всё будет с нуля и о Рамсее не идет речь (в смысле об упоминании обобщенной теоремы). А какое решение Вы подразумевали?

[ИСН]

Не все числа, которые больше 17, равны 18.

[Keter]

ИСН, легко доказал, что $R(4, 4) \le 18$. Гораздо сложнее $R(4, 4)>17$... но пока до ума не довел
А о чем Вы говорили, когда написали про оценку?

[Keter]

ИСН, я уже кучу времени как доказал, что $R(4, 4)$ не более $18$... этим же всё сказано в данной задаче, ведь так? $R(4, 4) \le 18 < 24$

[ИСН]

Об этом и говорил! Нам достаточно, что оно меньше 24. Остальное - неважно. Ограничение снизу не интересует.

[Keter]

ИСН, я правильно понял, что алгоритм док-ва такой:

1) Доказываем $R(r, s) \le R(r-1, s)+R(r, s-1)$
2) Усиливаем: если $R(r-1, s)$ и $R(r, s-1)$ чётные, то $R(r, s) \le R(r-1, s)+R(r, s-1)-1$
3) Доказываем $R(3, 3)=6$ и $R(4, 2)=4$
4) Применяем доказанное по пунктам 2,3: $R(4, 3) \le R(4, 2)+R(3, 3)−1=9$
5) Из пунктов 1, 4: $R(4, 4) \le R(3, 4)+R(4, 3)=18$

Или есть более рациональный способ, как Вы считаете?

[ИСН]

Да я не помню на память, смотреть надо. Или даже не надо. Если вышло, то и хорошо.

[hippie]

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

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

Можем.

[Keter]

ИСН, тут вот в чем загвоздка... Вы не знаете, можно ли доказать, что $R(3, 4) \le 9$ без п.2,3 ?

hippie, уже не актуально, но спасибо )

-- 26.06.2013, 18:54 --

Или легче всего опустить п.2 и доказать, что $R(4, 4) \le 20$