［Ｑ］ａ円玉とｂ円玉を用いてｎ円支払えるための条件を求めよ．

という問題では，

［Ａ］ｎはｄ＝ｇｃｄ（ａ，ｂ）の倍数，ｘ，ｙは非負整数．したがって，ｘ，ｙが存在するための条件は

　　ｘ＝ｘ0−ｂｔ／ｄ≧０，ｙ＝ｙ0＋ｃｔ／ｄ≧０

というｔに関する連立不等式を解けばよい．結局，区間

　　［−ｙ0ｄ／ａ，−ｘ0ｄ／ｂ］

が整数を含めばよいことになる．

　５と８は互いに素であるが，８と１２は互いに素ではない．互いに素な２つの整数ａ1，ａ2が与えられたとき，非負整数が存在して

　　ｍ1ａ1＋ｍ2ａ2＝ｎ

が成り立つことは，硬貨の言葉に置き換えるとａ1円玉とａ2円玉を用いてｎ円が支払えることを意味する．

　どの額が支払えるか，支払えない最高額はいくらかという問題が考えられるところである．この問題はフロベニウスの硬貨交換問題とも呼ばれる．

　　［参］ＴＳマイケル「離散数学パズルの冒険」青土社

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【１】フロベニウス数

［Ｑ］５セント切手と８セント切手を用いて２７セント支払えるための条件を求めよ．

［Ａ］実現不可能．

　２７よりも小さい１４の数に対しては実現可能（０，５，８，１０，１３，１５，１６，１８，２０，２１，２３，２４，２５，２６），１４の数に対しては実現不可能（１，２，３，４，６，７，９．１１．１２，１４，１７，１９，２２，２７）．

　２７よりも大きければ恒に実現可能である．なぜならば５つの連続した数２８，２９，３０，３１，３２がいったん生じてしまえば，５の倍数を加えることで３２より大きな数はすべて表すことができるからである．

　支払えない最高額をフロベニウス数と呼び，ｇ（ａ1，ａ2）で表される．

　　ｇ（ａ1，ａ2）＝ａ1ａ2−ａ1−ａ2＝（ａ1−１）（ａ2−１）−１

で与えられ，１と（ａ1−１）（ａ2−１）の間にある整数のちょうど半数が表現可能である．

　たとえば，ａ1＝５，ａ2＝８の場合，ｇ（ａ1，ａ2）＝２７で，表現不可能な整数の数は（ａ1−１）（ａ2−１）／２＝１４となる．ａ1＝４，ａ2＝７の場合，ｇ（ａ1，ａ2）＝１７で，表現不可能な整数の数は（ａ1−１）（ａ2−１）／２＝９となる．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【２】シルヴェスターの定理

　ａ1とａ2が互いに素ならば，ａ1ａ2よりも小さい実現不可能な数の個数は

　　（ａ1−１）（ａ2−１）／２

である．

　たとえな，ｎ＝２，ａ1＝５，ａ2＝８のとき，母関数

　　Ｐ（ｚ）＝（１＋ｚ^5＋ｚ^10＋・・・＋ｚ^40）（１＋ｚ^8＋ｚ^16＋・・・＋ｚ^40）

＝１＋ｚ^5＋ｚ^8＋・・・＋２ｚ^40＋・・・ｚ^42＋ｚ^75＋ｚ^80

を調べると，展開式の項はｚ^nとｚ^80-で対称で，中央項はｚ^40であることから，シルヴェスターの定理が証明される．

　シルヴェスターは３つ以上の切手が利用できるとき何が起こるかを調べた．ｎ＝２の場合のシルヴェスターの定理の証明は母関数

　　ｆ（ｚ）＝１／（１−ｚ^a1）（１−ｚ^a2）ｚ^n

の定数項と関連しているが，実は硬貨が３枚以上になると格段複雑になり，ｎ元１次形式に対する公式はほとんど成功しなかった．

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

　ｇｃｄ（ａ1，ａ2，・・・，ａv）＝１すなわちａ1，ａ2，・・・，ａvが互いの素のとき

　　ｍ1ａ1＋ｍ2ａ2＋・・・＋ｍvａv＝ｎ

が実現不可能な最大の数ｎをみつけよ．

［Ａ］ｎ＝３の場合は，セルマー・ベイヤーによって明示的な形で解決されたが，ｎ≧４の場合には一般的な公式は知られていない．

　ａ1＜ａ2＜・・・＜ａvとすると，不等式

［１］交換できない最大の金額≦（ａ1−１）（ａv−１）−１

［２］交換不可能な金額の個数≧（ａ1−１）（ａv−１）／２

を満たす．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