Plane Euclidean geometry is good for mind training but research mathematicians rarely have to deal with it in their work. Here is such an occasion: the following problem has naturally appeared in my current work and will probably be included in a paper. It's not hard but I find it amusing.
Let T be a triangulation of a convex polygon P using non-crossing diagonals. So if P has n+3 sides for some n > 0, then T has n diagonals, and we identify T with this n-element set. Consider the following two ways of selecting some special subsets of T.
1. Crossing: take any diagonal d of P, and select the set of diagonals in T crossed by d (here "crossing" means having a common interior point).
2. Corralling: take any four distinct mid-points A,B,C,D of sides of P (say in a clockwise order), and select the set of diagonals in T having one end-point between B and C, and another between A and D.
Claim: these two ways of generating subsets of T are equivalent, that is, if a subset can be obtained by one of them, then it can also be obtained by another.
Solutions are welcome. If nobody finds my solution, I'll post it myself a little later.
2 comments:
1->2 берем множество диагоналей, пересекающих диагональ WE, идущую с запада на восток. Тогда на множестве пересекающих ее диагоналей можно определить понятие "восточнее", и это будет линйеный порядок. Берем самые западную и восточную диагонали AB и CD, пересекающие EW, соответственно (A,C на севере, B,D на юге). Тогда любая диагональ, пересекающая EW, имеет один конец между A и C, другой между B и D.
2->1 Рассмотрим множество всех диагоналей, кроме ABCD-corralling. Они разбивают многоугольник на несколько частей. Одна из частей имеет вершины как между A и B, так и между C и D. В самом деле, иначе любая часть имеет вершины только на (не более чем) двух их четырех возможных дуг, и часть, соседняя, например, с той, в которой есть вершины с дуг AB, BC, снова будет такой же. Но должен быть какой-то способ дойти от части одного типа до части другого типа, переходя в соседние.
Так вот возьмем эту часть, соответствующие вершины назовем U,V. Диагональ UV искомая.
Но почему Вы называете это евклидовой геометрией? Это же чистая комбинаторика.
Федя: спасибо за решение. Вы правы, конечно, это чистая комбинаторика, просто рисование треугольников (а у меня еще и "дополнительное построение" имеется) напомнило уроки школьной геометрии.
Мое решение немножко отличается в деталях и, мне кажется, несколько попроще (но это мелочи, конечно).
1 --> 2 For every diagonal d of P, take as A and B the mid-points of two sides of P that are incident to one end-point of d, and as C and D the mid-points of two sides incident to another end-point of d. Then a diagonal is crossed by d if and only if it is corralled by A,B,C,D.
2 --> 1 Let E (resp. F) be the endpoint of some diagonal corralled by A,B,C,D, such that E is between B and C (resp. between A and D) and is closest to B (resp. to A). Then the diagonal EF belongs to T, and there is a (unique) triangle EFG of T such that G is between A and B. Similarly, let E'F'G' be a triangle of T such that E'F' is a diagonal of T corralled by A,B,C,D and closest to the segment CD, and G' is between C and D. Clearly, a diagonal is corralled by A,B,C,D if and only if it is crossed by the diagonal GG'.
Post a Comment