昔イギリスのマクドナルドで売られていたチキンマックナゲットは、9個パックと20個パックだった。
そこで作られ問題が、
「買うことができない最大の個数はいくつか？」
という問題だった。
すなわち、
「x,yを非負の整数とする。
9x+20yの形に表せない最大の数を求めよ。」
という問題になる。
【step1】
a,bは互いに素の自然数とし、
x,yを非負の整数とする。
ax+byの形で表せない最大の自然数Pについて考えてみよう。
【解】
0, a,2a,……,(b-1)aはbを法として合同でない
(bで割ったときの余りが異なる)
(∵)1≦i≦j≦bとする。
ia≡ja (mod b)
(j-i)a≡0 (mod b)
aとbは互いに素だから、j-i≡0 (mod b)
0≦j-i≦b-1より、j-i=0
ia≡ja (mod b)ならばi=j
対偶を考えると、
i≠jならばiaとjaはbを法として合同でない。
bを法とする剰余類を考える。
iaを含む剰余類をIとする。
Iの要素はia-kbの形で表される。
Iを次の2つのグループ①②に分けることができる。
①k≦0→ax+byの形に表せる
②k＞0→ax+byの形に表せない
(∵)
①(x,y)=(i,-k)で自明
②0≦i≦b-1, k＞0
ia-kb=ax+by
特殊解(i,-k)→一般解(bt+i,-at-k)
x=bt+i≧0→bt≧-i≧-(b-1)＞-b→t≧0
→y=-at-k≦-k＜0
よって、自然数(x,y)は存在しない
すなわち、
Iの要素でiaより小さいものは
ax+by (x,yは非負の整数)の形に表せない
iが最大、kが最小のとき、
ia-kbは最大になる。→i=b-1, k=1
P=(b-1)a-b=ab-a-bが表せない最大の数
【step2】
では
ax+by (x,yは非負の整数)の形で表せない数の個数Fを考えてみよう。
剰余類Iの中で、
ia-b,……,ia-kb＞0が表せない。
その個数kは、k＜(ia)/bだから、
Iの中には、[(ia)/b] (ガウス記号)個
よって、
F=Σ《i=1,…,b-1》[(ia)/b]
横b縦aの長方形と、原点と点(b,a)を結ぶ直線を考える。
直線の方程式は、y=(a/b)x
[(ia)/b]は、x=i上にある直線より下側の格子点の数である。
よって、Fは直線の下側にある直角三角形の内部にある格子点の等しい。
a,bは互いに素だから、直線上に格子点はない。二つ直角三角形の内部にある格子点は等しい。
長方形の内部にある格子点は(a-1)(b-1)で、三角形の内部にある格子点は
{(a-1)(b-1)}/2だから、
F={(a-1)(b-1)}/2
【step3 まとめ】
a,bは互いに素の自然数で、x,yを非負の整数とする。
ax+byの形に表せない自然数は
F={(a-1)(b-1)}/2個あり、
最大の数は、P=ab-a-bである。
また、表せない数はia-kbの形をしている。ただし、1≦i≦b-1, k＞0
【step4】
x,yを非負の整数とする。
9x+20yの形に表せない自然数は
F={(9-1)×(20-1)}/2=76個あり、
最大の数は、P=9×20-9-20=151
である。
i=15,k=2→ia-kb=15×9-2×20=95
9x+20y=95は、自然数(x,y)は存在しない
逆に
9x-20y=95は、自然数(x,y)は存在する
一次不定方程式が自然数解を持つ問題と関係がある。
【step5 参考】
フロベニウスの硬貨交換問題
指定された硬貨だけではぴったり払えない最大の金額を求める数学の問題である。フロベニウスの問題、シルベスターの切手問題とも呼ばれる。数学者フェルディナント・ゲオルク・フロベニウスにちなんで名付けられた。
ab-a-bは、ジェームス・ジョセフ・シルベスターが1882年に発見した。
①フェルディナント・ゲオルク・フロベニウス(Georg Ferdinand Frobenius)
(1849年10月26日 - 1917年8月3日)
ドイツの数学者。
②ジェームス・ジョセフ・シルベスター（James Joseph Sylvester)
(1814年9月3日 - 1897年3月15日)
イギリスの数学者。
(2021/8/18)
