■両替問題(その4)

【1】n=3の場合の両替問題

 1ドルを25セント,10セント,5セントを用いて両替する方法を考える.

  25q+10d+5n=100

すべてをリストアップすると(少しの労力で)29通りあること求められる.

 しかし,Dドルを両替するという一般の問題

  25q+10d+5n=100D

  5q+2d+n=20D

に対しては,十分な見通しが立たない.

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

【2】格子直角三角形の格子数

 3点(0,0),(a,0),(0,b)を頂点とする格子直角三角形内のの格子点の個数は,

  L={(a+1)(b+1)+gcd(a,b)+1}/2

となる.

 3点(0,0),(Na,0),(0,Nb)を頂点とする格子直角三角形内のの格子点の個数は,

  LN=(ab/2)N^2+(a+b+gcd(a,b)}/2N+1

となる.

  5q+2d+n=20D

のnを無視し,不等式

  5q+2d≦20D

を満たす組(q,d)を調べればよい.

 a=4D,b=10Dとして,前述の公式を適用すれば,gcd(a,b)=2Dより,

  L=20D^2+8D+1

が得られる.1ドルを25セント,10セント,5セントを用いて両替する方法は29通りあるというわけである.

 また,これらの硬貨をそれぞれ少なくとも1つは使う両替の方法は,三角形内部の格子点に対応する.三角形の境界上に16D個の格子点があることより,は

  B=16D

  I=L−B=20D^2−8D+1

1ドルを25セント,10セント,5セントをそれぞれ少なくとも1つは用いて両替する方法は13通りあるというわけである.

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

【3】n=3の場合の両替問題(その2)

 3種類の硬貨d1,d2,1を用いてd1d2Nのお金を両替する方法は

  (d1d2)/2・N^2+{(d1+1)(d2+1)+gcd(d1,d2)+1}/2・N+1

通りある.

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