返回题库

HMMT 二月 2018 · ALGNT 赛 · 第 8 题

HMMT February 2018 — ALGNT Round — Problem 8

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

题目详情

英文原题

  1. For how many pairs of sequences of nonnegative integers ( b , b , . . . , b ) and ( c , c , . . . , c ) does
    1 2 2018 1 2 2018
    there exist a sequence of nonnegative integers ( a , . . . , a ) with the following properties:
    0 2018
    2018
    • For 0 ≤ i ≤ 2018, a < 2 ;
    • For 1 ≤ i ≤ 2018, b = a + a and c = a | a ;ii i − 1 i i i − 1 iwhere | denotes the bitwise or operation?
    (The bitwise or of two nonnegative integers x = · · · x x x x and y = · · · y y y y expressed in binary
    3 2 1 0 3 2 1 0
    is defined as x | y = · · · z z z z , where z = 1 if at least one of x and y is 1, and 0 otherwise.)
    3 2 1 0 i i i
    4 3 21
解析

英文解析

  1. For how many pairs of sequences of nonnegative integers ( b , b , . . . , b ) and ( c , c , . . . , c ) does
    1 2 2018 1 2 2018
    there exist a sequence of nonnegative integers ( a , . . . , a ) with the following properties:
    0 2018
    2018
    • For 0 ≤ i ≤ 2018, a < 2 ;
    • For 1 ≤ i ≤ 2018, b = a + a and c = a | a ;ii i − 1 i i i − 1 iwhere | denotes the bitwise or operation?
    (The bitwise or of two nonnegative integers x = · · · x x x x and y = · · · y y y y expressed in binary
    3 2 1 0 3 2 1 0
    is defined as x | y = · · · z z z z , where z = 1 if at least one of x and y is 1, and 0 otherwise.)
    3 2 1 0 i i i
    Proposed by: Kevin Sun
    2019 2018
    Answer: (2 − 1)
    Define the bitwise and of two nonnegative integers x = · · · x x x x and y = · · · y y y y expressed in
    3 2 1 0 3 2 1 0
    binary to be x & y = · · · z z z z , where z = 1 if both x and y are 1, and 0 otherwise.
    3 2 1 0 i i i
    Now, we can prove that from the definitions of | and & that x + y = ( x | y ) + ( x & y ). Therefore itsuffices to count pairs of sequences ( c , c , . . . , c ) and ( d , d , . . . , d ) such that c = a | a and
    1 2 2018 1 2 2018 i i − 1 i
    2018
    d = a & a for 0 ≤ a < 2 .
    i i − 1 i i
    Since both | , & are bitwise operations, it suffices to count the number of sequences { c } and { d }
    i ikrestricting each a to { 0 , 2 } for each k ∈ [0 , 2017] and multiply these counts together. Each sequenceik k k
    ( a , . . . , a ) leads to a unique { c } and { d } except for the sequences (2 , 0 , 2 , 0 , . . . , 2 ) and the
    0 2018 i ik ksequences (0 , 2 , 0 , 2 , . . . , 0), which lead to the same { c } and { d } .
    i i
    2019
    Therefore for each k , there are 2 − 1 ways to determine the k -th bits of each c and d . Multiplyingi i
    2019 2018
    this over all k gives a final count of (2 − 1) .
    4 3 2 1