PUMaC 2023 · 组合（A 组） · 第 2 题
PUMaC 2023 — Combinatorics (Division A) — Problem 2
题目详情
- Let ⊕ denote the xor binary operation. Define x ⋆ y = ( x + y ) − ( x ⊕ y ). Compute 63 X ( k ⋆ 45) . k =1 ( Remark: The xor operator works as follows: when considered in binary, the k th binary digit of a ⊕ b is 1 exactly when the k th binary digits of a and b are different. For example, 5 ⊕ 12 = 0101 ⊕ 1100 = 1001 = 9.) 2 2 2
解析
- Let ⊕ denote the xor binary operation. Define x ⋆ y = ( x + y ) − ( x ⊕ y ). Compute 63 X ( k ⋆ 45) . k =1 ( Remark: The xor operator works as follows: when considered in binary, the k th binary digit of a ⊕ b is 1 exactly when the k th binary digits of a and b are different. For example, 5 ⊕ 12 = 0101 ⊕ 1100 = 1001 = 9.) 2 2 2 Proposed by Julian Shah Answer: 2880 Solution 1: Consider pairing the k th term with the (63 − k )th term: ( k ⋆ 45) + ((63 − k ) ⋆ 45) = 63 + 2 · 45 − [ k ⊕ 45 + (63 − k ) ⊕ 45] k and 63 − k differ in every binary digit, so the values of k ⊕ 45 and (63 − k ) ⊕ 45 will be completely complementary; hence, they add to 63 (when performing the addition k ⊕ 45, switching a 0 to a 1 in k ’s representation will switch the result of that output digit). 63 P So, when we pair k and 63 − k , the result is 2 · 45. This means ( k ⋆ 45) = 64 · 45, but k =0 (0 ⋆ 45) = 45 − 45 = 0, so our final answer is actually 64 · 45 = 2880 . Solution 2: For any x and y , we can obtain the relationship: ( x ⊕ y ) + 2( x & y ) = x + y , where x & y is the bitwise- and operator: x & y has a 1 in a place only if both x and y do. This occurs since x ⊕ y returns 0 in all places where x and y are both 1, whereas under normal addition this should contribute 2 times that place value. Adding 2( x & y ) covers this difference. Therefore, x ⋆ y = ( x + y ) − ( x ⊕ y ) = 2( x & y ). Again, note that ((63 − k )&45) + ( k &45) = 45. Collectively, k and 63 − k will ‘select’ all the 1’s places of 45, so adding them will return exactly 45. 63 P Using the same trick as earlier, ( k &45) = 32 · 45, so our answer is twice this, 2 · 32 · 45 = 2880 . k =0 1