フロベニウスの硬貨交換問題とその応用

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

フロベニウスの硬貨交換問題 Wikipediaという面白い問題を見つけたので紹介します。

指定された硬貨だけではぴったり払えない最大の金額を求める数学の問題。
例えば、3円と5円のコインだけでは作れない最大の金額は7円。
式で書くと、フロベニウス数 $g(3,5) = 7$

2個のコインの場合の公式

これは簡単な公式があって

\begin{align}
gcd(a_1, a_2) &= 1のとき　\\
\large g( a_1, a_2 ) &= a_1 a_2-a_1-a_2
\end{align}

例えば、$(a_1, a_2) = (3,5)$の時は$3 \times 5 - 3-5=7$となります。
念のため$a_1x + a_2y $で表せない数をプログラムでリストしてみると${1, 2, 4, 7}$となり$g(3,5)=7$となりそうです。

from itertools import product
a,b = 3,5
nall = set([n for n in range(31)])   # set of non-negative integers up to 30
lc =  set(sorted([a*x+b*y for x, y in product(range(6),repeat=2)]))
print(nall-lc)
#  {1, 2, 4, 7}

３個以上のコインの場合

３個以上のコインの場合は簡単な公式は無いようですが、ある条件の場合には導きだせるようです。以下の論文から必要な所だけ抽出すると、

• ON A LINEAR DIOPHANTINE PROBLEM OF FROBENIUS, Amitabha Tripathi(2006)

\begin{align}
& \large [定理 1]　\\
&a_1, a_2,　\dots , a_k を互いに素な正の整数とする \\
&P = a_1 \times a_2 \times　\dots \times a_k \\
&A_i = P / a_i \quad (1 \le i \le k ) \\
&このとき　\\
&g(A_1 ,A_2 , \dots , A_k)=(k-1)P - (A_1 + A_2 + \dots + A_k)
\end{align}

この式だけだとちょっと分かりずらいので具体例で見てみます。

[例題] 6円, 10円, 15円のコインで表せない最大の金額を求めよ

これは[定理 1]の$a_1, a_2 , a_3 = 5,3,2 $の場合に当てはまるので。

\begin{align}
&P = 5 \times 3 \times 2 = 30 \\
&A_1, A_2 , A_3 = 6,10,15\\
&g(6,10,15) = (3-1) \times 30 - (6+10+15) = 29
\end{align}

同様にしてプログラムで$6x+10y+15z$で表せない数をリストすると最大値は29となることが確認できました。

from itertools import product
a,b,c = 6,10,15
nall = set([n for n in range(101)])   # set of non-negative integers up to 100
lc =  set(sorted([a*x+b*y+c*z for x, y, z in product(range(6),repeat=3)]))
print(nall-lc)
# {1, 2, 3, 4, 5, 7, 8, 9, 11, 13, 14, 17, 19, 23, 29}

この考え方は Euler Project: Problem 278を解くのに役に立ちます。

（開発環境：Google Colab）