HMMT 二月 2020 · 冲刺赛 · 第 25 题
HMMT February 2020 — Guts Round — Problem 25
题目详情
- [15] Let S be the set of 3 points in four-dimensional space where each coordinate is in {− 1 , 0 , 1 } . Let N be the number of sequences of points P , P , . . . , P in S such that P P = 2 for all 1 ≤ i ≤ 2020 1 2 2020 i i +1 n and P = (0 , 0 , 0 , 0). (Here P = P .) Find the largest integer n such that 2 divides N . 1 2021 1
解析
- [15] Let S be the set of 3 points in four-dimensional space where each coordinate is in {− 1 , 0 , 1 } . Let N be the number of sequences of points P , P , . . . , P in S such that P P = 2 for all 1 ≤ i ≤ 2020 1 2 2020 i i +1 n and P = (0 , 0 , 0 , 0). (Here P = P .) Find the largest integer n such that 2 divides N . 1 2021 1 Proposed by: James Lin Answer: 4041 Solution: From (0 , 0 , 0 , 0) we have to go to ( ± 1 , ± 1 , ± 1 , ± 1), and from (1 , 1 , 1 , 1) (or any of the other similar points), we have to go to (0 , 0 , 0 , 0) or ( − 1 , 1 , 1 , 1) and its cyclic shifts. If a is the number i of ways to go from (1 , 1 , 1 , 1) to point of the form ( ± 1 , ± 1 , ± 1 , ± 1) in i steps, then we need to find ν (16 a ). To find a recurrence relation for a , note that to get to some point in ( ± 1 , ± 1 , ± 1 , ± 1), we 2 2018 i must either come from a previous point of the form ( ± 1 , ± 1 , ± 1 , ± 1) or the point (0 , 0 , 0 , 0). In order to go to one point of the form ( ± 1 , ± 1 , ± 1 , ± 1) through (0 , 0 , 0 , 0) from the point ( ± 1 , ± 1 , ± 1 , ± 1), we have one way of going to the origin and 16 ways to pick which point we go to after the origin. Additionally, if the previous point we visit is another point of the form ( ± 1 , ± 1 , ± 1 , ± 1) then we have 4 possible directions to go in. Therefore the recurrence relation for a is a = 4 a + 16 a . Solving i i i − 1 i − 2 the linear recurrence yields √ √ 1 1 i i i √ √ a = (2 + 2 5) − (2 − 2 5) = 4 F , i i +1 5 5 so it suffices to find ν ( F ). We have F ≡ 0 , 1 , 1 , 2 , 3 , 1 (mod 4) for n ≡ 0 , 1 , 2 , 3 , 4 , 5 (mod 6), so 2 2019 n ν ( F ) = 1, and the answer is 4 + 2 · 2018 + 1 = 4041. 2 2019