フロベニウスの硬貨交換問題
フロベニウスの硬貨交換問題(フロベニウスのこうかこうかんもんだい)とは、指定された種類の硬貨だけではぴったり払えない最大の金額を求める数学の問題である。フロベニウスの問題、シルベスターの切手問題とも呼ばれる。数学者フェルディナント・ゲオルク・フロベニウスに因んで名付けられた。例えば、3円と5円の硬貨だけでは作れない最大の金額は7円である。コインの種類の組み合わせに対するこの問題の解はフロベニウス数と呼ばれる。フロベニウス数が存在するのは、硬貨の額面が互いに素のときに限られる。
硬貨が a円と b円の2種類だけの場合は、フロベニウス数の公式が存在し、ab − a − b (= (a − 1)(b − 1) − 1) である。硬貨が3種類以上の場合の公式は未解決問題である。しかし、任意の種類の硬貨に対して、(硬貨の種類の数の「対数」に対して)多項式時間でフロベニウス数を計算するアルゴリズムが存在する。硬貨の種類に対して多項式時間で解けるアルゴリズムは見つかっておらず、硬貨の種類に制限を設けない一般的な問題はNP困難である。