Игры разума

[Poma][a]

Рассмотрим 2 точки начальную и конечную(точка 1 и точка n).
Проведем через них прямую.
На прямой будет лежать точку n-1 (что следует из условия)
Теперь возьмем и проведем прямую из точки 1 в точку n-1. Она будет совпадать с прямой, соединяющей 1 и n.
На прямой, соединяющей 1 и n-1 будет лежать еще одна точка (что следует из условия) эта точка будет n-2. Теперь проведем прямую через точку 1 и точку n-2, эта прямая будет совпадать с прямой, соединяющей 1 и n-1, а так же 1 и n-2.

И дальше методом "?".
Здесь как-то не очень подходит определение редукция (имхо).

P.S. Все пожелания принимаются к сведению, и будут использованы по мере возможностей.
P.P.S. Долго думал, начал вспоминать посты, и там TinMan сказал что задача вписывается в тему не давно обсуждаемую тему (разумеется фраза слегка изменена), что и натолкнула на такую идею.
P.P.P.S. В тех решениях видел не связность, но всё равно выставил их на суд, сейчас все кажется логичным и завершенным.

[TinMan]

Ром, извини, но твоя версия док-ва тоже не проходит.. Замечания - по ходу ответа.

Сообщение от Poma][a

Рассмотрим 2 точки начальную и конечную(точка 1 и точка n).

Что значит "конечная"? Как ты выбираешь эту точку? Упорядочиваешь в произвольном порядке (естественного порядка на плоскости, замечу, нет).

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

А почему именно предпоследняя точка? или это ты тоже просто так сортируешь их по ходу дела?

Теперь возьмем и проведем прямую из точки 1 в точку n-1. Она будет совпадать с прямой, соединяющей 1 и n.
На прямой, соединяющей 1 и n-1 будет лежать еще одна точка (что следует из условия) эта точка будет n-2.

Первые два были просто вопросы/замечания (не ошибки). А это - существенная ошибка, она пускает все доказательство под откос..
Да, на прямой (1,n-1) действительно должна быть точка (см. условие). Но на роль этой точки вполне годится точка n.
Остаток док-ва не цитирую, поскольку оно уже проколото..

P.P.S. Долго думал, начал вспоминать посты, и там TinMan сказал что задача вписывается в тему не давно обсуждаемую тему (разумеется фраза слегка изменена), что и натолкнула на такую идею.

Я уточню: я имел в виду задачу про "вазик", разговор о которой я пока считаю незаконченным. И добавлю.. Задача про N точек на плоскости действительно кажется очень простой на вид, но решение ее совсем непростое. Ромаха прав, тут есть своеобразный "подвох" )).

[Poma][a]

Я "отсортировал в таком виде" (см приложение). Тоесть с проецировал эти точки на ось x. Но точки могут быть расположены вертикально, в таком случае стоит рассматривать проекции на ось y.

Да, на прямой (1,n-1) действительно должна быть точка (см. условие). Но на роль этой точки вполне годится точка n.

Агась. Не подумал. А что если опять же рассматривать точки, у которых значение x (или если все точки можно соединить так, что получиться вертикальная прямая значение y) меньше значения х (или y) точки сначала n, потом n-1.

Забыл прикрепить

[Аватар]

Согласен на счет моего и т.д. – не корректно, для фиксированного n сойдет путем дальнейшего прибавления 1, пока до n не доберемся, а для любого нет. Тогда от противного. Построим прямые, соединяющие каждую точку с каждой. Из предположения, что точки не лежат на одной прямой подсчитаем расстояние от каждой из точек до прямых, на которых они не лежат. А дальше фокус с критичными значениями. Выберем точку D с минимальным расстоянием DF до такой прямой c точками A, B, C. Выбрать можно, поскольку к-во точек и прямых конечно. Возможные расклады расположения точек A, B, C относительно точки F: B и F совпадает, A и B по одну сторону или B и C по другую сторону от F на прямой. В раскладе приведенном на рисунке расстояние от B до прямой AD (BK) менше DF, что противоречит минимальности расстояния DF. Для других раскладов аналогично показать

[TinMan]

Сообщение от Аватар

... , что противоречит минимальности расстояния DF.

СУПЕР! Аватар, на этот раз - выстрел точно в цель! )
Если смогу, то +1

Для других раскладов аналогично показать

Достаточно сказать - выбираем те две точки, которые лежат по одну сторону от основания перпендикуляра: дальняя - А, а поближе - B.

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

Теперь пришло время открыть карты и сказать, почему я запостил эту задачу.. Дело в том, что я неоднократно видел такое, с позволения сказать, "решение":
1. для N=3 это верно (легко проверить);
2. предположим, что это верно для некоторого N=K;
3. берем N=K+1;
4. выбираем произвольную точку из множества и удаляем ее (на время) - приходим к случаю N=K, в котором все точки лежат на одной прямой А;
5. возвращаем убранную точку - разумеется, все на ту же прямую А, ибо иначе условия будут нарушены;
6. все точки коллинеарны, утверждение доказано по индукции.
Вопрос: где в этом решении ошибка? ))

Так вот - задача "про вазик", мне кажется, обладает аналогичным свойством (решение по индукции там не годится). Аватар, что скажешь? )

[Poma][a]

Вот наша плоскость. Переместим для простоты эту плоскость в 1 координатную четверть.
С проецируем точки на ось x.
[IMG][/IMG]

Теперь возьмем 1 точку (Как её найти? - Взять самую левую точку на оси x)
И n (последнюю точку) (Как её найти? - Взять самую правую точку на оси x)
Проведем через них прямую. На этой прямой будет лежать как минимум еще одна точка. Эта точка n-1.
[IMG][/IMG]



Дальше рассмотрим не прямую, а отрезок 1 n-1. Если на нем лежит какая-либо точка, то

Теперь соединим точку 1 и (уже)n-2, прямая соединяющая их будет лежать лежать отрезке 1 и n-1 => будет лежать на прямой соединяющей 1 и n

После этого повторим действие с отрезком уже 1 n-2 до тех пор пока не останется ни одной точки.

Если же там нет точки, то мы доказали.

[Аватар]

Poma][a, так и не понял что доказано. Отсутствие точек на отрезке не значит, что точек нет на прямой.

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

Специально нашел формальное определение индукции в математике. Действительно решение о вазике не вписывается в это определение. Но примененный там метод исключения точек считаю вполне корректным. Как его назвать - есть идеи?

[Poma][a]

Возможно назвать редукцией будет более-менее правильно.
А так ждем пока TinMan освободится, далее он нас всех просветит.


Мне кажется косяк идет в п.3 нужно доказывать или от 1 до n. Или от n до одного.

[DiemonStar]

точку D с минимальным расстоянием DF до такой прямой

В раскладе приведенном на рисунке расстояние от B до прямой AD (BK) менше DF, что противоречит минимальности расстояния DF.

Извините, но не вижу никакого противоречия в том, что расстояние от точки D до прямой AB больше расстояния от точки B до прямой AD.

[Poma][a]

Было время подумать. Всё-таки косяк в пукте 2. Нужно доказать это утверждение для n = k (база индукции). И дальше уже доказывать для n = k+1(переход индукции).