HMMT 十一月 2013 · 冲刺赛 · 第 16 题
HMMT November 2013 — Guts Round — Problem 16
题目详情
- [ 10 ] A bug is on one exterior vertex of solid S , a 3 × 3 × 3 cube that has its center 1 × 1 × 1 cube removed, and wishes to travel to the opposite exterior vertex. Let O denote the outer surface of S (formed by the surface of the 3 × 3 × 3 cube). Let L ( S ) denote the length of the shortest path through S . (Note that such a path cannot pass through the missing center cube, which is empty space.) Let L ( S ) L ( O ) denote the length of the shortest path through O . What is the ratio ? L ( O ) 1
解析
- [ 10 ] A bug is on one exterior vertex of solid S , a 3 × 3 × 3 cube that has its center 1 × 1 × 1 cube removed, and wishes to travel to the opposite exterior vertex. Let O denote the outer surface of S (formed by the surface of the 3 × 3 × 3 cube). Let L ( S ) denote the length of the shortest path through S . (Note that such a path cannot pass through the missing center cube, which is empty space.) Let L ( S ) L ( O ) denote the length of the shortest path through O . What is the ratio ? L ( O ) √ √ √ √ 29 145 2 2 √ Answer: OR By (), the shortest route in O has length 2 1 . 5 + 3 = 3 5. By (**), 15 3 5 √ √ √ 2 2 2 2 2 2 the shortest route overall (in S ) has length 2 1 . 5 + 1 + 2 = 3 + 2 + 4 = 29. Therefore the √ √ 29 145 √ desired ratio is = . 15 3 5 () Suppose we’re trying to get from (0 , 0 , 0) to (3 , 3 , 3) through O . Then one minimal-length path through O is (0 , 0 , 0) → (1 . 5 , 0 , 3) → (3 , 3 , 3). () Suppose we’re trying to get from (0 , 0 , 0) to (3 , 3 , 3) through S . Then the inner hole is [1 , 2] × [1 , 2] × [1 , 2], and one minimal-length path is (0 , 0 , 0) → (1 . 5 , 1 , 2) → (3 , 3 , 3). To justify (*), note that we must at some point hit one of the three faces incident to (3 , 3 , 3), and therefore one of the edges of those faces. Without loss of generality, the first of these edges (which must lie on a face incident to (0 , 0 , 0)) is { ( t, 0 , 3) : 0 ≤ t ≤ 3 } . Then the shortest path goes directly from the origin to the edge, and then directly to (3 , 3 , 3); t = 1 . 5 minimizes the resulting distance. (One may either appeal to the classic geometric “unfolding” argument, or just direct algebraic minimization.) To justify (), consider the portion of S “visible” from (0 , 0 , 0). It sees 3 mutually adjacent faces of the center cube “hole” (when looking inside the solid) and its 6 edges. (3 , 3 , 3) can also see these 6 edges. The shortest path through S must be a straight line from the start vertex to some point P on the surface of the center cube (+), and it’s easy to see, using the triangle inequality, that this point P must be on one of the 6 edges. Without loss of generality, it’s on the edge { ( t, 1 , 2) : 1 ≤ t ≤ 2 } . The remaining path is a straight line to (3 , 3 , 3). Then once again, t = 1 . 5 minimizes the distance. (And once again, one may either appeal to the classic geometric “unfolding” argument—though this time it’s a little trickier—or just direct algebraic minimization.) Comment. (+) can be proven in many ways. The rough physical intuition is that “a fully stretched rubber band” with ends at (0 , 0 , 0) and (3 , 3 , 3) must not have any “wiggle room” (and so touches the inner cube). Perhaps more rigorously, we can try shortening a path that does not hit the center cube, for instance by “projecting the path down” towards the closest edge of the inner cube. 1