(cache)フロベニウスの硬貨交換問題 | 高校数学の美しい物語

$A$ と $B$ が互いに素なとき， $A$ 円の硬貨と $B$ 円の硬貨を使って支払えない金額の最大値は $(A B - A - B) = {(A - 1) (B - 1) - 1}$ 円。

フロベニウスの硬貨交換問題（硬貨が二種類の場合）についての美しい結果とその証明の解説。

フロベニウスの硬貨交換問題について

・与えられた何種類かの硬貨を使って「払えない金額の最大値（フロベニウス数と呼ばれる）」を求める問題をフロベニウスの硬貨交換問題と言います。硬貨が二種類の場合には冒頭に挙げた美しい結果が得られます。

・大学受験や数学オリンピックでも出題されたことがある有名問題です。例えば，以下は2000年JMO予選第二問です。

例題

$3 a + 5 b$ （ただし $a, b$ は非負整数) の形で表わせない正の整数の最大値を求めよ。

解答

数字が小さいので具体的に実験していけば答えを求めるのは難しくありません。しかし，冒頭の定理を認めれば一発です！
$A = 3, B = 5$ の場合なので答えは $15 - 3 - 5 = 7$

硬貨が三種類以上の場合には，冒頭のような綺麗な結果は知られていません。
$A$ と $B$ が互いに素という条件は必須です。もし $A$ と $B$ がともに $d (\geq 2)$ の倍数だと， $d$ の倍数以外の金額はどう頑張っても支払えません。

定理の証明1

主張を二つに分解します。

主張1：( $A B - A - B$ )円はどう頑張っても支払えない
主張2： $(A B - A - B + 1)$ 円以上はうまくすれば支払える

まずは比較的簡単な主張1から証明します。

証明

背理法で証明する。もし $A B - A - B$ 円が支払えると仮定すると，非負整数 $x, y$ が存在して
$A x + B y = A B - A - B$ （※）となる。
変形すると， $B (y + 1) = A (B - 1 - x)$
右辺が $A$ の倍数であることと $A$ と $B$ が互いに素であることから $y + 1$ は $A$ の倍数。同様に， $B - 1 - x$ は $B$ の倍数。つまり $x + 1$ は $B$ の倍数。
よって， $x + 1 \geq B$ かつ $y + 1 \geq A$ なので，
$A x + B y \geq A (B - 1) + B (A - 1) = 2 A B - A - B$
となり，（※）に矛盾。

定理の証明2

主張2の証明にはベズーの定理を使います。→一次不定方程式ax+by=cの整数解
$A$ と $B$ が互いに素なとき， $A x + B y = k$ を満たす整数 $x, y$ が存在するという定理です。難関大の入試にちょうどよいレベルです。

証明

$k \geq A B - A - B + 1$ のとき， $A x + B y = k$ を満たす非負整数 $x, y$ が存在することを証明する。

ベズーの定理より $A x + B y = k$ を満たす（非負とは限らない）整数 $x, y$ が存在する。そのような解は無数にあるが， $x \geq 0$ なる解の中で $x$ が最小なものを $(x_{0}, y_{0})$ とする。
すると $0 \leq x_{0} \leq B - 1$ である（なぜなら， $(x, y)$ が解なら $(x - B, y + A)$ も解だから）。

よって，
$y_{0} = \frac{1}{B} (k - A x_{0}) \geq \frac{1}{B} {A B - A - B + 1 - A (B - 1)} = \frac{1}{B} - 1 > - 1$
よって， $y_{0} \geq 0$ となり，非負の整数解 $(x_{0}, y_{0})$ が構成できた。

シルベスターの定理

以上より， $A$ 円と $B$ 円の硬貨で払えない額 $k$ として考えられるのは， $1 \leq k \leq A B - A - B$ の範囲のものです。その候補たちの中で実際に支払えない額は $\frac{(A - 1) (B - 1)}{2}$ 通りであることが知られています（シルベスターの定理）。

例

先ほどの $A = 3, B = 5$ の場合において，支払えない額は $1, 2, 4, 7$ の四通り。これは $\frac{2 \times 4}{2} = 4$ と一致している。

大学入試でも出題されたことがあるのですが，どこの大学の問題か忘れてしまいました。