郵票問題(postage stamp problem)是一個尚未完全解決的著名組合問題。
基本介紹
- 中文名：郵票問題
- 外文名：postage stamp problem
1937年，羅爾巴丈 (Rohrbach , H.)提出了一個有關郵票設計的課題 郵票有k種不同整數幣值a az,... }ak，組成一個凳 合Ak - l a l f a p , "' , ak，其中a，為正整數(i- 1 f 2 .. ,k)，且滿足1一a} G a2 G…＜ak.但信封上最多 可貼h張郵票，於是一個信封上的總郵資 N=a,.x,+azxz+…+ak}k， 式中二((z=1,2, ”””,k)為非負整數，且滿足二l+二 +…+二*＜h，那么不滿足上述要求的最小正整那 N是多少?這個最小正整數記為N(h,Ak).由此知 信封總郵資從1開始可連續取到的種數是 n(h,Ak)=N(h,Ak)一1， 稱之為A*的h值域((h range)，而A*稱為h階加性 基，簡稱h基.由此產生了兩類不同的郵票問題: 1.局部問題.給定h和一個基Ak，求n(h,Ak)`, 對於k一2，已求得n(h,A2)一((h+3一az}az一2 式中h妻az-2,az}a,=1.對於k=3,羅德塞邦 ＜ Rodseth , b)找到了基於連分數算法的一般方法. 塞爾默(Selmer, E. S.)據此導出了一些確定的么 式，解決了對於幾乎所有的A3的n(h,A3)計算.劉 於k}3的局部問題，尚在研究中. 2.總體問題.給定h和k，求maxn (h , Ak )，其牛 最大值取在一切可能的基A*上，這個最大值簡記大 n＜h,k). 1)給定h值.主要成果是h=2的情形。
