решение задачки
May. 23rd, 2003 05:35 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaВот относительно простое решение ночной задачки.
Будем доказывать нужное утверждение следующим образом: покажем, что если есть какой-то набор точек, отстоящих друг от друг на целые расстояния, и при этом не лежащих на одной прямой, то их количество конечно. Это эквивалентно нужному утверждению.
Итак, у нас есть какое-то множество точек, таких, что расстояние между любыми двумя из них — целое число. Возьмём любые две точки из данного множества, 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 тоже может быть только конечное число; следовательно, наше множество не может быть бесконечным, что и требовалось доказать.
Будем доказывать нужное утверждение следующим образом: покажем, что если есть какой-то набор точек, отстоящих друг от друг на целые расстояния, и при этом не лежащих на одной прямой, то их количество конечно. Это эквивалентно нужному утверждению.
Итак, у нас есть какое-то множество точек, таких, что расстояние между любыми двумя из них — целое число. Возьмём любые две точки из данного множества, 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 тоже может быть только конечное число; следовательно, наше множество не может быть бесконечным, что и требовалось доказать.
