Многоугольник

DarkMel
Сообщений: 124
Зарегистрирован: 10 июн 2012, 21:00

Многоугольник

Сообщение DarkMel » 20 июн 2013, 23:12

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

Какие есть мысли? Как доказать, что такое может быть всегда?

У нас 252 диагонали..
Верно ли то, что худший случай для нас - это когда 12 сторон в один цвет, 12 - в другой и 126 диагоналей в один цвет, 126 - в другой? Если да, то нужно ли это в задаче? Как доказать?

Используется теория графов или нет? Уже второй день никакой
Последний раз редактировалось DarkMel 28 ноя 2019, 13:34, всего редактировалось 1 раз.
Причина: test

Аватар пользователя
Ian
Сообщений: 5455
Зарегистрирован: 28 июл 2009, 21:00

Многоугольник

Сообщение Ian » 21 июн 2013, 08:02

Лемма про 6-угольник и 3 вершины надо взять (она носит имя, к сожалению забыл. А по нему и решение этой задачи в сети найдется)
Возьмем вершину а, ребра в остальные 5 -как минимум 3 одного цвета, пусть для определенности это цвет А. Тогда 1) если между этими тремя есть ребро цвета А, то вместе с а это ребро дает искомый треугольник 2) если между этими тремя нет ребра цвета А, то они образуют треугольник цвета В
Ну а это обобщение леммы с 6=3! на 24=4!
Последний раз редактировалось Ian 28 ноя 2019, 13:34, всего редактировалось 1 раз.
Причина: test

СергейП
Сообщений: 4145
Зарегистрирован: 17 июл 2009, 21:00

Многоугольник

Сообщение СергейП » 21 июн 2013, 09:28

Ian писал(а):Source of the post ...она носит имя, к сожалению забыл. А по нему и решение этой задачи в сети найдется...
Я вот тоже имя не могу вспомнить, но помнится что это венгр.
Можно по венгерским математикам поискать
Последний раз редактировалось СергейП 28 ноя 2019, 13:34, всего редактировалось 1 раз.
Причина: test

Аватар пользователя
Ian
Сообщений: 5455
Зарегистрирован: 28 июл 2009, 21:00

Многоугольник

Сообщение Ian » 21 июн 2013, 09:42

Совместными усилиями нашли ) [url=http://ru.wikipedia.org/wiki/Теория_Рамсея]http://ru.wikipedia.org/wiki/Теория_Рамсея[/url]
А факториал тут ни при чем даже для 18-угольника утверждение пост 1 верно-глава Finding R(4,4)
Последний раз редактировалось Ian 28 ноя 2019, 13:34, всего редактировалось 1 раз.
Причина: test

DarkMel
Сообщений: 124
Зарегистрирован: 10 июн 2012, 21:00

Многоугольник

Сообщение DarkMel » 24 июн 2013, 08:51

Ian писал(а):Source of the post
Совместными усилиями нашли ) [url=http://ru.wikipedia.org/wiki/Теория_Рамсея]http://ru.wikipedia.org/wiki/Теория_Рамсея[/url]
А факториал тут ни при чем даже для 18-угольника утверждение пост 1 верно-глава Finding R(4,4)

Спасибо! Я смотрел теорему Рамсея.. Тут вот как получается.. Число Рамсея характеризует минимально возможный полный граф, чтобы выполнялись условия задачи. Это 18. А у нас 24 - хватит за глаза.
Но видимо, это-то и надо доказать, не опираясь на информацию извне. Ведь точно найти число Рамсея сложно, но получить для него какую-то оценку должно быть легче.
Есть какие-то идеи, как можно получить оценку? И с чего начать вообще..
Последний раз редактировалось DarkMel 28 ноя 2019, 13:34, всего редактировалось 1 раз.
Причина: test

Аватар пользователя
Hottabych
Сообщений: 1807
Зарегистрирован: 25 ноя 2007, 21:00

Многоугольник

Сообщение Hottabych » 24 июн 2013, 10:02

DarkMel писал(а):Source of the post
Есть какие-то идеи, как можно получить оценку? И с чего начать вообще..

С принципа Дирихле
Последний раз редактировалось Hottabych 28 ноя 2019, 13:34, всего редактировалось 1 раз.
Причина: test

DarkMel
Сообщений: 124
Зарегистрирован: 10 июн 2012, 21:00

Многоугольник

Сообщение DarkMel » 24 июн 2013, 19:50

Hottabych писал(а):Source of the post
DarkMel писал(а):Source of the post
Есть какие-то идеи, как можно получить оценку? И с чего начать вообще..

С принципа Дирихле

А каким методом именно?.. С чего начать.. пока не могу разобраться, что тут кролик))
А если серьезно, то о какой оценке идет речь, я понимаю, что она есть, но не имею представления о механизме её получения.
Например, можно попробовать доказать, что R(4, 4)>17... как так сделать, чтобы довольно коротко получилось?
Последний раз редактировалось DarkMel 28 ноя 2019, 13:34, всего редактировалось 1 раз.
Причина: test

