задачка

[avva]

Несложная, но красивая. Комменты скрывать не буду, так что там могут появиться вскорости правильные решения — те, кто хотят сами подумать, учтите это.

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

Comments

[lezze.livejournal.com]

а можно предположить, что расстояние измеряется в бесконечно малых единицах? :)

[ona-i-on.livejournal.com]

Линейная функция?

[zhenyach.livejournal.com]

...различных точек

[bugabuga.livejournal.com]

Возьмём в этом множестве 3 любые несовпадающие точки, приняв расстояние между двумя из них за единицу , и построим треугольник. Для того, чтобы расстояние от третьей точки до первой было целым, косинус угла должен быть целым числом. До второй -- синус должен быть целым числом. Следовательно все углы в этом треугольнике будут кратны 90 градусам :) Поскольку сумма углов треугольника должна быть 180 градусов, мы должны выбрать углы в 0 и 180 градусов. Прямая линия :)

п.с. смухлевал? :)

[angerona.livejournal.com]

Я тоже думaлa про треугольники, но что-то в вaшем обьяснении не тaк. А кaк нaсчет прямоугольного треугольникa со сторонaми: 4, 3, 5?

Тут скорее что-то про множество состоящее из чисел a, b, c, где a^2 + b^2 = c^2 и a, b, c -- integers.

[amigofriend.livejournal.com]

Смухлевали, потому что треугольник может быть равносторонним. Надо рассмотреть отдельно.

Но вообще, конечно - через треугольник - правильно :)

[bugabuga.livejournal.com]

_Расстояние между двумя из них принимаем за единицу_
:)

[angerona.livejournal.com]

da, ya videla, no togda kakoe otnoshenie eto imeet k zadache? To est' snachala dokazhite, chto eto "rasstoyanie berem za edinicu" pokazyvaet chto-to.

[alexmoskalyuk.livejournal.com]

Предположим, что все точки находятся на прямой, и лишь одна из них – вне прямой. Тогда перпендикуляр от этой точки к прямой является целым числом, согласно условию задачи. Расстояние от этой точки до любой другой точки на прямой также является целым числом. Таким образом всегда имеем прямоугольный треугольник с катетом и гипотенузой, представленными целым числом. Длина второго катета тогда составляет sqrt (h^2 – k^2), что составит целое число лишь в исключительных случаях. Т.е. число точек тогда может быть только конечным. От противного делаем вывод, что все точки расположены на единой прямой, так как тогда длина перпендикуляра равна 0, а h == k.

[plus25c.livejournal.com]

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

А вдруг точка в основании перпендикуляра не принадлежит множеству целых чисел?

[plus25c.livejournal.com]

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

[alexmoskalyuk.livejournal.com]

Да, верно подмечено, выбирать месторасположение точек и создавать новые нам не дано.

Треугольники

[bouh.livejournal.com]

где a^2 + b^2 = c^2 - это только прямоугольные треугольники. Если брать любой треугольник, то для каждой стороны треугольника должно выполняться условие, что ее длина не больше суммы двух других.
В качестве примера возьмите стороны 2, 3, 4. :)

[mudak.livejournal.com]

ОК. (Это я like, "ну-с, приступим".)
Допустим, точки не лежат на одной плоскости.
Тогда, во множестве точек выберем треугольник (ABC).
Нетрудно показать, что раз расстояния между точками должны быть целыми (т.е. >= 1), а число точек бесконечно, то для любого заданного расстояния существует бесконечное множество точек, находящихся на большем расстоянии от (любой точки) выбранного нами треугольника.
Возьмем произвольную точку вне треугольника (O). Между как минимум одной (точнее двумя) парой векторов OA, OB, OC - ненулевой угол. При этом OA, OB, OC имеют целую длину (как и AB, AC, BC).
Назовем направлением произвольную прямую с проекциями точек (относя параллельные прямые к одному и тому же направлению). Существует конечное число направлений, для которых самая длинная проекция ребра выбранного треугольника является целым числом (p' <= p). При этом, пусть p = AB (p' = A'B'), тогда C' (проекция точки C) принадлежит отрезку A'B'.
Рассмотрим некоторое направление. Для него ищем все точки множества, для которых |OA - OB| = p', т.е. если OA = n, то OB = n +/- p' (т.е. может быть не более двух точек для заданных n и p'). Но при этом и OC также должно быть целым.
Дальше получается два варианта:
если A'C' - целое и если A'C' нецелое.
Во втором случае, т.к. OC -> OA + A'C' при n->inf, то мы можем взять некоторое заведомо большое, но конечное N, при котором если OA>N, то OC не будет целым. Т.к. других точек, отвечающих условию задачи, нет, то по данному направлению мы не можем построить бесконечное множество точек.
Если же A'С' целое, то, грубо говоря, т.к. точки не лежат на одной прямой, то в общем случае OC != OA + A'C', хотя и сколь угодно близко при достаточно большом n, т.е. также не может быть целым.
Окончательно, т.к. существует конечное число направлений, по каждому из которых можно найти не более чем конечное число точек, отвечающих условию: {OA, OB, OC - целые} (что слабее, чем условие задачи), то невозможно построить бесконечное множество точек, не лежащих на одной прямой, с целыми расстояниями.

[bugabuga.livejournal.com]

Если с единицей то случаи вышеописанного треугольника не пройдут -- расстояния между вершинами должны быть кратные :)

