從郵票問題談起梳理常見結論與典型問題

從(cong) 郵票問題談起

近年來，國內(nei) 外以郵票問題為(wei) 背景的競賽題時有出現，這些題目難度跨度大，既可以是簡單的選擇題，也可以是TST級別的難題。本文將介紹郵票問題用到的常見結論，同時也梳理了一些典型的問題供大家思考。

郵票問題源於(yu) 寄信貼郵票這一場景，假設郵局有麵值為(wei) a1,a2,…an，貨幣單位的n類郵票，現需要寄一封郵費為(wei) N個(ge) 貨幣單位的信件。

我們(men) 很自然地會(hui) 產(chan) 生這樣兩(liang) 個(ge) 問題：一是能否恰好用這n類郵票湊出郵費，二是如果能湊出郵費，貼郵票的組合方式有多少種？

對於(yu) 第一個(ge) 問題，我們(men) 可以轉換為(wei) 線性不定方程，而第二個(ge) 問題通常可以采用生成函數解決(jue) 。對於(yu) 任意的a1,a2,…an，以及N，我們(men) 很難得到兩(liang) 個(ge) 問題的解析表達式，基於(yu) 此，我們(men) 從(cong) 特定形式入手，給出一些已經得到解決(jue) 的特殊情形，為(wei) 表述方便，下文均采用不定方程的形式描述郵票問題。

01、結論1

每月一講：從(cong) 郵票問題談起，梳理常見結論與(yu) 典型問題

結論1的證明利用Bezout定理以及線性不定方程理論即可，這裏不再贅述。一般地，若正整數a1,a2,…an，滿足（a1,a2,…an，）=1，則存在最大的正整數m使得不定方程沒有非負整數解。然而當n≥3時，我們(men) 目前仍無法得到m的解析表達式。

此外，結論1表明隻有每月一講：從(cong) 郵票問題談起，梳理常見結論與(yu) 典型問題時，方程才可能沒有非負整數解，那麽(me) 究竟有多少個(ge) 非負整數使得方程沒有整數解呢？

事實上，我們(men) 可以證明在區間每月一講：從(cong) 郵票問題談起，梳理常見結論與(yu) 典型問題中恰有個(ge) c不能表示為(wei) 的形式，這裏x,y為(wei) 非負整數。這個(ge) 結果的證明隻要注意到n和兩(liang) 者恰有一個(ge) 能被上述形式表出即可。

結論1回答了隻有兩(liang) 種麵值的郵票時，能否恰好湊出特定郵費的分界線，該結論在AMC/AIME中也經常考到。

例如2019年AIME-II-P14就是將這個(ge) 結論變形後得到的，題目是這樣的：

Find the sum of all positive integers n such that, given an unlimited supply of stamps of denominations 5, n, and n+1 cents, 91 cents is the greatest postage that cannot be formed.

問題的詳細解答可自行查閱，這裏僅(jin) 給一個(ge) 思路。若選手考試時隻知道結論1，但又不知道三元及以上的形式通常沒有解析解，而寄望於(yu) 將結論1推廣到三元實屬緣木求魚，難以找到突破點。

事實上，這個(ge) 題目需要先考慮5和n能表出的正整數，以及5和n+1能表出的正整數，在此基礎上注意到96能用5,n,n+1表出，而91則不能，這說明96是僅(jin) 靠n和n+1表出的（如果96的表出包含了5,則去掉一個(ge) 就能表出91，矛盾！）。

除了在數學競賽領域，在信息（編程）競賽，結論1也被作為(wei) 過賽題。2016年我國NOIP提高組的第一題就是直接考察了結論1，不過筆者認為(wei) 直接將數論的已知結論作為(wei) 編程類競賽題略有不妥，因為(wei) 這樣過於(yu) 注重數學知識但缺少了編程技巧的考核，與(yu) 信息競賽初衷有所違背。

結論2

每月一講：從(cong) 郵票問題談起，梳理常見結論與(yu) 典型問題

結論2給出了其中一種特定型式n元問題的解析解。

02、上述均是討論郵票問題的存在性情況，下麵接著討論郵票的組合方式，即不定方程非負整數解個(ge) 數。

對於(yu) 某些給定具體(ti) 數值的問題，我們(men) 可以通過枚舉(ju) 、構造模型等方式解決(jue) 。然而，對於(yu) 任意一組互素（a1,a2,…an，）以及正整數m，方程每月一講：從(cong) 郵票問題談起，梳理常見結論與(yu) 典型問題的非負整數解組數通常也是無法得到閉式（closed form）表達的，而與(yu) 數論有關(guan) 的很多問題，我們(men) 更關(guan) 注的是一個(ge) 整體(ti) 趨勢而非具體(ti) 表達，例如我們(men) 已經通過研究得到素數在自然中的分布密度，但卻無法得到素數列的通項公式。