?

Log in

решение задачки - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

решение задачки [май. 23, 2003|05:35 pm]
Anatoly Vorobey
Вот относительно простое решение ночной задачки.

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


Итак, у нас есть какое-то множество точек, таких, что расстояние между любыми двумя из них — целое число. Возьмём любые две точки из данного множества, 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 тоже может быть только конечное число; следовательно, наше множество не может быть бесконечным, что и требовалось доказать.
СсылкаОтветить

Comments:
[User Picture]From: urs
2003-05-23 09:36 am
>Множество точек P, удовлетворяющих данному
>условию — гипербола с осью AB
Это-то как раз понятно, это на лекциях по аналитической геометрии рассказывается
А вот выйти именно на конечное число гипербол, это надо было суметь.
Действительно красивая задачка
(Ответить) (Thread)
[User Picture]From: arbat
2003-05-23 11:26 am

1. Дано: множество точек, такое, что на любой прямой, проходящей через две точки множества лежит как минимум еще и третья точка из множества. Доказать: все точки лежат на одной прямой.

2. Кафельная квадратная плитка со стороной 1. Хозяин разрешает мастеру разрезать плитки только один раз и только вдоль стороны (если надо, конечно). Может ли мастер уложить плиткой прямоугольную комнату с нецелыми сторонами? (То, есть каждая плитка - прямоугольник 1хА, где 0<А<=1)




(Ответить) (Thread)
[User Picture]From: scolar
2003-05-23 11:50 am
Утверждение #1 - неверно, если множество не конечно - пример: множество всех точек плоскости с целыми координатами - любая прямая, проходящая через две точки этого множества содержит бесконечное число точек из этого множества.

Если отказаться и от счётности, то можно взять множество всех точек плоскости.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2003-05-23 12:58 pm

Re:

Там пропущена конечность множества, оно есть в условии. Я знаю эту задачу, она хорошая. Когда-то я её приводил у себя в журнале, где-то год назад.
(Ответить) (Parent) (Thread)
From: ex_p_k
2003-05-23 04:53 pm
1) Проще решать в дуальной формулировке - дано (конечное) множество прямых (можно требовать их непараллельности, выбрав центр для дуализации в общем положении), через точку пересечения любых двух проходит минимум еще одна. Пусть не все прямые пересекаются в одной точке. Возьмем самую близкую к прямой L точку P пересечения других прямых. Через P проходит минимум три прямые L1, L2 и L3, пересекающие L в трех точках. Выберем промежуточную точку (пусть это будет точка от пересечения с L2). Через нее проходит прямая L4, пересекающая либо L1 либо L3 в точке, лежащей ближе к L, чем P. Противоречие => все прямые проходят через одну точку. В изначальной формулировке - все точки лежат на одной прямой.

2) На торе R^2/Z^2 у плитки нет углов, а у нецелой комнаты есть.
(Ответить) (Parent) (Thread)
From: (Anonymous)
2004-04-25 08:30 pm
Наши плитки, что разрезанные, что целые, обладают следующей свойствой: положим плитку на шахматную доску с длиной стороны клетки 1/2, так, что плитка орентирована по сторонам доски. Тогда площадь накрытых плиткой черной и белой частей будет одинакова(напоминаю, одна из сторон у плитки -- единичная).Так вот, разобьем нашу команту на клетки, и положим плитки. Если положились -- значит, и в комнате площадь белого равна площади черного. Но легко видеть, что целость хотя бы одной стороны -- не только достаточное, но и необх. условие для равенства. Сталбыть -- не покроется комната с обеими нецелыми сторонами. Ура.
(Ответить) (Parent) (Thread)
From: (Anonymous)
2004-04-25 08:40 pm
Да, кстати, прошу прощения за занудство -- из решения видно, что ни ровно единичность, ни квадратность плиток ни зах не нужны. Просто -- куча прямоугольных плиток с хотя бы одной целой стороной. Теперь уже окончательное ура.
(Ответить) (Parent) (Thread)
[User Picture]From: arbat
2004-04-25 08:50 pm
Ну, что ура - то ура.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2004-04-26 03:40 am
Да, совершенно верно.
(Ответить) (Parent) (Thread)
From: ona_i_on
2003-05-23 02:18 pm
Да, действительно, про-о-о-о-стенькая такая задачка.

Прям как эта:
http://www.livejournal.com/users/ptizza/85798.html
(Ответить) (Thread)
From: (Anonymous)
2003-05-23 04:33 pm
грустно то как - это решение вчера нашел, но решил, что слишком сложное: доказательство, что гипербола (с уравнениями), и распределение гипербол, сходящихся асимптотически к прямым, звездой,
с направлением, заданным косинусом (для расстояния n: cos \alpha = j / n (j = 0 .. n - 1).

и, кстати, при j = 0 --не гипербола, а прямая,
перпендикуляр через середину отрезка между 2 точками.
(Ответить) (Thread)
[User Picture]From: kenigtiger
2003-05-24 01:04 pm

Все куда как элементарнее

По теореме косинусов в треугольнике ABC(три любые точки из этого множества)
bc^2=ab^2+ac^2-2ab*ac*cos(BAC)

Если все длины - целые чила, то и cos(BAC) должен быть целым числом, иначе, если он нескоратимая дробь, bc как корень из правой части тоже будет дробью. Так?
Следовательно - косинус у нас или -1, или 0, или 1. С учетом того, что угол треугольника - только один вариант - 0. Т.е. прямоугольный треугольник. Повторяем то же самое для всех трех вершин и получаем, что любой произвольный треугольник из всех, которые возможно построить на этих точках будет иметь три угла по 90 градусов. Что невозможно, значит, трегуольников нет, любые три точки на одной прямой.
ЧТД
(Ответить) (Thread)
From: (Anonymous)
2003-05-24 02:43 pm

Re: Все куда как элементарнее

ага! И равносторонние треугольники (с целочисленной стороной), и прямоугольный (3, 4, 5) и проч. в реальности не существуют! я всегда знал, что математика - не наука, а абстрактные утверждения, но чтоб она была настолько иллюзорной...
(Ответить) (Parent) (Thread)
[User Picture]From: vyastik
2003-05-25 10:37 pm

Re: Все куда как элементарнее

Если cos (BAC) = 1/2, Ваше утверждение теряет силу. Также оно неверно для случаев, когда знаменатель несократимой дроби является делителем ab или ac.
(Ответить) (Parent) (Thread)