■シルベスターの公式・フロベニウス数(その8)

[Q]a円玉とb円玉を用いてn円支払えるための条件を求めよ.

という問題では,

[A]nはd=gcd(a,b)の倍数,x,yは非負整数.したがって,x,yが存在するための条件は

  x=x0−bt/d≧0,y=y0+ct/d≧0

というtに関する連立不等式を解けばよい.結局,区間

  [−y0d/a,−x0d/b]

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

 5と8は互いに素であるが,8と12は互いに素ではない.互いに素な2つの整数a1,a2が与えられたとき,非負整数が存在して

  m1a1+m2a2=n

が成り立つことは,硬貨の言葉に置き換えるとa1円玉とa2円玉を用いてn円が支払えることを意味する.

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

  [参]TSマイケル「離散数学パズルの冒険」青土社

===================================

【1】フロベニウス数

[Q]5セント切手と8セント切手を用いて27セント支払えるための条件を求めよ.

[A]実現不可能.

 27よりも小さい14の数に対しては実現可能(0,5,8,10,13,15,16,18,20,21,23,24,25,26),14の数に対しては実現不可能(1,2,3,4,6,7,9.11.12,14,17,19,22,27).

 27よりも大きければ恒に実現可能である.なぜならば5つの連続した数28,29,30,31,32がいったん生じてしまえば,5の倍数を加えることで32より大きな数はすべて表すことができるからである.

 支払えない最高額をフロベニウス数と呼び,g(a1,a2)で表される.

  g(a1,a2)=a1a2−a1−a2=(a1−1)(a2−1)−1

で与えられ,1と(a1−1)(a2−1)の間にある整数のちょうど半数が表現可能である.

 たとえば,a1=5,a2=8の場合,g(a1,a2)=27で,表現不可能な整数の数は(a1−1)(a2−1)/2=14となる.a1=4,a2=7の場合,g(a1,a2)=17で,表現不可能な整数の数は(a1−1)(a2−1)/2=9となる.

===================================

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

 a1とa2が互いに素ならば,a1a2よりも小さい実現不可能な数の個数は

  (a1−1)(a2−1)/2

である.

 たとえな,n=2,a1=5,a2=8のとき,母関数

  P(z)=(1+z^5+z^10+・・・+z^40)(1+z^8+z^16+・・・+z^40)

=1+z^5+z^8+・・・+2z^40+・・・z^42+z^75+z^80

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

 シルヴェスターは3つ以上の切手が利用できるとき何が起こるかを調べた.n=2の場合のシルヴェスターの定理の証明は母関数

  f(z)=1/(1−z^a1)(1−z^a2)z^n

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

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

 gcd(a1,a2,・・・,av)=1すなわちa1,a2,・・・,avが互いの素のとき

  m1a1+m2a2+・・・+mvav=n

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

[A]n=3の場合は,セルマー・ベイヤーによって明示的な形で解決されたが,n≧4の場合には一般的な公式は知られていない.

 a1<a2<・・・<avとすると,不等式

[1]交換できない最大の金額≦(a1−1)(av−1)−1

[2]交換不可能な金額の個数≧(a1−1)(av−1)/2

を満たす.

===================================