2017 точек на поверхности и задача о построении векторов

[daogiauvang]

Даны 2017 точек на поверхности, которые ни одних три точек на одной прямой линии. через каждые любые две точки $X,Y$ мы построим вектор $XY$ или $YX$. Множество $S$ - это набор 3 точек, удовлетворяющих условию сумма трех векторов рана вектору 0. Найти максимальное и минимальное значение множества $S$.

[svv]

daogiauvang в сообщении #1153017 писал(а):

Даны 2017 точек на поверхности, которые ни одних три точек на одной прямой линии

На плоскости даны 2017 точек, из которых никакие три не лежат на одной прямой.

Не знаю, что такое значение множества $S$, но ни больше, ни меньше трёх элементов в нём не может быть по условию задачи.

-- Вт сен 20, 2016 13:35:38 --

Может быть, имеется в виду вот что. Каждой паре точек $X,Y$ мы должны сопоставить один из двух векторов: $\vec{XY}$ или $\vec{YX}$. Если мы выбрали вектор $\vec{XY}$, то вектор $\vec{YX}$ использовать уже не можем. Требуется найти минимально возможное и максимально возможное количество таких наборов из трёх точек, что сумма векторов, сопоставленных каждой паре точек из набора, равна $\vec 0$.

[atlakatl]

svv
Похоже на google-перевод с китайского. Обсуждения здесь преждевременны.
daogiauvang
Вас трудно понять. Если Вы не китаец, переформулируйте задачу.

[daogiauvang]

svv в сообщении #1153058 писал(а):

daogiauvang в сообщении #1153017 писал(а):

Даны 2017 точек на поверхности, которые ни одних три точек на одной прямой линии

На плоскости даны 2017 точек, из которых никакие три не лежат на одной прямой.

Не знаю, что такое значение множества $S$, но ни больше, ни меньше трёх элементов в нём не может быть по условию задачи.

-- Вт сен 20, 2016 13:35:38 --

Может быть, имеется в виду вот что. Каждой паре точек $X,Y$ мы должны сопоставить один из двух векторов: $\vec{XY}$ или $\vec{YX}$. Если мы выбрали вектор $\vec{XY}$, то вектор $\vec{YX}$ использовать уже не можем. Требуется найти минимально возможное и максимально возможное количество таких наборов из трёх точек, что сумма векторов, сопоставленных каждой паре точек из набора, равна $\vec 0$.

Ваше понимание все верно. Я иностранец, а не китаец.

[svv]

Спасибо. В таком случае, вот иная формулировка задачи.

Возьмём полный граф с $n=2017$ вершинами. Произвольным образом приписав каждому ребру направление, превратим его в ориентированный. Нас интересуют ориентированные (согласованные с направлением рёбер) циклы длиной $3$. Какое максимальное и минимальное их количество может получиться?

-- Вт сен 20, 2016 17:14:56 --

Минимальное — ни одного. Перенумеруем вершины. Каждое ребро направим от вершины с меньшим номером к вершине с большим. Идя по направлению рёбер, вернуться в исходную точку не сможем.

[DeBill]

Оценка:
Пусть $2017 = n$ - нечетно.
Всего треугольников $N = C^3_n$.
Каждый треугольник либо хороший (ребра образуют цикл), либо плохой (и тогда есть вершина, откуда выходит два ребра, есть вершина, куда приходит два ребра, ну, и есть нейтральная вершина.) Пусть в некоторую вершину графа приходит $x$ ребер, а выходит - $y$, $x+y = n-1$. Тогда с этой вершиной есть заведомо $C^2_x + C^2_y$ плохих треугольников, и эта сумма не меньше чем $\frac{n-1}{2}\cdot (\frac{n-1}{2}-1)$. Поэтому плохих не меньше чем $\frac{2017\cdot 1008 \cdot 1007}{2}$ (каждый плохой сосчитан дважды) из общего числа $\frac{2017\cdot 2016 \cdot 2015}{6}$.....
Пример: расставим точки по кругу, и каждую соединим стрелкой с половиной остальных - а именно, с теми, кто - по направлению по часовой стрелке - ближе прочих. Оценка превратится в равенство.

[daogiauvang]

DeBill в сообщении #1153100 писал(а):

Оценка:
Пусть $2017 = n$ - нечетно.
Всего треугольников $N = C^3_n$.
Каждый треугольник либо хороший (ребра образуют цикл), либо плохой (и тогда есть вершина, откуда выходит два ребра, есть вершина, куда приходит два ребра, ну, и есть нейтральная вершина.) Пусть в некоторую вершину графа приходит $x$ ребер, а выходит - $y$, $x+y = n-1$. Тогда с этой вершиной есть заведомо $C^2_x + C^2_y$ плохих треугольников, и эта сумма не меньше чем $\frac{n-1}{2}\cdot (\frac{n-1}{2}-1)$. Поэтому плохих не меньше чем $\frac{2017\cdot 1008 \cdot 1007}{2}$ (каждый плохой сосчитан дважды) из общего числа $\frac{2017\cdot 2016 \cdot 2015}{6}$.....
Пример: расставим точки по кругу, и каждую соединим стрелкой с половиной остальных - а именно, с теми, кто - по направлению по часовой стрелке - ближе прочих. Оценка превратится в равенство.

Я не понимаю, почему каждый плохой сосчитан дважды, по-моему трижды.

[alcoholist]

(Оффтоп)

daogiauvang в сообщении #1153084 писал(а):

Я иностранец,а но не китаец.

[ИСН]

daogiauvang в сообщении #1153102 писал(а):

Я не понимаю, почему каждый плохой сосчитан дважды, по-моему трижды.

Одна вершина фиксирована. Расматриваем все тройки с этой вершиной.

[DeBill]

daogiauvang в сообщении #1153102 писал(а):

почему каждый плохой сосчитан дважды, по-моему трижды.

Нет, дважды:

daogiauvang в сообщении #1153102 писал(а):

плохой (и тогда есть вершина, откуда выходит два ребра, есть вершина, куда приходит два ребра, ну, и есть нейтральная вершина.)

По "нейтральным" вершинам, счет не производился

-- 20.09.2016, 20:58 --

Проверьте все рассуждения на примере, для $n=5$, или $n=7$.
Для четного $n$ - те же рассуждения, только теперь нечетное $n-1$ надо разбивать в сумму "почти" равных. И пример будет чуть сложнее: надо стрелки рисовать в точки на "ближней полуокружности по часовой стрелке", Ну, а на "диаметрах" расставить стрелки произвольно. И формула будет другая.

[daogiauvang]

Спасибо Вам, ИСН, DeBill и SVV.