Задача
COM-B2-M09-P020 Двоичные грузы с переносами
Пусть \(m\ge 1\). Есть грузы весов \(2^0,2^1,\ldots,2^{m-1}\), и груз каждого веса можно взять \(0\), \(1\), \(2\) или \(3\) раза. Сколькими способами можно получить общий вес \(2^m-1\)?
Запишите коэффициент произведения \(\prod_{i=0}^{m-1}(1+x^{2^i}+x^{2\cdot 2^i}+x^{3\cdot 2^i})\), но считайте его через переносы в двоичной записи.
Пусть \(a_i\in\{0,1,2,3\}\) - сколько грузов веса \(2^i\) взято. Нужно решить \(\sum_{i=0}^{m-1}a_i2^i=2^m-1\), то есть получить двоичную запись из \(m\) единиц.
Считаем слева направо по разрядам снизу вверх. Пусть перед очередным разрядом перенос равен \(0\) или \(1\). Если перенос \(0\), чтобы получить единицу в разряде, нужно взять \(a_i=1\) и оставить перенос \(0\), либо \(a_i=3\) и создать перенос \(1\). Если перенос \(1\), нужно взять \(a_i=0\) и получить перенос \(0\), либо \(a_i=2\) и оставить перенос \(1\). Поэтому после каждого из \(m\) разрядов число способов прийти в состояние переноса \(0\) равно числу способов прийти в состояние переноса \(1\), и оба равны сумме двух предыдущих состояний.
После первого разряда получаем по \(1\) способу в состояниях \(0\) и \(1\). После \(m\) разрядов в каждом состоянии \(2^{m-1}\) способов. В конце перенос должен быть \(0\), иначе сумма превысит \(2^m-1\). Значит, ответ \(2^{m-1}\).
Сильная задача: формальная производящая функция есть, но основной ход - увидеть переносы.