Аватар пользователя
Ian
Сообщений: 5455
Зарегистрирован: 28 июл 2009, 21:00

Многоугольник

Сообщение Ian » 25 июн 2013, 06:57

DarkMel писал(а):Source of the post доказать, что R(4, 4)>17... как так сделать, чтобы довольно коротко получилось?
Пример дать. [url=http://plus.maths.org/content/proving-r4417]http://plus.maths.org/content/proving-r4417[/url] Нарисовать по инструкции а внизу написать слово "смотри")
Последний раз редактировалось Ian 28 ноя 2019, 13:34, всего редактировалось 1 раз.
Причина: test

DarkMel
Сообщений: 124
Зарегистрирован: 10 июн 2012, 21:00

Многоугольник

Сообщение DarkMel » 26 июн 2013, 16:58

Ian писал(а):Source of the post
DarkMel писал(а):Source of the post доказать, что R(4, 4)>17... как так сделать, чтобы довольно коротко получилось?
Пример дать. [url=http://plus.maths.org/content/proving-r4417]http://plus.maths.org/content/proving-r4417[/url] Нарисовать по инструкции а внизу написать слово "смотри")

Мне кажется легче всего в этой задаче просто доказать, что

1) $$R(a, b) \le R(a-1, b) + R(a, b-1)$$
2) $$R(3, 3)=6, R(2, 4)=4$$
3) Из 1,2 $$R(3, 4) \le 10$$
4) Из 1,3 $$R(4, 4) \le 20$$

Вывод: $$R(4, 4) < 24$$
Последний раз редактировалось DarkMel 28 ноя 2019, 13:35, всего редактировалось 1 раз.
Причина: test

arojda1
Сообщений: 4
Зарегистрирован: 26 июн 2013, 21:00

Многоугольник

Сообщение arojda1 » 01 июл 2013, 18:21

Если вопрос не потерял актуальность, могу доказать, что из 20 точек найдутся 4, соед. отрезками одного цвета.
Тут нужна будет ещё одна Лемма-2, следующая очевидным образом из упомянутой Леммы-1 о шести точках.
Только, для начала, немного терминологии, чтобы побыстрее. Назовём «связью типа А», если точки соед. отрезком цвета «А», ну и «В», соответственно. «Общество А» - 4 точки соединённые только отрезками цвета «А», и «В», соответственно.
Так вот, Лемма-2:
Если каждая из множества шести точек имеет «связь типа А» с какой-либо точкой вне множества и «связь типа В» с другой точкой вне этого множества, то среди этих восьми точек есть «Общество А» или «В», в зависимости от того, какого цвета там треугольник.
Теперь рассмотрим некую точку (назовём её – «Исходная точка»), имеющую «связь, например, типа А» с 10-ю точками. Каждая из этих десяти (пусть называется – «Вторая точка») точек имеет «связь типа А», как минимум, с четырьмя другими из оставшихся девяти. В противном случае, она имеет «связь типа В» с не менее, чем шестью точками этого множества, и приводит нас к Лемме-2.
Если какие-то две из этих четырёх точек имеют между собой «связь типа А», то мы имеем «общество А», состоящее из «исходной», «второй» и этих двух точек. Если нет, то мы имеем «общество В» из этих четырех точек.
DarkMel, 18 точек пока не одолел, но изначально, Вам, вроде, нужно было 24. И может кого-нибудь это натолкнёт на мысль, как разобраться с 18-ю.
Последний раз редактировалось arojda1 28 ноя 2019, 13:35, всего редактировалось 1 раз.
Причина: test


Вернуться в «Школьная математика»

Кто сейчас на форуме

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