フロベニウスの硬貨交換問題

更新 2023/04/16

$A$ と $B$ が互いに素なとき， $A$ 円の硬貨と $B$ 円の硬貨を使って支払えない金額の最大値は

$(AB-A-B)=\{(A-1)(B-1)-1\}$ 円。

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

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

与えられた何種類かの硬貨を使って「払えない金額の最大値」を求める問題をフロベニウスの硬貨交換問題と言います。
「払えない金額の最大値」をフロベニウス数と呼びます。
硬貨が二種類の場合には冒頭に挙げた美しい結果が得られます。
大学受験や数学オリンピックでも出題されたことがある有名問題です。例えば，以下は2000年JMO予選第二問です（2000年の大阪大学理系第三問もほとんど同じ問題です）。

例題

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

数が小さいので具体的に実験していけば答えを求めるのは難しくありません。しかし，冒頭の定理を認めれば一発です！

解答

$A=3,\:B=5$ の場合なので答えは

$AB-A-B\\ =15-3-5=7$

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

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

主張1： $(AB-A-B)$ 円はどう頑張っても支払えない

主張2： $(AB-A-B+1)$ 円以上はうまくすれば支払える

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

主張1の証明

背理法で証明する。もし $AB-A-B$ 円が支払えると仮定すると，非負整数 $x,\:y$ が存在して

$Ax+By=AB-A-B$ （※）となる。

変形すると， $B(y+1)=A(B-1-x)$

右辺が $A$ の倍数であることと $A$ と $B$ が互いに素であることから $y+1$ は $A$ の倍数。同様に， $B-1-x$ は $B$ の倍数。つまり $x+1$ は $B$ の倍数。

よって， $x+1\geqq B$ かつ $y+1\geqq A$ なので，

$Ax+By\geqq A(B-1)+B(A-1)=2AB-A-B$

となり（※）に矛盾。

主張2の証明にはベズーの定理を使います。→一次不定方程式ax+by=cの整数解

$A$ と $B$ が互いに素なとき， $Ax+By=k$ を満たす整数 $x,y$ が存在するという定理です。難関大の入試にちょうどよいレベルです。

主張2の証明

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

ベズーの定理より $Ax+By=k$ を満たす（非負とは限らない）整数 $x,y$ が存在する。そのような解は無数にあるが， $x\geqq 0$ なる解の中で $x$ が最小なものを $(x_0,y_0)$ とする。

すると $0\leqq x_0\leqq B-1$ である（なぜなら， $(x,y)$ が解なら $(x-B,y+A)$ も解だから）。

よって，

$y_0=\dfrac{1}{B}(k-Ax_0)\\\geqq \dfrac{1}{B}\{AB-A-B+1-A(B-1)\}\\=\dfrac{1}{B}-1 > -1$

よって， $y_0\geqq 0$ となり，非負の整数解 $(x_0,y_0)$ が構成できた。

以上より， $A$ 円と $B$ 円の硬貨で払えない額 $k$ として考えられるのは， $1\leqq k\leqq AB-A-B$ の範囲のものです。

実は，その候補たちの中で実際に支払えない額は $\dfrac{(A-1)(B-1)}{2}$ 通りであることが知られています（シルベスターの定理）。

例

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

フロベニウスの硬貨交換問題の特殊ケースのことを「チキンマックナゲット数（を求める問題）」と呼ぶこともあるようです。

この記事の監修者

マスオ

高校数学の美しい物語の管理人。「わかりやすいこと」と「ごまかさないこと」の両立を意識している。著書に『高校数学の美しい物語』『超ディープな算数の教科書』。記事の誤植やわかりにくい等のご指摘はお気軽にメールください！