Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Category:

решение задачки

Вот относительно простое решение ночной задачки.

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


Итак, у нас есть какое-то множество точек, таких, что расстояние между любыми двумя из них — целое число. Возьмём любые две точки из данного множества, A и B. Теперь возьмём ещё одну произвольную точку P из данного множества. |AB|, напомню, обозначает расстояние от A до B.

Согласно неравенству треугольника, |BP| <= |AB| + |AP| (длина BP, стороны треугольника ABP, меньше или равна сумме длин двух других сторон — равенство будет в случае, если P совпадает с A или B или лежит с ними на одной прямой). Отсюда |BP| - |AP| <= |AB|. Если BP длиннее AP, то это условие ограничивает величину разницы; но если BP короче AP, то разница меньше нуля и условие выполняется тривиальным образом. Однако для этого случая мы можем написать то же неравенство треугольника для другой стороны: |AP| <= |AB| + |BP|, и, следовательно, |AP| - |BP| <= |AB|.

Отсюда вывод: абсолютное значение разницы длин AP и BP (т.е. разница по модулю) меньше или равна фиксированному числу |AB|. Но при этом эта разница длин сама должна быть целым числом, поэтому для неё есть только конечное количество возможностей. Предположим, например, что |AB| = 5. Тогда разница |AP| - |BP| может быть следующей: -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5.

Для каждого конкретного возможного значения разницы, назовём его K, у нас есть уравнение для всех P в нашем множестве: |AP| - |BP| = K. Множество точек P, удовлетворяющих данному условию — гипербола с осью AB (если это неясно, нарисуйте картинку, решите уравнение или подглядите здесь). Таким образом, все точки P нашего множества обязаны лежать на одной из конечного числа гипербол, каждая из которых построена на оси AB.

Возьмём теперь точку C нашего множества, не лежащую на AB (согласно условию такая точка есть). Повторим предыдущие рассуждения и заключим, что все точки P нашего множества обязаны лежать на одной из конечного числа гипербол, каждая из которых построена на оси AC. Но две гиперболы, построенные на не-параллельных осях AB и AC, могут пересекаться только в конечном числе точек. Поэтому "подходящих" точек P тоже может быть только конечное число; следовательно, наше множество не может быть бесконечным, что и требовалось доказать.
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 14 comments