PUMaC 2020 · 加试 · 第 1 题
PUMaC 2020 — Power Round — Problem 1
题目详情
Problem 1.4. Prove that, given any two points A, B on the boundary of a convex polygon P , there exists infinitely many billiard trajectories starting at A and ending at B . 2 Introduction to ant-paths Alan the Ant lives on the surface of a three-dimensional polyhedron P . His life consists of moving along this surface, in a specific manner. Every day, Alan chooses two points X and Y on that surface, positions himself at X and tries to get as fast as possible to Y . To do that, he needs to find a shortest path between X and Y on the surface of P . To formalize these concepts, we have the following definitions. Although these definition may seem cumbersome at first, they are only rephrasing the intuition we have about poly- hedra and their surfaces in mathematical terms. The first definition gives us the concept of the polyhedron: Definition 2.A. A half-space is a region on one side of the plane. Half-spaces can be closed or open , depending on whether they contain the bounding plane or not. A set of points 3 in R is said to be bounded if there is a big enough ball containing it. A polyhedron is a bounded intersection of several closed half-spaces. The following definition will formalize the concept of the surface of that polyhedron. Definition 2.B. Let P be a polyhedron and let H be a plane which does not intersect the interior of P . If the intersection of H and P is a point, that point is called a vertex of P . If H ∩ P is a line segment, that line segment is called an edge of P , while if H ∩ P is a plane polygon, it is called a face of P . The set of vertices of P is denoted by V ( P ). The surface of P is the union of all its faces. We denote the surface of P by S ( P ). Finally, the last definition explains what a path on the surface is and how we measure its length. Definition 2.C. Let X and Y be two points on the surface of a polyhedron P . A path between X and Y on the surface S ( P ) is a continuous curve C ⊂ S ( P ), having one end in X and the other end in Y . For any such curve C , we can pick several points along it, say X = T , T , T , ..., T = Y in that order along C , such that the segments of C 0 1 2 k between T and T lie on only one face. Then, as the segments T and T , we can i i +1 i i +1 measure their length and denote it by l ( T T ). Now, we can define the length of C as i i +1 l ( C ) = l ( T T ) + l ( T T ) + · · · + l ( T T ). A shortest path between X and Y is the path 0 1 1 2 k − 1 k between X and Y with the minimum length. It turns out that shortest paths on a surface of a polyhedron are exceedingly interesting, as the following properties show:
解析
Problem 1.2. Prove that L is indeed a closed billiard trajectory, in the sense of defini- tions 1.B and 1.C. Proof 1.2. In order to show L is a closed billiard trajectory, it will be enough to check that the latter two conditions of the definition 1.B are satisfied, as all other conditions directly follow from the definition of L . This proof will have two parts: first, we will show that all breakpoints of L are vertices of P , and then we will prove the property three of the definition 1.B for these points. These two parts are very similar in nature, but we present two different arguments. Note that both of these arguments can essentially be used to prove both parts. We use both approaches as to show several possible options students could take. First, we will show that all the breakpoints of L are actually the vertices of P . To see this, we will take an arbitrary breakpoint A and look at the segments A A and i i − 1 i A A . As the length of L is maximal, we see that A is a point of P which maximizes i i +1 i A A + A A , for given A , A . We claim that it is impossible that such A is in the i − 1 i i i +1 i − 1 i +1 i interior of some edge of P . If A was in the interior of the edge XY , we would consider the i set of all the points T with A T + T A = A A + A A , which is an ellipse containing i − 1 i +1 i − 1 i i i +1 A . As XY is a segment through A and as the ellipse is convex, at least one of X, Y must i i lie outside of the ellipse. Say this point is X . Then, A X + XA > A A + A A , i − 1 i +1 i − 1 i i i +1 contradicting the fact A A + A A was maximal. Thus, A must be a vertex of the i − 1 i i i +1 i polygon. Now, we will prove the property three of the definition 1.B. Let A be a breakpoint, i which is a vertex of P and let X, Y be the adjacent vertices. Assume, without loss of generality, that ∠ XA A ≤ XA A . Moreover, for the sake of contradiction, assume i i − 1 i i +1 that | ∠ XA A − ∠ A A Y | > 180 ° − ∠ XA Y . Again, because of symmetry, we may i i − 1 i +1 i i assume ∠ XA A > ∠ A A Y and so we have: i i − 1 i +1 i ∠ XA A − ∠ A A Y > 180 ° − ∠ XA Y i i − 1 i +1 i i Let s be the external angle bisector of ∠ A A A , and let B be the reflection of A i − 1 i i +1 i +1 over s . First, we show that points A , A lie on the same side of s , and that the line s i − 1 i +1 separates them from X . The first part is clear by definition of s , and for the second part, we need to prove that ∠ XA A > ∠ ( s, A A ). Further, we compute the angles to get i i − 1 i i +1 ( ) 1 1 ∠ ( s, A A ) = 90 ° − ∠ A A A = 90 ° − ∠ XA Y − ∠ XA A − ∠ A A Y i i +1 i − 1 i i +1 i i i − 1 i +1 i 2 2 Thus, the previous inequality transforms into: ∠ XA A > ∠ ( s, A A ) ⇐⇒ i i − 1 i i +1 ( ) 1 ∠ XA A > 90 ° − ∠ XA Y − ∠ XA A − ∠ A A Y ⇐⇒ i i − 1 i i i − 1 i +1 i 2 ( ) 1 1 ∠ XA A − ∠ A A Y > 90 ° − ∠ XA Y, i i − 1 i +1 i i 2 2 where the last line follow by assumption we made. Now, we will show a final contradiction by showing that A X + XA > A A + i − 1 i +1 i − 1 i A A . To show this, note that A A + A A = A A + A B = A B , because i i +1 i − 1 i i i +1 i − 1 i i i − 1 A , A and B are collinear. Moreover, as s is the perpendicular bisector of A B , we see i − 1 i i +1 that A X > BX , because X and B are on the same side of s . Thus, we can claim the i +1 following chain of inequalities: A A + A A = A B < A X + XB < A X + XA . i − 1 i i i +1 i − 1 i − 1 i − 1 i +1 This shows that A does not maximize the sum A A + A A , which gives an ultimate i i − 1 i i i +1 contradiction and means | ∠ XA A − ∠ A A Y | ≤ 180 ° − ∠ XA Y . i i − 1 i +1 i i