Комбинаторная геометрия
Комбинаторная геометрия
Перевод: На плоскости проведены n прямых, разбивающих ее на некоторое множество многоугольников С. Доказать , что сумма квадратов чисел вершин этих многоугольников оценивается константой на [math]
Мне кажется, разрешены и неограниченные многоугольники.Наличие пересечений трех и более прямых в одной точке, или параллельных прямых, только уменьшают оцениваемую сумму, поэтому будем считать что их нет. Тогда общее число вершин [math], а областей [math] ,но это ничего не дает.
Если даже среди областей есть n- угольник, это не гарантирует, что все остальные области будут треугольниками, например n=9- прямые . являющиеся продолжением сторон правильного 9-угольника, образуют и как минимум 9 4-угольников. В общем, задача похожа на олимпиадную
Комбинаторная геометрия
Ian писал(а):Source of the post Наличие пересечений трех и более прямых в одной точке, или параллельных прямых
Да, это существенно.
Для пересекающихся в одной точке, или для параллельных (пересекающихся в бесконечной точке), рост мог бы быть линейным.
Ian писал(а):Source of the post а областей
Это сразу даёт квадратное ограничение снизу. Остаётся только ограничить квадратно сверху.
Да, как-то оно не просто выглядит. Один многоугольник может иметь много вершин - вплоть до .
Но при этом другие не могут иметь много вершин. В этом всё дело. Вопрос в том, как это формализовать.
Наверно надо как-то с углами похимичить. Там сумма для каждого многоугольника.
Все они выпуклые, значит внешний угол , и если много вершин, то в своей массе эти внешние углы должны быть маленькие.
Но для большого числа многоугольников этого не может быть, т.к. сами эти углы - это углы между каким-то двумя прямыми из этих , а все они не могут быть маленькими.
Вобщем интуитивно, что-то в этом направлении.
Комбинаторная геометрия
Вот еще две задачи в том же духе.
Вольные переводы.
3. Есть (n-1)! перестановок чисел 1,2,...n, расположенных по окружности, далее кратко называемых "круговыми перестановками" . На плоскости есть n пронумерованных точек общего положения, никакие три не на одной прямой и никакие 4 не вершины трапеции. Рассмотрим для каждой иной точки плоскости круговую перестановку- порядок видения n точек при повороте наблюдателя из данной точки против часовой стрелки. Рассмотрим, сколько разных круговых перестановок можно получить изменением точки наблюдателя. Доказать, что это число оценивается снизу константой на [math]
5. M- множество из n точек общего положения (никакие три не лежат на одной прямой). Говорят, что множество P "прокалывающее треугольники" для множества M, если во внутренности всякого треугольника с тремя разными вершинами из М найдется точка множества Р. Доказать, что найдется P из (2n-5) точек, а из (2n-6) не обязательно.
Вольные переводы.
3. Есть (n-1)! перестановок чисел 1,2,...n, расположенных по окружности, далее кратко называемых "круговыми перестановками" . На плоскости есть n пронумерованных точек общего положения, никакие три не на одной прямой и никакие 4 не вершины трапеции. Рассмотрим для каждой иной точки плоскости круговую перестановку- порядок видения n точек при повороте наблюдателя из данной точки против часовой стрелки. Рассмотрим, сколько разных круговых перестановок можно получить изменением точки наблюдателя. Доказать, что это число оценивается снизу константой на [math]
5. M- множество из n точек общего положения (никакие три не лежат на одной прямой). Говорят, что множество P "прокалывающее треугольники" для множества M, если во внутренности всякого треугольника с тремя разными вершинами из М найдется точка множества Р. Доказать, что найдется P из (2n-5) точек, а из (2n-6) не обязательно.
Комбинаторная геометрия
Соображения по 3й. Понятно, что число прямых проведенных через каждую пару точек [math], а число областей, на которые они делят плоскость, [math]. Раскрасим каждую прямую так: отрезок между точками в красный цвет, а оставшиеся два луча -в синий цвет. При переходе из области в соседнюю через красную границу - круговая перестановка не меняется, а через синюю -обязательно меняется (умножается на транспозицию соседних точек).
1. Есть возможность доказать, что только синие лучи -разбивают плоскость на число частей, оцениваемых снизу константой на [math]
2. Но этого мало, для n=3 у нас (после стирания красных отрезков) 4 области на плоскости, а число круговых перестановок 2!=2 всего. То есть нет гарантии, что в разных несоседних областях - сидят разные круговые перестановки.
1. Есть возможность доказать, что только синие лучи -разбивают плоскость на число частей, оцениваемых снизу константой на [math]
2. Но этого мало, для n=3 у нас (после стирания красных отрезков) 4 области на плоскости, а число круговых перестановок 2!=2 всего. То есть нет гарантии, что в разных несоседних областях - сидят разные круговые перестановки.
Последний раз редактировалось Ian 31 янв 2021, 08:47, всего редактировалось 1 раз.
Комбинаторная геометрия
Ну это наверно не олимпиадные задачи, а задачник по теме "Комбинаторная геометрия".
Если в олимпиадных ещё можно догадаться логически, то в задачнике обычно рассчитано на то, что студент изучил теорию. А там есть сложные теоремы, которые так просто, с пол пинка, не докажешь.
Я с этой теорией не сталкивался. Только так, мимоходом, какие-нибудь простые олимпиадные задачи.
Если в олимпиадных ещё можно догадаться логически, то в задачнике обычно рассчитано на то, что студент изучил теорию. А там есть сложные теоремы, которые так просто, с пол пинка, не докажешь.
Я с этой теорией не сталкивался. Только так, мимоходом, какие-нибудь простые олимпиадные задачи.
Комбинаторная геометрия
Даже не задачник, а задания студентам из Праги. Мне тоже интересно, в чем у них состояла теория, если она позволяет такое решить.
Комбинаторная геометрия
Не знаю, никогда этим не занимался.
Вот например студентам курс предлагали:
https://page.mi.fu-berlin.de/sanyal/teaching/dg1/
Там в списке литературы:
Можно посмотреть, что там за теоремы у них имеются.
Например вот это может иметь отношение к таким задачам:
Combinatorial geometry / Geometric combinatorics
Вот например студентам курс предлагали:
https://page.mi.fu-berlin.de/sanyal/teaching/dg1/
Там в списке литературы:
- Arne Brondsted, An Introduction to Convex Polytopes, Springer GTM 90
- Branko Grünbaum Convex Polytopes, Springer GTM 221 (Second Edition)
- Gil Kalai, Günter Ziegler, Polytopes - Combinations and Computation, Birkhäuser DMV Seminar, Band 29
- Peter Gruber Convex and discrete Geometry, Springer Grundlehren 336
- Jirka Matousek, Lectures on Discrete Geometry, Springer GTM 212
- Peter McMullen, Geoffrey Shephard, Convex polytopes and the upper bound conjecture, LMS Lecture Notes 3
- Günter Ziegler, Lectures on Polytopes, Springer GTM 152
Можно посмотреть, что там за теоремы у них имеются.
Например вот это может иметь отношение к таким задачам:
Combinatorial geometry / Geometric combinatorics
- Arrangements of points and lines, Sylvester-Gallai, Erdos-Szekeres,
- Szemeredi--Trotter
- Arrangements, zonotopes, zonotopal tilings, oriented matroids
Комбинаторная геометрия
По поводу задачи 1 видимо вот это подходит: Complexity of arrangements.
Там сказано: "Summing the complexities of all zones, one finds that the sum of squares of cell complexities in an arrangement is ".
И дана ссылка [7]: Aronov, B.; Matoušek, J.; Sharir, M. (1994), "On the sum of squares of cell complexities in hyperplane arrangements", Journal of Combinatorial Theory, Series A, 65 (2): 311–321.
Там сказано: "Summing the complexities of all zones, one finds that the sum of squares of cell complexities in an arrangement is ".
И дана ссылка [7]: Aronov, B.; Matoušek, J.; Sharir, M. (1994), "On the sum of squares of cell complexities in hyperplane arrangements", Journal of Combinatorial Theory, Series A, 65 (2): 311–321.
Комбинаторная геометрия
Более фундаментальный результат тут - это Szemerédi–Trotter theorem.
Кто сейчас на форуме
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 13 гостей