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

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

【１】ｎ＝３の場合の両替問題

　１ドルを２５セント，１０セント，５セントを用いて両替する方法を考える．

　　２５ｑ＋１０ｄ＋５ｎ＝１００

すべてをリストアップすると（少しの労力で）２９通りあること求められる．

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

　　２５ｑ＋１０ｄ＋５ｎ＝１００Ｄ

　　５ｑ＋２ｄ＋ｎ＝２０Ｄ

に対しては，十分な見通しが立たない．

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

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

　３点（０，０），（ａ，０），（０，ｂ）を頂点とする格子直角三角形内のの格子点の個数は，

　　Ｌ＝｛（ａ＋１）（ｂ＋１）＋ｇｃｄ（ａ，ｂ）＋１｝／２

となる．

　３点（０，０），（Ｎａ，０），（０，Ｎｂ）を頂点とする格子直角三角形内のの格子点の個数は，

　　ＬN＝（ａｂ／２）Ｎ^2＋（ａ＋ｂ＋ｇｃｄ（ａ，ｂ）｝／２Ｎ＋１

となる．

　　５ｑ＋２ｄ＋ｎ＝２０Ｄ

のｎを無視し，不等式

　　５ｑ＋２ｄ≦２０Ｄ

を満たす組（ｑ，ｄ）を調べればよい．

　ａ＝４Ｄ，ｂ＝１０Ｄとして，前述の公式を適用すれば，ｇｃｄ（ａ，ｂ）＝２Ｄより，

　　Ｌ＝２０Ｄ^2＋８Ｄ＋１

が得られる．１ドルを２５セント，１０セント，５セントを用いて両替する方法は２９通りあるというわけである．

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

　　Ｂ＝１６Ｄ

　　Ｉ＝Ｌ−Ｂ＝２０Ｄ^2−８Ｄ＋１

１ドルを２５セント，１０セント，５セントをそれぞれ少なくとも１つは用いて両替する方法は１３通りあるというわけである．

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

【３】ｎ＝３の場合の両替問題（その２）

　３種類の硬貨ｄ1，ｄ2，１を用いてｄ1ｄ2Ｎのお金を両替する方法は

　　（ｄ1ｄ2）／２・Ｎ^2＋｛（ｄ1＋１）（ｄ2＋１）＋ｇｃｄ（ｄ1，ｄ2）＋１｝／２・Ｎ＋１

通りある．

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