前回の記事で書いた「硬貨3種類の Change-Making Problem（お釣り生成問題）を解く計算量 log オーダーのアルゴリズム」の解説です。
完結した証明として書きたかったのですが時間がかかっていてすぐには記事として完成できそうにないのでまずはキーとなるアイデアから解説していきます。
今後少しずつ解説を追加していって最終的には完全な証明にしていこうと思います。

準備

$u_1, u_2, n, a_i, p_i, q_i, r_i, l$ などの表記は前回の記事と同様に使います。

$y$ は $u_1$ の枚数、$z$ は $u_2$ の枚数、$x$ は $1$ の枚数を表すのに使いますが並びが $x,y,z$ の順でないのはアルゴリズムを模索する際に $n$ を $u_1$ で割った余りと商を $1, u_1$ の枚数と結びつけて $XY$座標上で考えたことの名残りです。

特に断り書き等がない限り変数は非負の整数を表すものとします。

定義

表現、最小枚数表現、最適表現

$n = y u_1 + z u_2 + x$ を満たすとき $(y, z, x)$ は $n$ の表現、
$n$ の表現の中で総枚数 $y + z + x$ が最も小さい表現を $n$ の最小枚数表現、
$n$ の最小枚数表現の中で $u_1$ の枚数 $y$ が最も大きいものを $n$ の最適表現
と呼ぶことにします。
最適表現は必ず存在して一意に決まります。

例えば硬貨が $11, 6, 1$ の 3種類のとき
$(0,0,12), (0,1,6), (0,2,0), (1,0,1)$ が $12$ の表現のすべて、
$(0,2,0), (1,0,1)$ が $12$ の最小枚数表現、
$(1,0,1)$ が $12$ の最適表現です。

QUOT, REM, Y, X

$n$ を $u_1$ で割った商と余りを $QUOT(n)$ と $REM(n)$ と書くことにします。
また
$Y(n, z) = QUOT(n - z u_2)$
$X(n, z) = REM(n - z u_2)$
と定義します。

$n - z u_2 = QUOT(n - z u_2) u_1 + REM(n - z u_2)$ なので $z u_2 \le n$ のとき
$(Y(n, z), z, X(n, z))$ は $n$ の表現の一つです。

条件1

$p$ に対する次の条件を条件1と呼ぶことにします。

$a_i = QUOT(i u_2), b_i = REM(i u_2)$ としたとき
$0 \lt i \le p$ であるすべての $i$ に対して $a_i + b_i \gt i$ が成り立つ.

この条件は $0 \lt i \le p$ の範囲で金額 $i u_2$ を払うなら $u_2$ だけ使った方が $u_1$ と $1$ だけ使って払うより枚数が少なくてすむということを意味しています。

条件2

$n$ と $p$ に対する次の条件を条件2と呼ぶことにします。

$n \ge p u_2$ かつ
$0 \le i \lt p$ であるすべての $i$ に対して $X(n,i) \gt X(n,p)$ が成り立つ.

この条件は $u_2$ を $p$枚使った残りの金額 $n - p u_2$ がいい感じに $u_1$ の倍数に近いということを意味しています。

アルゴリズムの正当性の証明（途中まで）

いよいよ証明に入ります。

まずは当たり前にも思える次の補題から。

補題1

$y \ge y', z \ge z', x \ge x'$ で
$(y, z, x)$ が $n$ の最適表現ならば
$(y - y', z - z', x - x')$ が $n - (y' u_1 + z' u_2 + x')$ の最適表現である.

特に $y' = 0, z' = z, x' = 0$ の場合にあてはめると
$(y, 0, x)$ が $n - z u_2$ の最適表現で $y = Y(n, z), x = X(n, z)$ であり
$n$ の最適表現は $(Y(n,z), z, X(n,z))$ という形になる.

証明

