На плоскости отмечены $%17$% точек, не лежащих на одной прямой (т.е. найдутся хотя бы $%3$% точки, не лежащие на одной прямой). Через каждые две точки провели прямую. Какое наименьшее количество различных прямых могло получиться?

задан 4 Окт '17 6:36

10|600 символов нужно символов осталось
1

Есть такой общий факт: теорема Эрдёша - де Брёйна. Если на плоскости дано n точек, из которых не все лежат на одной прямой, то прямых, проходящих через эти точки, также будет не менее n. Доказывается он не просто. См. здесь соответствующее рассуждение. Таким образом, наименьшее число прямых равно 17. Пример строится легко: берём 16 точек на одной прямой, одну точку отдельно, и через неё проводим ещё 16 прямых.

Для разнообразия рассмотрим ещё один способ решения при помощи линейной алгебры. Допустим, что прямых проведено m < n. Около каждой точки запишем неизвестную x(i), где 1<=i<=n. Для каждой прямой составим однородное линейное уравнение: сумма неизвестных для точек этой прямой равна нулю. Уравнений меньше, чем переменных, и такая однородная система имеет ненулевое решение. Теперь покажем, что так оказаться не могло, то есть на самом деле, все числа должны быть равны нулю. Пусть S -- сумма всех чисел. Рассмотрим одну точку. Пусть ей соответствует число x=x(i), а через точку проведено k=k(i) прямых. По условию, k > 1. Сумма всех чисел по каждой из прямых, без учёта x, равна -x. Итого S=x-kx=x(1-k). Если S=0, отсюда следует x=0 для произвольной точки, и всё доказано. Допустим, что S > 0. Тогда за счёт неравенства 1-k < 0 оказывается, что x имеет противоположный знак: x < 0. И это верно для всех рассматриваемых точек, то есть все n чисел отрицательны, и их сумма положительной быть не может. Аналогично приводится к противоречию случай S < 0.

ссылка

отвечен 4 Окт '17 9:50

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×552

задан
4 Окт '17 6:36

показан
654 раза

обновлен
4 Окт '17 9:50

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru