返回题库

HMMT 二月 2020 · 冲刺赛 · 第 25 题

HMMT February 2020 — Guts Round — Problem 25

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  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
解析

英文解析

  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