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

[kinoman84]

Помогите, пожалуйста, в решении двух следующих задач.

1. Плоскость произвольно заполнена точками количества n. Доказать, что при любом n всегда можно провести прямую, которая не пройдет ни через одну из них.

Собственная попытка решения:
Проведем через каждые две точки прямую. После этого у нас будут пространства между прямыми. Поставим две точки в этих свободных участках и проведем прямую. Но она теоретически может коснуться хотя бы одной (не больше) точки помимо этих двух.

2. Внутри окружности произвольно раскиданы 50 точек. Доказать, что всегда можно провести прямую, которая не коснется ни одну из них и разделит их ровно пополам по 25 штук.

Собственная попытка решения:
Проведем прямую через одну из точек и начнем вращать ее словно точка это ось. Прямая однажды разделит окружность на две области и в каждой будет примерно по 25 точек. Но это рассуждение не конкретное и туманное. Дальше мыслей нет.

[ozheredov]

kinoman84 в сообщении #1703735 писал(а):

1.

Возьмем произвольную прямую $L$. Рассмотрим совокупность проекций Ваших точек на прямую $L$ - это просто $n$ чисел, среди которых есть $\min$ и $\max$. Возмем точку на прямой $L$ которая лежит вне диапазона $\min - \max$, и проведем через нее прямую $L_1$, перпендикулярную прямой $L$. Будет она ответом к задаче?

[realeugene]

kinoman84
Если у вас есть бесконечное множество и конечное его подмножество, то существуют элементы бесконечного множества, не входящие в это конечное подмножество. Подумайте, как строго доказать это утверждение, и как можно им затем воспользоваться для доказательства обоих утверждений в вашей задаче?

[TOTAL]

kinoman84 в сообщении #1703735 писал(а):

2. Внутри окружности произвольно раскиданы 50 точек. Доказать, что всегда можно провести прямую, которая не коснется ни одну из них и разделит их ровно пополам по 25 штук.

Это неверное утверждение, не доказывается.

[dgwuqtj]

TOTAL в сообщении #1703765 писал(а):

Это неверное утверждение, не доказывается.

Доказывается: выберем достаточно общее направление и поделим прямой с этим направлением. Если вращать, то правда как-то всё мутно

[TOTAL]

dgwuqtj в сообщении #1703767 писал(а):

TOTAL в сообщении #1703765 писал(а):

Это неверное утверждение, не доказывается.

Доказывается:

Точки раскиданы произвольно. Я их все одну в одну раскидаю, делите.

[dgwuqtj]

Тогда это одна точка, а не 50... Или я слишком творчески понял условие.

[TOTAL]

dgwuqtj в сообщении #1703771 писал(а):

Тогда это одна точка, а не 50... Или я слишком творчески понял условие.

Условие кривовато. Например, когда говорят, что взяты произвольные целые числа, то могут уточнять, что они различные. Так и с этими точками надо бы поаккуратнее.

-- Пн сен 29, 2025 23:50:37 --

kinoman84 в сообщении #1703735 писал(а):

2. Внутри окружности произвольно раскиданы 50 точек. Доказать, что всегда можно провести прямую, которая не коснется ни одну из них и разделит их ровно пополам по 25 штук.

Собственная попытка решения:
Проведем прямую через одну из точек и начнем вращать ее словно точка это ось.

Сначала через каждую пару точек проведите прямую.
На плоскости останется точка, через которую не проходит ни одна из прямых?
Если останется, то эту точку берите в качестве центра вращения искомой "делительной" прямой.

[Shadow]

kinoman84 в сообщении #1703735 писал(а):

1. Плоскость произвольно заполнена точками количества n. Доказать, что при любом n всегда можно провести прямую, которая не пройдет ни через одну из них.

А давайте "усложним" задачу....что через точку $(0;0)$ (если конечно она не одна из них) можно провести бесконечно много таких прямых.

[Евгений Машеров]

1. Проведём линию через две произвольные точки. Затем рассмотрим линии, параллельные ей, проходящие через прочие точки. Их конечное число (не более, чем $n-2$)
Затем выберем параллельную первой линию, не совпадающую с прочими рассмотренными линиями.
2. (Оговорим, что точки несовпадающие)
Проведём все возможные линии, соединяющие пары точек и затем линию, непараллельную ни одной из них. Будем её сдвигать параллельно самой себе, подсчитывая число точек по каждую сторону. Поскольку она непараллельна ни одной из линий, соединяющих точки, по мере сдвигания число точек по одну сторону от этой линии будет меняться не более, чем на единицу.Досчитываем до 25 точек и радуемся.

[TOTAL]

Евгений Машеров в сообщении #1703830 писал(а):

1. Проведём линию через две произвольные точки. Затем рассмотрим линии, параллельные ей, проходящие через прочие точки. Их конечное число (не более, чем $n-2$)
Затем выберем параллельную первой линию, не совпадающую с прочими рассмотренными линиями.

Сразу проведём $n+1$ параллельных друг другу линий. Одна из них точно свободна от заданных зловредных точек.

[kinoman84]

Спасибо за ответы!

Евгений Машеров

Цитата:

Проведём все возможные линии, соединяющие пары точек и затем линию, непараллельную ни одной из них. Будем её сдвигать параллельно самой себе, подсчитывая число точек по каждую сторону. Поскольку она непараллельна ни одной из линий, соединяющих точки, по мере сдвигания число точек по одну сторону от этой линии будет меняться не более, чем на единицу.Досчитываем до 25 точек и радуемся.

Тут смущает "и затем линию, непараллельную ни одной из них". Как это реализовать? Нет ли более изящного способа?

Shadow

Цитата:

А давайте "усложним" задачу....что через точку $(0;0)$ (если конечно она не одна из них) можно провести бесконечно много таких прямых.

Нет соображений на этот счет.

[Shadow]

kinoman84 в сообщении #1703836 писал(а):

Нет соображений на этот счет.

Да ладно, семейство всех прямых, проходящих через точку $(0;0)$ имеют вид $y=kx$ (и еще $x=0$, но она не интересна). Нам нужно подобрать такое $k$, чтобы наша прямая не проходила через некоторых заданных точек. Как?
Ну, например - нельзя проходить через $(1;2)$. Какое условие надо наложить на $k$?

[kinoman84]

ozheredov

Цитата:

Возьмем произвольную прямую $L$. Рассмотрим совокупность проекций Ваших точек на прямую $L$ - это просто $n$ чисел, среди которых есть $\min$ и $\max$. Возмем точку на прямой $L$ которая лежит вне диапазона $\min - \max$, и проведем через нее прямую $L_1$, перпендикулярную прямой $L$. Будет она ответом к задаче?

К сожалению, не понимаю что значит $\min$ и $\max$. Получается, нужно будет просто провести перпендикуляр к нашей прямой, не совпадающий ни с одним из предыдущих?

-- 30.09.2025, 11:06 --

Shadow

Цитата:

Ну, например - нельзя проходить через $(1;2)$. Какое условие надо наложить на $k$?

В данном случае $k\ne2$

[Shadow]

kinoman84 в сообщении #1703843 писал(а):

Получается, нужно будет просто провести перпендикуляр к нашей прямой, не совпадающий ни с одним из предыдущих?

Просто нужно провести прямую $y=C$ (параллельную оси абсцисс), где $C$ достаточно большое, или маленькое. (Не работает при счетном множетстве точек, но при конечном - вполне)

-- 30.09.2025, 09:11 --

kinoman84 в сообщении #1703843 писал(а):

В данном случае $k\ne2$

Да, еще несколько таких условий $k \ne$. А все остальное можно.