PUMaC 2011 · 组合（A 组） · 第 6 题
PUMaC 2011 — Combinatorics (Division A) — Problem 6
题目详情
- [ 6 ] For every integer n from 0 to 6, we have 3 identical weights with weight 2 . How many ways are there to form a total weight of 263 grams using only these given weights?
解析
- First solution : Turning to generating functions, this is the same problem as asking for the 263 coefficient of x in the polynomial 2 3 2 4 6 64 128 192 (1 + x + x + x )(1 + x + x + x ) · · · (1 + x + x + x ) and we can simplify the polynomial by telescoping: 4 8 256 128 256 x − 1 x − 1 x − 1 x − 1 x − 1 · · · · = · 2 64 2 x − 1 x − 1 x − 1 x − 1 x − 1 2 4 126 2 255 = (1 + x + x + · · · + x )(1 + x + x + · · · + x ) . 263 From here we can easily calculate the coefficient of x to be 60 . 2 Second solution : First, notice the sum of all of the weights is 127 × 3 = 381, and any combination of weights that sum to 263 corresponds to a combination of weights that sum to 381 − 263 = 118 (by using the leftover weights instead). So we instead consider the number of ways of forming a total weight of 118. Then, we can construct a bijection between any set of weights to the set of even nonnegative integers 2 m ≤ 118: use twice the weights corresponding to the binary expansion of m , and then add the weights corresponding to the binary expansion of 118 − 2 m . This is possible because the binary expansion of any natural number less than or 6 equal to 118 has at most 7 binary digits, corresponding to 2 = 64. Conversely, for any such n combination of weights, if zero or one of the 2 weights are used, then the corresponding binary n digit for m will be 0, while if two or three of the 2 weights are used, then the corresponding 118 binary digit for m will be 1. So again, there are + 1 = 60 ways in total. 2