4 硬貨系

まずは、一般の硬貨系 (2), (3), (4) とその上限 ($+1$) である $N_{j}$ について考察する ($N_j\geq 2$)。 本稿では、$M_c$ 未満の金額をすべて一意的に表せる硬貨系を扱うことにする。

硬貨 $j_1$ だけを使って作れる最大額は、

$$(N_{j_1} - 1)j_1 = N_1 - 1$$

であり、これが $(j_2 - 1)$ 以上でないと $(j_2 - 1)$ 円が表せないし、 逆にこれが $j_2$ 以上だと $j_2$ を 2 通りで表せてしまうので、 この硬貨系ですべての金額を一意に表せるためには

$$j_2 = N_1 = N_{j_1}$$ (8)

であることが必要になる。

同様に硬貨 $j_1$, $j_2$ の 2 枚で作れる最大額は、 (8) より、

$$(N_{j_1} - 1)j_1 + (N_{j_2} - 1)j_2 = (j_2 - 1) + (N_{j_2} - 1)j_2 = N_{j_1} N_{j_2} - 1$$

であり、上と同じ理由で、この値は $j_3 - 1$ に等しい必要がある。 よって、

$$j_3 = N_{j_1}N_{j_2}$$ (9)

となる。 この議論を繰り返せば、結局すべての $k (\geq 2)$ に対し、

$$j_k = N_{j_1}N_{j_2}\cdots N_{j_{k-1}} = \prod_{i=1}^{k-1}N_{j_i}$$ (10)

となり、またこの硬貨系で表せる最大の金額 $+1$ である $M_c$ 円は

$$M_c = \prod_{k=1}^{m} N_{j_k} = \prod_{j\in K} N_j$$ (11)

となる。

命題 1.

$0\leq x< M_c$ の金額 $x$ に対して、 (10) を満たす硬貨系 (2), (3), (4) では、$x$ を表現する $U_1$ の硬貨の集まりが必ず存在し、 その硬貨の集まりは一意的に定まる。

証明

(10) より、 $\mathrm{Tot}(A)$ は、

$$\mathrm{Tot}(A) = n_{j_1} + N_{j_1}(n_{j_2} + N_{j_2}(n_{j_3}+\cdots))$$ (12)

のように表されることに注意する。

$\mathrm{Tot}(A) = x$ とすると、$n_{j_1}(A)$ は、 (12) より $x$ を $N_{j_1}$ で割った 余りとすればよい。 また $n_{j_2}(A)$ は、 $(x-j_1\cdot n_{j_1}(A))/N_{j_1}$ を $N_{j_2}$ で割った余りとすればよい。 これを繰り返していくことで仮定 3 を満たす $A (\in U_1)$ が構成される。

一意性は、もし $\mathrm{Tot}(A) = \mathrm{Tot}(B) = x$ ($A,B\in U_1$) で あるとすると、$n_{j_1}$ 成分の一意性 ( $n_{j_1}(A) = n_{j_1}(B)$) は、 $N_{j_1}$ で割った余りを考えればそれが成立することはわかるし、 $n_{j_2}$ 成分の一意性も、 上と同じように $(x-j_1\cdot n_{j_1}(A))/N_{j_1}$ を $N_{j_2}$ で割った余りを考えればよい。 以下同様にして繰り返せば、すべての $j\in K$ に対して、 $n_j(A) = n_j(B)$ であることがわかる。

この一般の硬貨系では、必要なときに使用できるお札は $M_c$ 円札であることになる。