从邮票问题谈起梳理常见结论与典型问题

从邮票问题谈起

近年来，国内外以邮票问题为背景的竞赛题时有出现，这些题目难度跨度大，既可以是简单的选择题，也可以是TST级别的难题。本文将介绍邮票问题用到的常见结论，同时也梳理了一些典型的问题供大家思考。

邮票问题源于寄信贴邮票这一场景，假设邮局有面值为a1,a2,…an，货币单位的n类邮票，现需要寄一封邮费为N个货币单位的信件。

我们很自然地会产生这样两个问题：一是能否恰好用这n类邮票凑出邮费，二是如果能凑出邮费，贴邮票的组合方式有多少种？

对于第一个问题，我们可以转换为线性不定方程，而第二个问题通常可以采用生成函数解决。对于任意的a1,a2,…an，以及N，我们很难得到两个问题的解析表达式，基于此，我们从特定形式入手，给出一些已经得到解决的特殊情形，为表述方便，下文均采用不定方程的形式描述邮票问题。

01、结论1

每月一讲：从邮票问题谈起，梳理常见结论与典型问题

结论1的证明利用Bezout定理以及线性不定方程理论即可，这里不再赘述。一般地，若正整数a1,a2,…an，满足（a1,a2,…an，）=1，则存在最大的正整数m使得不定方程没有非负整数解。然而当n≥3时，我们目前仍无法得到m的解析表达式。

此外，结论1表明只有每月一讲：从邮票问题谈起，梳理常见结论与典型问题时，方程才可能没有非负整数解，那么究竟有多少个非负整数使得方程没有整数解呢？

事实上，我们可以证明在区间每月一讲：从邮票问题谈起，梳理常见结论与典型问题中恰有个c不能表示为的形式，这里x,y为非负整数。这个结果的证明只要注意到n和两者恰有一个能被上述形式表出即可。

结论1回答了只有两种面值的邮票时，能否恰好凑出特定邮费的分界线，该结论在AMC/AIME中也经常考到。

例如2019年AIME-II-P14就是将这个结论变形后得到的，题目是这样的：

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.

问题的详细解答可自行查阅，这里仅给一个思路。若选手考试时只知道结论1，但又不知道三元及以上的形式通常没有解析解，而寄望于将结论1推广到三元实属缘木求鱼，难以找到突破点。

事实上，这个题目需要先考虑5和n能表出的正整数，以及5和n+1能表出的正整数，在此基础上注意到96能用5,n,n+1表出，而91则不能，这说明96是仅靠n和n+1表出的（如果96的表出包含了5,则去掉一个就能表出91，矛盾！）。

除了在数学竞赛领域，在信息（编程）竞赛，结论1也被作为过赛题。2016年我国NOIP提高组的第一题就是直接考察了结论1，不过笔者认为直接将数论的已知结论作为编程类竞赛题略有不妥，因为这样过于注重数学知识但缺少了编程技巧的考核，与信息竞赛初衷有所违背。

结论2

每月一讲：从邮票问题谈起，梳理常见结论与典型问题

结论2给出了其中一种特定型式n元问题的解析解。

02、上述均是讨论邮票问题的存在性情况，下面接着讨论邮票的组合方式，即不定方程非负整数解个数。

对于某些给定具体数值的问题，我们可以通过枚举、构造模型等方式解决。然而，对于任意一组互素（a1,a2,…an，）以及正整数m，方程每月一讲：从邮票问题谈起，梳理常见结论与典型问题的非负整数解组数通常也是无法得到闭式（closed form）表达的，而与数论有关的很多问题，我们更关注的是一个整体趋势而非具体表达，例如我们已经通过研究得到素数在自然中的分布密度，但却无法得到素数列的通项公式。