2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 2017 точек на поверхности и задача о построении векторов
Сообщение20.09.2016, 07:15 
Аватара пользователя


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

 Профиль  
                  
 
 Re: 2017 точек на поверхности и задача о построении векторов
Сообщение20.09.2016, 13:19 
Заслуженный участник


23/07/08
10626
Crna Gora
daogiauvang в сообщении #1153017 писал(а):
Даны 2017 точек на поверхности, которые ни одних три точек на одной прямой линии
На плоскости даны 2017 точек, из которых никакие три не лежат на одной прямой.

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

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

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

 Профиль  
                  
 
 Re: 2017 точек на поверхности и задача о построении векторов
Сообщение20.09.2016, 13:40 
Аватара пользователя


21/09/12

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

 Профиль  
                  
 
 Re: 2017 точек на поверхности и задача о построении векторов
Сообщение20.09.2016, 16:41 
Аватара пользователя


21/06/08
476
Томск
svv в сообщении #1153058 писал(а):
daogiauvang в сообщении #1153017 писал(а):
Даны 2017 точек на поверхности, которые ни одних три точек на одной прямой линии
На плоскости даны 2017 точек, из которых никакие три не лежат на одной прямой.

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

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

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

 Профиль  
                  
 
 Re: 2017 точек на поверхности и задача о построении векторов
Сообщение20.09.2016, 17:11 
Заслуженный участник


23/07/08
10626
Crna Gora
Спасибо. В таком случае, вот иная формулировка задачи.

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

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

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

 Профиль  
                  
 
 Re: 2017 точек на поверхности и задача о построении векторов
Сообщение20.09.2016, 18:17 
Заслуженный участник


10/01/16
2315
Оценка:
Пусть $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}$.....
Пример: расставим точки по кругу, и каждую соединим стрелкой с половиной остальных - а именно, с теми, кто - по направлению по часовой стрелке - ближе прочих. Оценка превратится в равенство.

 Профиль  
                  
 
 Re: 2017 точек на поверхности и задача о построении векторов
Сообщение20.09.2016, 18:33 
Аватара пользователя


21/06/08
476
Томск
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}$.....
Пример: расставим точки по кругу, и каждую соединим стрелкой с половиной остальных - а именно, с теми, кто - по направлению по часовой стрелке - ближе прочих. Оценка превратится в равенство.

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

 Профиль  
                  
 
 Re: 2017 точек на поверхности и задача о построении векторов
Сообщение20.09.2016, 18:39 
Заслуженный участник
Аватара пользователя


22/01/11
2641
СПб

(Оффтоп)

daogiauvang в сообщении #1153084 писал(а):
Я иностранец,а но не китаец.

 Профиль  
                  
 
 Re: 2017 точек на поверхности и задача о построении векторов
Сообщение20.09.2016, 19:00 
Заслуженный участник
Аватара пользователя


18/05/06
13435
с Территории
daogiauvang в сообщении #1153102 писал(а):
Я не понимаю, почему каждый плохой сосчитан дважды, по-моему трижды.

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

 Профиль  
                  
 
 Re: 2017 точек на поверхности и задача о построении векторов
Сообщение20.09.2016, 19:48 
Заслуженный участник


10/01/16
2315
daogiauvang в сообщении #1153102 писал(а):
почему каждый плохой сосчитан дважды, по-моему трижды.

Нет, дважды:
daogiauvang в сообщении #1153102 писал(а):
плохой (и тогда есть вершина, откуда выходит два ребра, есть вершина, куда приходит два ребра, ну, и есть нейтральная вершина.)

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

-- 20.09.2016, 20:58 --

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

 Профиль  
                  
 
 Re: 2017 точек на поверхности и задача о построении векторов
Сообщение21.09.2016, 09:31 
Аватара пользователя


21/06/08
476
Томск
Спасибо Вам, ИСН, DeBill и SVV.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 11 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

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


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group