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
and P = (0 , 0 , 0 , 0). (Here P = P .) Find the largest integer n such that 2 divides N .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
and P = (0 , 0 , 0 , 0). (Here P = P .) Find the largest integer n such that 2 divides N .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 othersimilar points), we have to go to (0 , 0 , 0 , 0) or ( − 1 , 1 , 1 , 1) and its cyclic shifts. If a is the numberof ways to go from (1 , 1 , 1 , 1) to point of the form ( ± 1 , ± 1 , ± 1 , ± 1) in i steps, then we need to findiν (16 a ). To find a recurrence relation for a , note that to get to some point in ( ± 1 , ± 1 , ± 1 , ± 1), we
2 2018 imust either come from a previous point of the form ( ± 1 , ± 1 , ± 1 , ± 1) or the point (0 , 0 , 0 , 0). In orderto 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 . Solvingi 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