[p-k.livejournal.com]

Возьмем четыре точки - A, B, C, D. Условие, что для пятой точки E верно, что |EA|-|EB| \in Z и |EC|-|ED| \in Z есть пересечение двух квадрик. Если таких пересечений больше 4, то это не общее положение => квадрики совпадают. Так как A, B и C, D являются фокальными точками, и все разные, то квадрики должны быть вырожденными, то есть быть парой совпадающих прямых, на которых лежат A, B, C, D. Поскольку точки были выбраны произвольно, то любые 4 точки лежат на одной прямой => все лежат на одной прямой.

А вот такой вариант задачи - сколько точек можно расположить на плоскости так, чтобы никакие три не лежали на одной прямой и расстояния между любыми двумя были бы целыми?

Навеяло...

[tigi.livejournal.com]

воспоминание о фразе некоего академика -

Через любые три точки можно провести прямую достаточной ширины.

[mudak.livejournal.com]

Я, честно говоря, ничего не понял, но если решение правильное, т.е. пятую точку уже не поставишь согласно условию, то ваша-то задача тривиальна:
4; например, прямоугольник 4х3.

[p-k.livejournal.com]

Пятую точку можно поставить - прямоугольник 8x6 с точкой в центре...

[mudak.livejournal.com]

Хм, ну, во-первых, тут есть три точки на одной прямой,
а во-вторых, тогда я совсем ничего не понял.

[p-k.livejournal.com]

Ага, есть. Но можно и без того:
(576, 168)
(225, 300)
(0,0)
(225, -300)
(576, -168)
:)

про во-вторых

[mudak.livejournal.com]

Тогда я не понял, что же было доказано сперва? :(
Если то, что к четырем точкам не на одной прямой с целочисленными расстояниями нельзя поставить пятую на целом же расстоянии от каждой, то здесь мы видим опровержение.

Re: про во-вторых

[p-k.livejournal.com]

Доказано, что если можно, то конечное количество. Да, про квадрики (или коники) - их не две, а два конечных семейства.

[avva.livejournal.com]

Ого! ;-)

[avva.livejournal.com]

Да, естественно.

[avva.livejournal.com]

нет ;)

[urs.livejournal.com]

Имхо, avva лукавит, по поводу того, что задачка не сложная.
Если ослабить условие и допустить существование двух точек в этом множестве с расстоянием 1 друг от друга, то задачку можно было бы раскрутить, а так даже не видно с какого конца браться

[urs.livejournal.com]

1. Даже если Вы докажите что утверждение “все точки находятся на прямой, и лишь одна из них – вне прямой” противоречиво, то это еще будет далеко не решение. Вполне возможна ситуация, когда вообще не существует ни одной прямой, на которой было бы бесконечное число точек. Это самый сложный момент задачи
2. “Тогда перпендикуляр от этой точки к прямой является целым числом, согласно условию задачи” такого не говорилось, но это интересный частный случай.
3. “что составит целое число лишь в исключительных случаях” – это еще доказать надо, хотя доказать несложно, конечно

[urs.livejournal.com]

Доказать для случая, когда перпендикуляр не целове число, тоже несложно.
Пусть a - длина перпендикуляра (не обязательно целое число).
Пусть b - расстояние по прямой от основания перпендикуляра до ближайшей точки множества, назовем ее В (без ограничения общности идем от основания по прямой влево). Докажем, что слева от основания перпендикуляра на прямой конечное число точек. Если точек было бы бесконечно, то для любого n существовало бы m, такое, что (n+m)^2 + (n+b)^2 = a^2, что равносильно:
2n(m-b) + m^2 = a^2 + b^2. При достаточно больших n условие выполняется только если m=b, a=0, т.е. точка на прямой. Противоречие.
Осталось доказать, что существует прямая, на которой было бы бесконечное число точек данного множества. Как это доказывать я не знаю, вообще, мне кажется данный пусть решения "через прямую" тупиковый