Problem
COM-B2-M09-P020 Binary Weights with Carries
Let \(m\ge 1\). There are weights \(2^0,2^1,\ldots,2^{m-1}\), and each weight may be taken \(0\), \(1\), \(2\), or \(3\) times. In how many ways can one obtain total weight \(2^m-1\)?
Write the coefficient of \(\prod_{i=0}^{m-1}(1+x^{2^i}+x^{2\cdot 2^i}+x^{3\cdot 2^i})\), but count it using carries in binary notation.
Let \(a_i\in\{0,1,2,3\}\) be the number of weights \(2^i\) taken. We need to solve \(\sum_{i=0}^{m-1}a_i2^i=2^m-1\), whose binary form consists of \(m\) ones.
Process the digits from low to high. Before each digit, the carry is \(0\) or \(1\). If the carry is \(0\), then to obtain a one in this digit we may take \(a_i=1\) and keep carry \(0\), or take \(a_i=3\) and create carry \(1\). If the carry is \(1\), then we may take \(a_i=0\) and get carry \(0\), or take \(a_i=2\) and keep carry \(1\). Thus after each of the \(m\) digits, the number of ways to reach carry \(0\) equals the number of ways to reach carry \(1\), and both are the sum of the two previous states.
After the first digit, there is \(1\) way in each state. After \(m\) digits, each state has \(2^{m-1}\) ways. At the end, the carry must be \(0\); otherwise the sum exceeds \(2^m-1\). Therefore the answer is \(2^{m-1}\).
A strong problem: the formal generating function is present, but the key move is seeing the carries.