HMMT 二月 2018 · ALGNT 赛 · 第 8 题
HMMT February 2018 — ALGNT Round — Problem 8
题目详情
- 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 ; i • For 1 ≤ i ≤ 2018, b = a + a and c = a | a ; i i − 1 i i i − 1 i where | 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 1 4 3 2
解析
- 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 ; i • For 1 ≤ i ≤ 2018, b = a + a and c = a | a ; i i − 1 i i i − 1 i where | 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 it suffices 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 i k restricting each a to { 0 , 2 } for each k ∈ [0 , 2017] and multiply these counts together. Each sequence i k 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 i k k sequences (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 . Multiplying i i 2019 2018 this over all k gives a final count of (2 − 1) . 4 3 2 1