切手問題
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)
となる。
例えば、順に
{ 1 } → 1 , 1 + 1 { 1 , 3 } → 1 , 1 + 1 , 3 , 3 + 1 { 1 , 3 , 4 } → 1 , 1 + 1 , 3 , 4 , 4 + 1 , 3 + 3 , 4 + 3 , 4 + 4 { 1 , 3 , 5 , 6 } → 1 , 1 + 1 , 3 , 3 + 1 , 5 , 6 , 6 + 1 , 5 + 3 , 6 + 3 , 5 + 5 , 6 + 5 , 6 + 6 {\displaystyle {\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}}}
となる。
となり、一般に { 1 , ⌊ ( h + 4 ) / 2 ⌋ } {\displaystyle \{1,\lfloor (h+4)/2\rfloor \}} の切手を用意することで最大化でき、その解は
⌊ 1 4 ( h 2 + 6 h + 1 ) ⌋ {\displaystyle \left\lfloor {\frac {1}{4}}(h^{2}+6h+1)\right\rfloor }
と表せる。
切手問題とは、ある枚数の切手で作れない最小の金額(郵便料金)を求める数学の問題である。封筒の面積の制約上、貼ることのできる切手の枚数が限られているとする。このとき、数種類の額面の切手を組み合わせて構成できない最小の郵便料金を問うものである。
例えば、封筒には3枚の切手しか貼ることができないとする。使用可能な切手の額面が1円、2円、5円、15円の場合、12円までの金額は3枚までの切手で構成できる(例えば、4=2+2、8=5+2+1、11=5+5+1)。しかし、13円を構成するには少なくとも4枚の切手が必要となるため、13が解となる。