OMC222(D)

　$1!$ から $3! = 6$ 円札を $2$ 枚まで用いることで，$1$ 円から $18$ 円まで $1$ 円刻みでちょうど払うことができる．一方で，$n \geq 4$ においては，帰納的に $$2\cdot1!+2\cdot2!+\cdots+2\cdot(n-1)! \lt n!$$ が示すことができるため，$n!$ 円未満のお札を $2$ 枚ずつ用いた金額よりも $n!$ の方が大きくなる．したがって，使用した $n!$ 円札の枚数ごとに異なる合計金額が対応する．したがって $n \geq 4$ のとき，$n!$ 円札までを使用して作ることのできる金額の種類は，$19 \cdot 3^{n-3}-1$ 種類であり，これらは $0 \le C \le 18$ および $c_4, c_5, \ldots, c_n \in \{0, 1, 2 \}$（すべてが $0$ とはならない）によって $$C + c_4 \cdot 4! + c_5 \cdot 5! + \cdots + c_n \cdot n!$$ と一意に表示される．さらに，これはちょうど支払える金額のうち，小さい方から $$C + c_4 \cdot 19 \cdot 3^0 + c_5 \cdot 19 \cdot 3^1 + \cdots + c_n \cdot 19 \cdot 3^{n-4}$$ 番目のものであることもわかる．これが $1000$ に等しくなるのは，$n=7$ かつ $$(C, c_4, c_5, c_6, c_7) = (12, 1, 2, 2, 1)$$ のときである．このとき，支払われた金額は $$12 + 1 \cdot 4! + 2 \cdot 5! + 2 \cdot 6! + 1 \cdot 7! = \mathbf{6756}$$ 円である．