返回题库

HMMT 十一月 2019 · 团队赛 · 第 7 题

HMMT November 2019 — Team Round — Problem 7

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

题目详情

英文原题

  1. [55] Consider sequences a of the form a = ( a , a , . . . , a ) such that each term a is either 0 or 1. For
    1 2 20 ieach such sequence a , we can produce a sequence b = ( b , b , . . . , b ) , where
    1 2 20


    a + a i = 1
    i i +1

    b =
    a + a + a 1 < i < 20
    i − 1 i i +1 i


    a + a i = 20 .
    i − 1 i
    How many sequences b are there that can be produced by more than one distinct sequence a ?
    − →
解析

英文解析

  1. [55] Consider sequences a of the form a = ( a , a , . . . , a ) such that each term a is either 0 or 1. For
    1 2 20 ieach such sequence a , we can produce a sequence b = ( b , b , . . . , b ) , where
    1 2 20


    a + a i = 1
    i i +1

    b =
    a + a + a 1 < i < 20
    i − 1 i i +1 i


    a + a i = 20 .
    i − 1 i
    How many sequences b are there that can be produced by more than one distinct sequence a ?2
    Proposed by: Benjamin Qi
    Answer: 64
    ˆ ˆ ˆ ˆ
    Let the two sequences be b and b . Then, observe that given a , if b = b and b = b , then b = b (since a
    1 1 2 2
    ˆ ˆwill uniquely determine the remaining elements in b and b ). Thus, b and b must start with (1 , 0 , . . . ) and
    (0 , 1 , . . . ), respectively (without loss of generality).
    ˆ ˆ
    Note that a is either 1 (in which case b = b = 0) or 2 (in which case b = b = 1). Moreover, b , b
    3 3 3 3 3 4 5
    must be the same as b , b (and the same for b ) for the sequences to generate the same a , a . We canˆ
    1 2 3 4
    then pick a , a , . . . .
    6 9
    Observe, that the last elements also have to be ( . . . , 1 , 0) for b and ( . . . , 0 , 1) for b . Thus, the answer isˆknonzero only for sequence lengths of 2 (mod 3), in which case, our answer is 2 , where the length is 3 k + 2
    (since we have two choices for every third element).
    Here, since N = 20 = 3(6) + 2, the answer is 2 = 64.6 − →