フロベニウスの硬貨交換問題
有名な特別な場合に、チキンマックナゲット数がある。この問題はHenri PicciottoがAnita Wahと共著で代数の教科書に書いたことで導入された。1980年代にPicciottoはマクドナルドで息子と食事をしながらこの問題を考え、ナプキン上で解決した。チキンマックナゲット数は、チキンマックナゲットのセットを購入することで揃えられるチキンマックナゲットの総数である。ハッピーセットサイズのナゲットの導入前のイギリスでは、6, 9, 20個入りのナゲットが提供されていた。
シューアの定理より、6, 9, 20は(6と9は公約数3を持つが)互いに素であるため、十分大きい整数はこれら3つの線形結合で表せる。したがって、最大の非チキンマックナゲット数(チキンマックナゲット数ではない整数)が存在する。すなわち、次の例外を除いてすべての正の整数はチキンマックナゲット数であるといえる。
1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37, 43
(オンライン整数列大辞典の数列 A065003)
上記の表より、最大の非チキンマックナゲット数は43である。43より大きい任意の整数がチキンマックナゲット数であることは、以下の自然数の分割のいずれかに6を適当な回数だけ足し合わせることで確かめられる。
」という形式で述べた。
この公式は以下のように証明できる。
m ≥ ( a 1 − 1 ) ( a 2 − 1 ) {\displaystyle m\geq (a_{1}-1)(a_{2}-1)} を表現したいとする。a1, a2 の最大公約数は1であるため、 σ = 0 , 1 , ⋯ , a 1 − 1 {\displaystyle \sigma =0,1,\cdots ,a_{1}-1} に対して m − σ a 2 {\displaystyle m-\sigma a_{2}} はすべて a1 を法として互いに異なる。したがって、 m = ρ a 1 + σ a 2 {\displaystyle m=\rho a_{1}+\sigma a_{2}} となるようなただ一つの σ と、非負整数 ρ が存在する。ρ が非負であるのは、
ρ a 1 = m − σ a 2 ≥ ( a 1 − 1 ) ( a 2 − 1 ) − ( a 1 − 1 ) a 2 = − a 1 + 1 {\displaystyle \rho a_{1}=m-\sigma a_{2}\geq (a_{1}-1)(a_{2}-1)-(a_{1}-1)a_{2}=-a_{1}+1}
から分かる。