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 ;
• 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
解析
英文解析
- 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