2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Точки и прямые
Сообщение12.08.2013, 20:22 
Заслуженный участник
Аватара пользователя


03/12/11
640
Україна

(Оффтоп)

Навеяна под впечатлением от 2 задачи IMO 2013. Интересно, сложнее она или проще? :?
На плоскости расположено $n$ точек, никакие три из которых не лежат на одной прямой. Каким минимальным количеством прямых, не проходящих ни через одну из этих точек, наверняка можно разделить плоскость на области, в каждой из которых находится не более одной из заданных точек?

 Профиль  
                  
 
 Re: Точки и прямые
Сообщение12.08.2013, 20:36 
Аватара пользователя


11/06/12
10390
стихия.вздох.мюсли
Я, возможно, туплю, но разве не $n-1$?

 Профиль  
                  
 
 Re: Точки и прямые
Сообщение12.08.2013, 20:38 


06/09/12
890
Aritaborian в сообщении #754218 писал(а):
Я, возможно, туплю, но разве не $n-1$?

Именно.

 Профиль  
                  
 
 Re: Точки и прямые
Сообщение12.08.2013, 20:43 
Заслуженный участник
Аватара пользователя


03/12/11
640
Україна
Aritaborian в сообщении #754218 писал(а):
Я, возможно, туплю, но разве не $n-1$?
Вообще говоря, нет.

 Профиль  
                  
 
 Re: Точки и прямые
Сообщение12.08.2013, 21:10 
Аватара пользователя


11/06/12
10390
стихия.вздох.мюсли
Возьмём $n$ точек с координатами $(i,\frac1i)$, $i=1,...,n$. Разве их можно отделить друг от друга менее чем $n-1$ прямыми?

 Профиль  
                  
 
 Re: Точки и прямые
Сообщение12.08.2013, 21:20 
Заслуженный участник
Аватара пользователя


03/12/11
640
Україна
А почему же нельзя?

 Профиль  
                  
 
 Re: Точки и прямые
Сообщение12.08.2013, 21:21 
Аватара пользователя


11/06/12
10390
стихия.вздох.мюсли
Но как? :?

 Профиль  
                  
 
 Re: Точки и прямые
Сообщение12.08.2013, 21:24 
Заслуженный участник
Аватара пользователя


03/12/11
640
Україна
Это уже будет подсказкой.

 Профиль  
                  
 
 Re: Точки и прямые
Сообщение12.08.2013, 21:24 
Аватара пользователя


29/08/12
40
Вечно зеленый
зведочкой

 Профиль  
                  
 
 Re: Точки и прямые
Сообщение13.08.2013, 10:53 


04/06/12
393
Предположение - $\left[\frac{n+1}{2}\right]$.

 Профиль  
                  
 
 Re: Точки и прямые
Сообщение13.08.2013, 16:26 
Заслуженный участник
Аватара пользователя


23/08/07
5420
Нов-ск
Aritaborian в сообщении #754243 писал(а):
Но как? :?
Прямой делим все точки на две равные (почти) части синего и красного цвета. Затем прямой линией от кучи красных и кучи синих отрезаем по одной точке. Затем еще по одной, затем еще и т.д.

 Профиль  
                  
 
 Re: Точки и прямые
Сообщение13.08.2013, 16:30 
Аватара пользователя


11/06/12
10390
стихия.вздох.мюсли
Кажется, понял ;-)

 Профиль  
                  
 
 Re: Точки и прямые
Сообщение13.08.2013, 17:37 


11/02/12
36
извините,но я не понял,а что нельзя взять выпуклую оболочку ,а потом отрезать по две точки этой оболочки?

 Профиль  
                  
 
 Re: Точки и прямые
Сообщение13.08.2013, 19:04 
Заслуженный участник
Аватара пользователя


03/12/11
640
Україна
TOTAL в сообщении #754477 писал(а):
Затем прямой линией от кучи красных и кучи синих отрезаем по одной точке.
Нужно ещё строго обосновать, почему это всегда возможно.

 Профиль  
                  
 
 Re: Точки и прямые
Сообщение13.08.2013, 19:42 
Заслуженный участник
Аватара пользователя


23/08/07
5420
Нов-ск
Dave в сообщении #754522 писал(а):
TOTAL в сообщении #754477 писал(а):
Затем прямой линией от кучи красных и кучи синих отрезаем по одной точке.
Нужно ещё строго обосновать, почему это всегда возможно.

А вот тут пригодится вышеупомянутая выпуклая оболочка, два ребра которой разноцветны, любое из них и отрезаем.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 22 ]  На страницу 1, 2  След.

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



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

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


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

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