以下合同式の法を $3$ とする.
$2$ 進法で表記した $n$ について,$2^{m-1}$ の位の数を $x_m$ とする.すなわち,$x_m=0$ または $x_m=1$ であり,
$$n=\sum_{m=1}^{15} (2^ {m-1} x_m)$$
となる.
$x_m=0$ のとき,$2^ {m-1} x_m≡0$ である.また,$x_m=1$ のとき,$m$ が奇数ならば $2^ {m-1} x_m≡1$ であり,$m$ が偶数ならば $2^ {m-1} x_m≡2$ である.そして,$x_{15}=1$ より $2^ {14} x_ {15}≡1$ だから,これらを考慮することでこの問題は以下の問題に帰着できる.
区別できる $14$ 枚のカードがあり,そのうち $7$ 枚には $1$ と,残りの $7$ 枚には $2$ と書かれています.このうち $9$ 枚を選ぶ方法で,書かれた数の総和を $3$ で割った余りが $2$ となるようなものは何通りありますか.
これは選ばれなかった $5$ 枚のカードに書かれた数の総和を $3$ で割った余りが $1$ となることと同値で,さらにこれは選ばれなかった $5$ 枚のカードに書かれた数の組が $(1,1,1,2,2)$ または $(2,2,2,2,2)$ であることと同値である.前者は ${}_{7}\mathrm{C}_{3}\cdot{}_{7}\mathrm{C}_{2}=735$ 通り,後者は ${}_{7}\mathrm{C}_{5}=21$ 通り存在するので,この問題の答えは $756$ 通りである.
よって,元の問題の答えも $\mathbf{756}$ 個である.
この問題を解いた人はこんな問題も解いています