решение задачки
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 тоже может быть только конечное число; следовательно, наше множество не может быть бесконечным, что и требовалось доказать.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2003-05-23 09:36 am (UTC)>условию — гипербола с осью AB
Это-то как раз понятно, это на лекциях по аналитической геометрии рассказывается
А вот выйти именно на конечное число гипербол, это надо было суметь.
Действительно красивая задачка
no subject
Date: 2003-05-23 11:26 am (UTC)1. Дано: множество точек, такое, что на любой прямой, проходящей через две точки множества лежит как минимум еще и третья точка из множества. Доказать: все точки лежат на одной прямой.
2. Кафельная квадратная плитка со стороной 1. Хозяин разрешает мастеру разрезать плитки только один раз и только вдоль стороны (если надо, конечно). Может ли мастер уложить плиткой прямоугольную комнату с нецелыми сторонами? (То, есть каждая плитка - прямоугольник 1хА, где 0<А<=1)
no subject
Date: 2003-05-23 11:50 am (UTC)Если отказаться и от счётности, то можно взять множество всех точек плоскости.
Re:
Date: 2003-05-23 12:58 pm (UTC)no subject
Date: 2003-05-23 04:53 pm (UTC)2) На торе R^2/Z^2 у плитки нет углов, а у нецелой комнаты есть.
no subject
Date: 2004-04-25 08:30 pm (UTC)no subject
Date: 2004-04-25 08:40 pm (UTC)no subject
Date: 2004-04-25 08:50 pm (UTC)no subject
Date: 2004-04-26 03:40 am (UTC)no subject
Date: 2003-05-23 02:18 pm (UTC)Прям как эта:
http://www.livejournal.com/users/ptizza/85798.html
no subject
Date: 2003-05-23 04:33 pm (UTC)с направлением, заданным косинусом (для расстояния n: cos \alpha = j / n (j = 0 .. n - 1).
и, кстати, при j = 0 --не гипербола, а прямая,
перпендикуляр через середину отрезка между 2 точками.
Все куда как элементарнее
Date: 2003-05-24 01:04 pm (UTC)bc^2=ab^2+ac^2-2ab*ac*cos(BAC)
Если все длины - целые чила, то и cos(BAC) должен быть целым числом, иначе, если он нескоратимая дробь, bc как корень из правой части тоже будет дробью. Так?
Следовательно - косинус у нас или -1, или 0, или 1. С учетом того, что угол треугольника - только один вариант - 0. Т.е. прямоугольный треугольник. Повторяем то же самое для всех трех вершин и получаем, что любой произвольный треугольник из всех, которые возможно построить на этих точках будет иметь три угла по 90 градусов. Что невозможно, значит, трегуольников нет, любые три точки на одной прямой.
ЧТД
Re: Все куда как элементарнее
Date: 2003-05-24 02:43 pm (UTC)Re: Все куда как элементарнее
Date: 2003-05-25 10:37 pm (UTC)