PUMaC 2020 · 加试 · 第 11 题
PUMaC 2020 — Power Round — Problem 11
题目详情
- There are two places where you may ask questions about the test. The first is Piazza. Please ask your coach for instructions to access our Piazza forum. On Piazza, you may ask any question so long as it does not give away any part of your solution to any problem . If you ask a question on Piazza, all other teams will be able to see it. If such a question reveals all or part of your solution to a power round question, your team’s power round score will be penalized severely. For any questions you have that might reveal part of your solution, or if you are not sure if your question is appropriate for Piazza, please email us at pumacpowerround2020@gmail.com. We will email coaches with important clarifications that are posted on Piazza. Introduction and Advice This year’s power round is about polyhedra . We will study various kinds of lines and segments on poolyhedra, combining their geometric and combinatorial properties. The questions will be motivated by extremal situations, such as making some paths as short as possible. The power round is structured such that it will walk you through proofs of some of the important theorems, by giving you hints and problems along the way. Here is some further advice with regard to the Power Round: • Read the text of every problem! Many important ideas are included in problems and may be referenced later on. In addition, some of the theorems you are asked to prove are useful or even necessary for later problems. • Make sure you understand the definitions . A lot of the definitions are not easy to grasp; don’t worry if it takes you a while to fully understand them. If you don’t, then you will not be able to do the problems. Feel free to ask clarifying questions about the definitions on Piazza (or email us). • Don’t make stuff up : on problems that ask for proofs, you will receive more points if you demonstrate legitimate and correct intuition than if you fabricate something that looks rigorous just for the sake of having “rigor.” • Check Piazza often! Clarifications will be posted there, and if you have a question it is possible that it has already been asked and answered in a Piazza thread (and if not, you can ask it, assuming it does not reveal any part of your solution to a question). If in doubt about whether a question is appropriate for Piazza, please email us at pumacpowerround2020@gmail.com. • Don’t cheat : as stated in Rules and Reminders, you may NOT use any references such as books or electronic resources. If you do cheat, you will be disqualified and banned from PUMaC, your school may be disqualified, and relevant external institu- tions may be notified of any misconduct. Good luck, and have fun! – Daniel Carter, Igor Medvedev, Aleksa Milojevic, Alan Yan We would like to acknowledge and thank many individuals and organizations for their support; without their help, this Power Round (and the entire competition) could not exist. Please refer to the solutions of the power round for full acknowledgments and references. Contents 1 Playing Billiard 6 2 Introduction to ant-paths 8 3 More about polyhedra 11 4 Ant-paths on tetrahedra 13 5 Ant-paths on cubes 15 Notation • ∀ : for all. Ex.: ∀ x ∈ { 1 , 2 , 3 } means “for all x in the set { 1 , 2 , 3 } ” • A ⊂ B : proper subset. Ex.: { 1 , 2 } ⊂ { 1 , 2 , 3 } , but { 1 , 2 } 6 ⊂ { 1 , 2 } • A ⊆ B : subset, possibly improper. ex.: { 1 } , { 1 , 2 } ⊆ { 1 , 2 } • f : x 7 → y : f maps x to y . Ex.: if f ( n ) = n − 3 then f : 20 7 → 17 and f : n 7 → n − 3 are both true. • { x ∈ S : C ( x ) } : the set of all x in the set S satisfying the condition C ( x ). Ex.: √ { n ∈ N : n ∈ N } is the set of perfect squares. • N : the natural numbers, { 1 , 2 , 3 , . . . } . • [ n ] = { 1 , 2 , 3 , ..., n } . • Z : the integers. • R : the real numbers. • | S | : the cardinality of set S . 1 Playing Billiard Alex loves playing billiard. Recently, he learned that the billiard balls bounce off the walls of the billiard table at the same angles they come in. Further, when a ball hits a corner of the table it may chose to bounce off any line between the two lines incident to that corner. Alex is a good geometer and has precisely defined this billiard game on an arbitrary convex polygon. Definition 1.A. A broken line A A . . . A is a union of line segments A A , A A , . . . A A . 1 2 n 1 2 2 3 n − 1 n We sat a broken line is closed if A = A and we call A , . . . , A the breakpoints of this 1 n 1 n broken line. Definition 1.B. Let P be a convex polygon. A broken line A A ...A is called a billiard 1 2 n trajectory on P if: • The points A lie on the boundary of P , for i = 1 , ..., n . i • If A lies in the interior of the edge XY of P , we have ∠ A A X = ∠ Y A A . i i − 1 i i i +1 • If A is a vertex of P , adjacent to the vertices X and Y of P , then i | ∠ XA A − ∠ A A Y | + ∠ XA Y ≤ 180 ° i i − 1 i +1 i i Now, Alex is interested what kinds of trajectories he can find on a polygon, and has one more definition. Definition 1.C. Let A A ...A be a billiard trajectory on a polygon P . If A = A and 1 2 n +1 1 n A = A , then A ...A is called a closed trajectory . For a closed trajectory C consisting 2 n +1 1 n of n line segments, we define its order as | C | = n . Clearly, if there is at least one closed trajectory C on a polygon P , there is infinitely many of them, obtained by walking several times over C . Trajectories obtained by repeating several times the same basic closed trajectory C are called powers of C . Trajectories that cannot be obtained as powers are called prime . Theorem 1.I. For any convex polygon P there exist infinitely many prime closed billiard trajectories on P . We will prove this theorem in several steps. The main idea is to take a longest closed broken line L with vertices on the boundary of P and at most n vertices, for some wisely 1 chosen n . The following three problems will show that this line satisfies the conditions of the theorem 1.I.
解析
- There are two places where you may ask questions about the test. The first is Piazza. Please ask your coach for instructions to access our Piazza forum. On Piazza, you may ask any question so long as it does not give away any part of your solution to any problem . If you ask a question on Piazza, all other teams will be able to see it. If such a question reveals all or part of your solution to a power round question, your team’s power round score will be penalized severely. For any questions you have that might reveal part of your solution, or if you are not sure if your question is appropriate for Piazza, please email us at pumac@math.princeton.edu. We will email coaches with important clarifications that are posted on Piazza. Introduction and Advice This year’s power round is about extremal combinatorics , and more specifically extremal combinatorics in Graph Theory. extremal combinatorics studies the maximum and/or minimum possible cardinalities of combinatorial structures with some desired prop- erties. It has applications in theoretical computer science, information theory, number theory, geometry and others. For example, a standard question in extremal combinatorics is of the form If we look at structures with specific properties, how big or small can they be? We will answer this question for a few examples with graphs. The power round is structured such that it will walk you through proofs of some of the most important theorems. Afterwards there will be some auxiliary problems. Here is some further advice with regard to the Power Round: • Read the text of every problem! Many important ideas are included in problems and may be referenced later on. In addition, some of the theorems you are asked to prove are useful or even necessary for later problems. • Make sure you understand the definitions . A lot of the definitions are not easy to grasp; don’t worry if it takes you a while to fully understand them. If you don’t, then you will not be able to do the problems. Feel free to ask clarifying questions about the definitions on Piazza (or email us). • Don’t make stuff up : on problems that ask for proofs, you will receive more points if you demonstrate legitimate and correct intuition than if you fabricate something that looks rigorous just for the sake of having “rigor.” • Check Piazza often! Clarifications will be posted there, and if you have a question it is possible that it has already been asked and answered in a Piazza thread (and if not, you can ask it, assuming it does not reveal any part of your solution to a question). If in doubt about whether a question is appropriate for Piazza, please email us at pumac@math.princeton.edu. • Don’t cheat : as stated in Rules and Reminders, you may NOT use any references such as books or electronic resources. If you do cheat, you will be disqualified and banned from PUMaC, your school may be disqualified, and relevant external institu- tions may be notified of any misconduct. Good luck, and have fun! – Marko Medvedev I would like to acknowledge and thank many individuals and organizations for their support; without their help, this Power Round (and the entire competition) could not exist. Please refer to the solutions of the power round for full acknowledgments and references. Contents 1 Playing Billiard 6 2 Introduction to ant-paths 9 3 More about polyhedra 13 4 Ant-paths on tetrahedra 17 5 Ant-paths on cubes 20 6 Connection to billiard trajectories 25 Notation • ∀ : for all. ex.: ∀ x ∈ { 1 , 2 , 3 } means “for all x in the set { 1 , 2 , 3 } ” • A ⊂ B : proper subset. ex.: { 1 , 2 } ⊂ { 1 , 2 , 3 } , but { 1 , 2 } 6 ⊂ { 1 , 2 } • A ⊆ B : subset, possibly improper. ex.: { 1 } , { 1 , 2 } ⊆ { 1 , 2 } • f : x 7 → y : f maps x to y . ex.: if f ( n ) = n − 3 then f : 20 7 → 17 and f : n 7 → n − 3 are both true. • { x ∈ S : C ( x ) } : the set of all x in the set S satisfying the condition C ( x ). ex.: √ { n ∈ N : n ∈ N } is the set of perfect squares. • N : the natural numbers, { 1 , 2 , 3 , . . . } . • [ n ] = { 1 , 2 , 3 , ..., n } . • Z : the integers. • R : the real numbers. • | S | : the cardinality of set S . 1 Playing Billiard Alex loves playing billiard. Recently, he learned that the billiard balls bounce off the walls of the billiard table at the same angles they come in. Further, when a ball hits a corner of the table it may chose to bounce off any line between the two lines incident to that corner. Alex is a good geometer and has precisely defined this billiard game on an arbitrary convex polygon. Definition 1.A. A broken line A A . . . A is a union of line segments A A , A A , . . . A A . 1 2 n 1 2 2 3 n − 1 n We sat a broken line is closed if A = A and we call A , . . . , A the breakpoints of this 1 n 1 n broken line. Definition 1.B. Let P be a convex polygon. A broken line A A ...A is called a billiard 1 2 n trajectory on P if: • The points A lie on the boundary of P , for i = 1 , ..., n . i • If A lies in the interior of the edge XY of P , we have ∠ A A X = ∠ Y A A . i i − 1 i i i +1 • If A is a vertex of P , adjacent to the vertices X and Y of P , then i | ∠ XA A − ∠ A A Y | + ∠ XA Y ≤ 180 ° i i − 1 i +1 i i Now, Alex is interested what kinds of trajectories he can find on a polygon, and has one more definition. Definition 1.C. Let A A ...A be a billiard trajectory on a polygon P . If A = A and 1 2 n +1 1 n A = A , then A ...A is called a closed trajectory . For a closed trajectory C consisting 2 n +1 1 n of n line segments, we define its order as | C | = n . Clearly, if there is at least one closed trajectory C on a polygon P , there is infinitely many of them, obtained by walking several times over C . Trajectories obtained by repeating several times the same basic closed trajectory C are called powers of C . Trajectories that cannot be obtained as powers are called prime . Theorem 1.I. For any convex polygon P there exist infinitely many prime closed billiard trajectories on P . We will prove this theorem in several steps. The main idea is to take a longest closed broken line L with vertices on the boundary of P and at most n vertices, for some wisely 1 chosen n . The following three problems will show that this line satisfies the conditions of the theorem 1.I.