切手問題

切手問題とは、ある枚数の切手で作れない最小の金額（郵便料金）を求める数学の問題である。封筒の面積の制約上、貼ることのできる切手の枚数が限られているとする。このとき、数種類の額面の切手を組み合わせて構成できない最小の郵便料金を問うものである。

例えば、封筒には3枚の切手しか貼ることができないとする。使用可能な切手の額面が1円、2円、5円、15円の場合、12円までの金額は3枚までの切手で構成できる（例えば、4=2+2、8=5+2+1、11=5+5+1）。しかし、13円を構成するには少なくとも4枚の切手が必要となるため、13が解となる。

数学的な定義

数学的には、問題は次のように定式化される。

整数 m と正の整数の集合 V が与えられたとき、k ≤ m なる k 個の要素の和 v₁ + v₂ + ··· + v_k で表せない最小の整数 z を求めよ。

特殊な場合

n 種類、2枚の切手での解

n種類を適切に選ぶと、2枚の切手での解は最大で

2, 4, 8, 12, 16, 20, 26, 32, 40, 46, 54, 64, 72, 80, 92, 104, 116, 128, 140, 152, 164, 180, 196, 212,... (オンライン整数列大辞典の数列 A001212)

となる。

例えば、順に

${\begin{array}{ll}\{1\}&\to 1,1+1\\\{1,3\}&\to 1,1+1,3,3+1\\\{1,3,4\}&\to 1,1+1,3,4,4+1,3+3,4+3,4+4\\\{1,3,5,6\}&\to 1,1+1,3,3+1,5,6,6+1,5+3,6+3,5+5,6+5,6+6\end{array}}$

となる。

2 種類、h 枚の切手での解

2 種類を適切に選ぶと、h枚の切手での解は最大で

2, 4, 7, 10, 14, 18, 23, 28, 34, 40, 47, 54, 62, 70, 79, 88, 98, 108, 119, 130, 142, 154, 167, 180,... (オンライン整数列大辞典の数列 A014616)

となる。

例えば、順に

${\begin{array}{ll}\{1,2\}&\to 1,2\\\{1,3\}&\to 1,1+1,3,3+1\\\{1,3\}&\to 1,1+1,3,3+1,3+1+1,3+3,3+3+1\\\{1,4\}&\to 1,1+1,1+1+1,4,4+1,4+1+1,4+1+1+1,4+4,4+4+1,4+4+1+1\end{array}}$

となり、一般に$\{1,\lfloor (h+4)/2\rfloor \}$の切手を用意することで最大化でき、その解は

$\left\lfloor {\frac {1}{4}}(h^{2}+6h+1)\right\rfloor$

と表せる。

3 種類、h 枚の切手での解

3種類を適切に選ぶと、 h 枚の切手での解は最大で

3, 8, 15, 26, 35, 52, 69, 89, 112, 146, 172, 212, 259, 302, 354, 418, 476, 548, 633, 714, 805, 902, 1012, 1127, 1254, 1382,... (オンライン整数列大辞典の数列 A001208)

となる。

n ≥ 20 のとき

$\beta =\left\lfloor {\frac {4h+4}{9}}\right\rfloor +2,\gamma =\left\lfloor {\frac {2}{9}}h\right\rfloor +2$

とおくと

$a_{1}=1,a_{2}=2\beta -\gamma +1,a_{3}=\gamma a_{2}-\beta$

が h 枚の切手での最大の解を与え、その最大の解は

$(h+4-\beta -\gamma )a_{3}+(\gamma -2)a_{2}+(\beta -2)a_{1}={\frac {4}{81}}h^{3}+{\frac {2}{3}}h^{2}+Ah+B,$

ここで A, B は

$(A,B)={\begin{cases}\left({\frac {22}{9}},0\right)&(n\equiv 0{\pmod {9}}),\\\left({\frac {68}{27}},{\frac {62}{81}}\right)&(n\equiv 1{\pmod {9}}),\\\left({\frac {71}{27}},-{\frac {26}{81}}\right)&(n\equiv 2{\pmod {9}}),\\\left({\frac {23}{9}},0\right)&(n\equiv 3{\pmod {9}}),\\\left({\frac {68}{9}},-{\frac {154}{81}}\right)&(n\equiv 4{\pmod {9}}),\\\left({\frac {68}{27}},{\frac {46}{81}}\right)&(n\equiv 5{\pmod {9}}),\\\left({\frac {23}{9}},-1\right)&(n\equiv 6{\pmod {9}}),\\\left({\frac {71}{27}},-{\frac {1}{81}}\right)&(n\equiv 7{\pmod {9}}),\\\left({\frac {68}{27}},-{\frac {170}{81}}\right)&(n\equiv 8{\pmod {9}})\end{cases}}$

となる 。

計算複雑性

この問題は、 総当たりまたはバックトラッキングで |V|^m の定数倍時間で解くことができる。ここで |V| は使用できる切手の額面の種類の数とする。したがって、封筒の容量 m が定数である場合、多項式時間で解ける問題である。容量 m が任意の場合、問題はNP困難である。

関連項目

• フロベニウスの硬貨交換問題 切手の枚数に制限がない場合に相当
• ナップサック問題
• 部分和問題

外部リンク

• Lunnon, W. F. (1969年). “A postage stamp problem”. Comput. J. 12 (4): pp. 377-380. doi:10.1093/comjnl/12.4.377 
• Alter, R.; Barnett, J. A. (1980). “A postage stamp problem”. Amer. Math. Monthly 87: 206–210. doi:10.2307/2321610. 
• Graham, R. L.; Sloane, N. J. A. (1980). “On additive bases and harmonious graphs”. SIAM J. Algebr. Discrete Methods 1: 382–404. doi:10.1137/0601045. 
• Kohonen, J.; Corander, J. (2013). "Addition chains meet postage stamps: reducing the number of multiplications". arXiv:1310.7090。
• Kohonen, Jukka (2014). "A meet-in-the-middle algorithm for finding extremal restricted additive 2-bases". arXiv:1403.5945。
• Weisstein, Eric W. "Postage Stamp Problem". mathworld.wolfram.com (英語).
• オンライン整数列大辞典の数列 A001212