切手問題

切手問題とは、ある枚数の切手で作れない最小の金額（郵便料金）を求める数学の問題である。限られたスペース（封筒の面積）に切手を組み合わせて郵便料金を払う事ができるかを問う。

例えば、封筒は3枚の切手しか貼れず、使用可能な切手の額面が1円、2円、5円、20円の場合、12円までの金額は4 = 2 + 2、8 = 5 + 2 + 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