盒中装有红色和蓝色纸牌各 $100$ 张，每色纸牌都含标数为 $1,3,3^{2},\cdots,3^{99}$ 的牌各一张，两色纸牌的标数总和记为 $S$；对于给定的正整数 $n$，若能从盒中取出若干张牌，使其标数之和恰为 $n$，便称为一种取牌 $n{\_}$ 的方案，不同的 $n{\_}$ 方案种数记为 $f(n)$；试求 $f(1)+f(2)+\cdots+f(S)$ 之值．
【难度】
【出处】
2013年全国高中数学联赛山西省预赛
【标注】
【答案】
$2^{200}-1$
【解析】
将盒中的纸牌按标数自小到大的顺序排成一列：$$1,1,3,3,3^{2},3^{2},\cdots,3^{99},3^{99},$$值相等的两个项不同色．
对于每个 $k(1\leqslant k\leqslant 100)$，数列前 $2k$ 项之和为 $3^k-1$，小于 $3^{k}$，故形如 $3^{n}$ 的项必须从两个 $3^{n}$ 中选出（任何其它项的和不等于 $3^{n}$），于是选出一个 $3^{n}$ 有两种方法，同时选出两个 $3^{n}$ 只有一种方法．
对于集合 $A=\{0,1,2,\cdots,S\}$ 中的每个元素 $m$，可将其表为含有一百个数位的三进制形式：\[m=\overline{a_{99}a_{98}\cdots a_{1}a_{0}},\]即$$m=a_{0}+a_{1}\cdot 3+a_{2}\cdot 3^{2}+\cdots+a_{99}\cdot 3^{99},$$其中$$a_{i}\in \{0,1,2\},i=0,1,2,3,\cdots,99.$$若在 $a_{0},a_{1},a_{2},\cdots,a_{99}$ 中恰有 $k$ 个为 $1$（其余 $100-k$ 个数为 $0$ 或 $2$），而每个 $1$ 有红蓝两种选取方案，所以$$f(m)=2^{k}.$$先将集合 $A$ 分解为\[A=A_{0}\cup A_{1}\cup A_{2}\cup \cdots\cup A_{100},\]其中 $A_{k}$ 中的每个数 $m$ 在表示成上述三进制形式后，其系数 $a_{0},a_{1},a_{2},\cdots,a_{99}$ 恰有 $k$ 个为 $1$（其余 $100-k$ 个数为 $0$ 或 $2$）．
因为从 $a_{0},a_{1},a_{2},\cdots,a_{99}$ 中选取 $k$ 个为 $1$，有 ${\rm C}_{100}^{k}$ 种选法，其余 $100-k$ 个数，每个可取作 $0$ 或 $2$，有 $2^{100-k}$ 种方法，因此集合 $A_{k}$ 中，共有$${\rm C}_{100}^{k}\cdot 2^{100-k}$$个数．
这样，$A_{k}$ 中各数的 $f$ 值之和为\[\sum\limits_{m\in A_{k}}f(m)=2^{k}\cdot {\rm C}_{100}^{k}\cdot 2^{100-k}=2^{100}\cdot {\rm C}_{100}^{k},\]由于集合 $A_{0},A_{1},A_{2},\cdots,A_{100}$ 两两不相交，从而\[\begin{split}\sum\limits_{m\in A}f(m)&=\sum\limits_{m\in A_{0}}f(m)+\sum\limits_{m\in A_{1}} f(m)+\sum\limits_{m\in A_{2}}f(m)+\cdots+\sum\limits_{m\in A_{100}}f(m)\\&=2^{100}\left({\rm C}_{100}^{0}+{\rm C}_{100}^{1}+\cdots+{\rm C}_{100}^{100}\right)\\&=2^{100}\cdot 2^{100}\\&=2^{200}.\end{split}\]注意到\[0=0+0\cdot 3+0\cdot 3^{2}+\cdots+0\cdot 3^{99},\]即数列中的每个数都不选，其方案数 $f(0)=1$，所以\[f(1)+f(2)+\cdots+f(S)=2^{200}-1.\]
对于每个 $k(1\leqslant k\leqslant 100)$，数列前 $2k$ 项之和为 $3^k-1$，小于 $3^{k}$，故形如 $3^{n}$ 的项必须从两个 $3^{n}$ 中选出（任何其它项的和不等于 $3^{n}$），于是选出一个 $3^{n}$ 有两种方法，同时选出两个 $3^{n}$ 只有一种方法．
对于集合 $A=\{0,1,2,\cdots,S\}$ 中的每个元素 $m$，可将其表为含有一百个数位的三进制形式：\[m=\overline{a_{99}a_{98}\cdots a_{1}a_{0}},\]即$$m=a_{0}+a_{1}\cdot 3+a_{2}\cdot 3^{2}+\cdots+a_{99}\cdot 3^{99},$$其中$$a_{i}\in \{0,1,2\},i=0,1,2,3,\cdots,99.$$若在 $a_{0},a_{1},a_{2},\cdots,a_{99}$ 中恰有 $k$ 个为 $1$（其余 $100-k$ 个数为 $0$ 或 $2$），而每个 $1$ 有红蓝两种选取方案，所以$$f(m)=2^{k}.$$先将集合 $A$ 分解为\[A=A_{0}\cup A_{1}\cup A_{2}\cup \cdots\cup A_{100},\]其中 $A_{k}$ 中的每个数 $m$ 在表示成上述三进制形式后，其系数 $a_{0},a_{1},a_{2},\cdots,a_{99}$ 恰有 $k$ 个为 $1$（其余 $100-k$ 个数为 $0$ 或 $2$）．
因为从 $a_{0},a_{1},a_{2},\cdots,a_{99}$ 中选取 $k$ 个为 $1$，有 ${\rm C}_{100}^{k}$ 种选法，其余 $100-k$ 个数，每个可取作 $0$ 或 $2$，有 $2^{100-k}$ 种方法，因此集合 $A_{k}$ 中，共有$${\rm C}_{100}^{k}\cdot 2^{100-k}$$个数．
这样，$A_{k}$ 中各数的 $f$ 值之和为\[\sum\limits_{m\in A_{k}}f(m)=2^{k}\cdot {\rm C}_{100}^{k}\cdot 2^{100-k}=2^{100}\cdot {\rm C}_{100}^{k},\]由于集合 $A_{0},A_{1},A_{2},\cdots,A_{100}$ 两两不相交，从而\[\begin{split}\sum\limits_{m\in A}f(m)&=\sum\limits_{m\in A_{0}}f(m)+\sum\limits_{m\in A_{1}} f(m)+\sum\limits_{m\in A_{2}}f(m)+\cdots+\sum\limits_{m\in A_{100}}f(m)\\&=2^{100}\left({\rm C}_{100}^{0}+{\rm C}_{100}^{1}+\cdots+{\rm C}_{100}^{100}\right)\\&=2^{100}\cdot 2^{100}\\&=2^{200}.\end{split}\]注意到\[0=0+0\cdot 3+0\cdot 3^{2}+\cdots+0\cdot 3^{99},\]即数列中的每个数都不选，其方案数 $f(0)=1$，所以\[f(1)+f(2)+\cdots+f(S)=2^{200}-1.\]
答案
解析
备注