$(y'', z'', x'')$ を $n - (y' u_1 + z' u_2 + x')$ の最適表現とすると
$n - (y' u_1 + z' u_2 + x') = y'' u_1 + z'' u_2 + x''$ なので
$n = (y'+y'') u_1 + (z'+z'') u_2 + (x'+x'')$.
よって $(y'+y'', z'+z'', x'+x'')$ も $n$ の表現.
$(y, z, x)$ は $n$ の最適表現（したがって最小枚数表現）だったので

y + z + x \le (y'+y'') + (z'+z'') + (x'+x'')

同様に $(y-y', z-z', x-z')$ は $n - (y' u_1 + z' u_2 + x')$ の表現で
$(y'', z'', x'')$ は $n - (y' u_1 + z' u_2 + x')$ の最適表現（したがって最小枚数表現）だったので

y'' + z'' + x'' \le (y-y') + (z-z') + (x-x')

したがって

y + z + x = (y'+y'') + (z'+z'') + (x'+x'')

$(y, z, x)$ と $(y'+y'', z'+z'', x'+x'')$ の両方とも $n$ の最小枚数表現になるが前者はその中でも最適表現なので $y \ge y'+y''$.
$(y-y', z-z', x-x')$ と $(y'', z'', x'')$ の両方とも $n - (y' u_1 + z' u_2 + x')$ の最小枚数表現になるが後者はその中でも最適表現なので $y - y' \le y''$.
よって $y = y'+y''$.
したがって $z + x = (z' + z'') + (x'+x'')$
それと $z u_2 + x = n - y u_1 = n - y' u_1 = (z' + z'') u_2 + (x'+x'')$ でもあるので
$z = z'+z', x = x+x'$ であることもわかる.

特に $y' = 0, z' = z, x' = x$ のケースに適用すると $n - z u_2$ の最適表現は $(y, 0, x)$ になる.
この最適表現は $u_2$ の使用枚数は $0$ なので後は $u_1$ を貪欲に使っていくのが最適なのは明らか。
よって $y = Y(n,z), \ x = X(n,z)$ になる.

【証明終わり】

この補題から、もしこのような正整数 $z'$ を確定することができれば $n$ の最適表現を求める問題をより金額の小さい $n - z' u_2$ の最適表現を求める問題に帰着できることがわかります。

補題2

$n$ の最適表現が $(y, p, x)$ で $p \gt 0$ ならば
$p$ は条件1 を満たし、$n$ と $p$ は条件2 を満たす.

条件1と条件2を満たす $p \gt 0$ が存在しない場合は $n$ の最適表現は $(QUOT(n), 0, REM(n))$ になる.

証明

$p$ が条件1を満たさないと仮定すると $QUOT(i u_2) + REM(i u_2) \le i, 0 \lt i \le p$ を満たす $i $ が存在する.
見やすいように $QUOT(i u_2), REM(i u_2)$ を $a,b$ で 書き直すと
$i u_2 = a u_1 + b$ で $a + b \le i$.
このとき $a \gt 0$ である。なぜなら $a = 0$ とすると $b = i u_2$ と $i > 0, u_2 > 1$ から $a+b = i u_2 \gt i$ となってしまう.

$i u_2 = a u_1 + b$ なので表現 $(y,p,x)$ の $p$枚の $u_2$ のうち $i$枚を $a$枚の $u_1$ と $b$枚の 1 に置き換えた表現 $(y+a,p-i,x+b)$ もまた $n$ の表現である.
その総枚数 $y+p+x-(i-a-b)$ は $y+p+x$ 以下で（なぜなら $i \ge a +b$ だから）
しかも $u_1$ の使用枚数で見ても $y+a \gt y$ である.
これは $(y,p,x)$ が最適表現であることに矛盾する. よって $p$ は条件1を満たす.

$p$ が条件2を満たさないと仮定すると $X(n, i) \le X(n, p)$ を満たすある $i \lt p$ が存在する.
（$n \ge p u_2$ の方は $n = y u_1 + p u_2 + x$ から明らか）

$(y, p, x)$ は $n$ の最適表現なので補題1から $y = Y(n, p), x = X(n, p)$.
$(Y(n, i), i, X(n, i))$ と $(Y(n, p), p, X(n, p))$ はどちらも $n$ の表現なので

\begin{align}
&(Y(n, i) - Y(n, p)) u_1 = (p - i) u_2 + (X(n, p) - X(n, i)). \\
&  u_1 \gt u_2 \gt 1, p \gt i と \\
&  X(n, p) \ge X(n, i) （背理法の仮定はここで効いてくる） なので \\
&(Y(n, i) - Y(n, p)) u_1 \lt (p - i) u_1 + (X(n, p) - X(n, i)) u_1 \\
& = (p - i + X(n, p) - X(n, i)) u_1 \\
&  両辺を u_1 で割って \\
&Y(n, i) - Y(n, p) \lt p - i + X(n, p) - X(n, i) \
\end{align}

したがって

Y(n, i) + i + X(n, i) \lt Y(n, p) + p + X(n, p) = y + p + x

これは $(y,p,x)$ が最適表現（したがって最小枚数表現）であることに矛盾. よって $n$ と $p$ は条件2を満たす.

対偶をとると
条件1と条件2を満たす $p \gt 0$ が存在しない場合は $u_2$ の使用枚数が正の最適表現は存在しない、つまり $u_2$ の使用枚数は $0$ となる.
補題1より最適表現は $(Y(n,0),0,X(n,0))$、つまり $(QUOT(n),0,REM(n))$ になる。

【証明終わり】

補題3

$n$ の最適表現を $(y, i, x)$ とする.
$p$ は条件1 を満たし、かつ $n$ と $p$ は条件2 を満たすならば $i \ge p$.

証明

もし $i \lt p$ と仮定する。

補題1より $y = Y(n, i), x = X(n, i)$.
$(Y(n, i), i, X(n, i))$ と $(Y(n, p), p, X(n, p))$ はどちらも $n$ の表現なので
$(p - i) u_2 = (Y(n, i) - Y(n, p)) u_1 + (X(n, i) - X(n, p))$ であり
見やすいように $j = p - i, a = Y(n, i) - Y(n, p), b = X(n, i) - X(n, p)$ として書き直すと

\begin{align}
&j u_2 = a u_1 + b, 0 \lt j \le p
\end{align}

背理法の仮定より $i \lt p$ なので条件2から $0 \le X(n, p) \lt X(n, i) \lt u_1$.
$0 \lt X(n, i) - X(n, p) \lt u_1$. よって $0 \lt b \lt u_1$.
したがって $a$ と $b$ は $j u_2$ を $u_1$ で割った商と余りになっていることがわかる.
$0 \lt j \le p$ なので条件1より $a + b \gt j$.
$a,b,j$ を元に戻して $(Y(n, i) - Y(n, p)) + (X(n, i) - X(n, p)) \gt p - i$.
したがって

Y(n, p) + p + X(n, p) \lt Y(n, i) + i + X(n, i) = y + i + x

これは $(y, i, x)$ が最適表現（したがって最小枚数表現）であることに矛盾するので $i \ge p$ である.

【証明終わり】

今後の展開

$n$ に対して条件1と条件2を満たす $p$ を探し、見つかれば補題3と補題1により $n - p u_2$ の問題に帰着でき、見つからなければ（存在しなければ）補題2により後は $u_1$ を貪欲に使う簡単な問題に帰着できます。

条件2を満たす $p$ を見つけるのに連分数の理論が利用できます。

次回掲載予定命題は

$QUOT(n) \ge q_{2k-1}$ かつ $r_{2k-1} \le REM(n) \lt r_{2k-2}$ ならば $n$ と $p = p_{2k-1}$ は条件2 を満たす.

です。

今回はここまで。次の更新に続く。(To be continued)