切手問題

出典: フリー百科事典『ウィキペディア(Wikipedia)』
ナビゲーションに移動 検索に移動

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

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

数学的な定義[編集]

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

整数 m と正の整数の集合 V が与えられたとき、km なる k 個の要素の和 v1 + v2 + ··· + vk で表せない最小の整数 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)

となる。

例えば、順に

となる。

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)

となる。

例えば、順に

となり、一般にの切手を用意することで最大化でき、その解は

と表せる[2]

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 のとき

とおくと

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

ここで A, B

となる [3][4][5]


計算複雑性[編集]

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

関連項目[編集]

参考文献[編集]

  1. ^ a b Jeffrey Shallit (2001), The computational complexity of the local postage stamp problem. SIGACT News 33 (1) (March 2002), 90-94. Accessed on 2009-12-30.
  2. ^ Stöhr, Alfred (1955年). “Gelöste und ungelöste Fragen über Basen der natürlichen Zahlenreihe. I”. J. reine angew Math. 194: pp. 40-65. doi:10.1515/crll.1955.194.40. https://eudml.org/doc/150281 
  3. ^ Mossige, Svein (1981). “Algorithms for Computing the h-Range of the Postage Stamp Problem”. Math. Comp. 36 (154): 575-582. doi:10.1090/S0025-5718-1981-0606515-1. MR0606515. 
  4. ^ Hofmeister, Gerd (1983). “Die dreielementigen Extremalbasen”. J. reine angew Math. 339: 207-214. doi:10.1515/crll.1983.339.207. MR0686707. https://eudml.org/doc/152515. 
  5. ^ Challis, M. F. (1993). “Two new techniques for computing extremal h-bases Ak”. Comput. J. 36 (2): 117–126. doi:10.1093/comjnl/36.2.117. 

外部リンク[編集]