задачка

[avva]

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

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

Comments

[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 - целые} (что слабее, чем условие задачи), то невозможно построить бесконечное множество точек, не лежащих на одной прямой, с целыми расстояниями.