HMMT 十一月 2009 · 团队赛 · 第 8 题

HMMT November 2009 — Team Round — Problem 8

[ 6 ] In how many ways can the ball be launched so that it will return again to a vertex for the first time after 2009 bounces? Super Mario 64! Mario is once again on a quest to save Princess Peach. Mario enters Peach’s castle and finds himself in a room with 4 doors. This room is the first in a sequence of 2 indistinugishable rooms. In each room, 1 door leads to the next room in the sequence (or, for the second room, into Bowser’s level), while the other 3 doors lead to the first room.

解析

[ 6 ] In how many ways can the ball be launched so that it will return again to a vertex for the first time after 2009 bounces? Answer: 502 We will use the same idea as in the previous problem. We first note that every vertex ( ) √ 5 5 3 of a triangle can be written uniquely in the form a (5 , 0) + b , , where a and b are non-negative 2 2 ( ) √ 5 5 3 integers. Furthermore, if a ball ends at a (5 , 0) + b , , then it bounches off of a wall 2( a + b ) − 3 2 2 times. Therefore, the possible directions that you can launch the ball in correspond to solutions to 2( a + b ) − 3 = 2009, or a + b = 1006. However, if a and b have a common factor, say, k , then the ball will a b pass through the vertex corresponding to and before it passes through the vertex corresponding k k to a and b . Therefore, we must discount all such pairs a, b . This corresponds to when a is even or a = 503, so after removing these we are left with 502 remaining possible values of a , hence 502 possible directions in which to launch the ball. Super Mario 64! Mario is once again on a quest to save Princess Peach. Mario enters Peach’s castle and finds himself in a room with 4 doors. This room is the first in a sequence of 2 indistinugishable rooms. In each room, 1 door leads to the next room in the sequence (or, for the second room, into Bowser’s level), while the other 3 doors lead to the first room.