Kvant Math Problem 2830
Let $S$ be the set of amounts obtainable with at most $1000$ coins of denominations $a$ and $b$.
Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 9m59s
Source on kvant.digital
Problem
Coins of denominations $a$ and $b$ doubloons are in circulation, where $a$ and $b$ are given relatively prime positive integers, and $a\lt b\lt100$. A nonnegative integer $n$ is called fortunate if a sum of $n$ doubloons can be formed using at most 1000 coins. Find the number of fortunate integers.
Folklore
Exploration
Let $S$ be the set of amounts obtainable with at most $1000$ coins of denominations $a$ and $b$.
If we use $x$ coins of value $a$ and $y$ coins of value $b$, then
$$n=ax+by, \qquad x,y\ge0, \qquad x+y\le1000.$$
Thus
$$S={ax+by:\ x,y\ge0,\ x+y\le1000}.$$
The question asks for the cardinality of $S$.
A first guess is that different pairs $(x,y)$ might frequently give the same sum. Since $\gcd(a,b)=1$, equality
$$ax+by=ax'+by'$$
implies
$$a(x-x')=b(y'-y).$$
Because $a$ and $b$ are coprime,
$$x-x'=bt,\qquad y'-y=at$$
for some integer $t$. Hence
$$(x'+y')-(x+y)=(b-a)t.$$
Since $b>a$, moving from one representation to another changes the total number of coins by a positive multiple of $b-a$.
This suggests looking at representations with a fixed total number of coins. If $x+y=k$, then
$$ax+by=a(k-y)+by=ak+(b-a)y.$$
For fixed $k$, the obtainable sums form an arithmetic progression
$$ak,\ ak+(b-a),\ldots,bk.$$
Different values of $k$ may overlap. The crucial issue is to understand exactly how.
Try a small example: $a=2$, $b=3$.
For $k=1$ we get ${2,3}$.
For $k=2$ we get ${4,5,6}$.
For $k=3$ we get ${6,7,8,9}$.
The overlap is the single value $6$.
The equation $ak+(b-a)y=ak'+(b-a)y'$ becomes
$$a(k-k')=(b-a)(y'-y).$$
Since $\gcd(a,b-a)=1$, equality is governed by multiples of $b-a$ in the coin count. This points toward residue classes modulo $b-a$.
The step most likely to hide an error is counting overlaps between different values of $k$. The structure of these overlaps must be described exactly, not approximately.
Problem Understanding
We must count all nonnegative integers that can be represented as
$$ax+by$$
with nonnegative integers $x,y$ satisfying $x+y\le1000$, where $a$ and $b$ are fixed coprime positive integers and
$$a<b<100.$$
This is a Type A problem. We must determine precisely the set of fortunate integers and count its elements.
The core difficulty is that many pairs $(x,y)$ can represent the same amount. The answer should depend only on $a$ and $b$, and the overlap pattern among the sets corresponding to different total coin counts must be counted exactly.
Proof Architecture
Lemma 1. For each $k\ge0$, the set of sums obtainable with exactly $k$ coins is
$$T_k={ak+(b-a)y:0\le y\le k}.$$
This follows by writing $x=k-y$.
Lemma 2. Two numbers from $T_k$ and $T_{k'}$ are equal if and only if $k\equiv k'\pmod{b-a}$.
This comes from the coprimality of $a$ and $b-a$.
Lemma 3. If $r\in{0,1,\dots,b-a-1}$, then
$$U_r=\bigcup_{m\ge0}T_{r+m(b-a)}$$
is an interval of an arithmetic progression with common difference $b-a$, and its cardinality can be computed explicitly.
Successive sets in the same residue class overlap in exactly one endpoint.
Lemma 4. The families $U_r$ are pairwise disjoint.
This is a reformulation of Lemma 2.
After computing $|U_r|$ and summing over all residue classes, we obtain the total number of fortunate integers.
The hardest direction is proving the exact overlap structure inside one residue class and deriving the correct count.
Solution
Let
$$d=b-a.$$
Since $\gcd(a,b)=1$, we also have
$$\gcd(a,d)=\gcd(a,b-a)=1.$$
For each integer $k\ge0$, let $T_k$ be the set of sums obtainable using exactly $k$ coins.
If $x+y=k$, then $x=k-y$, so
$$ax+by=a(k-y)+by=ak+dy.$$
Hence
$$T_k={ak+dy:0\le y\le k}.$$
Equivalently,
$$T_k={ak,,ak+d,,ak+2d,\ldots,bk}.$$
Its cardinality is
$$|T_k|=k+1.$$
We next determine when two such sets intersect.
Suppose
$$ak+dy=ak'+dy'$$
with $0\le y\le k$ and $0\le y'\le k'$.
Then
$$a(k-k')=d(y'-y).$$
Since $\gcd(a,d)=1$, there exists an integer $t$ such that
$$k-k'=dt, \qquad y'-y=at.$$
Thus $k\equiv k'\pmod d$.
Conversely, if $k-k'=dt$, then choosing $y'-y=at$ gives
$$ak+dy=ak'+dy'.$$
Therefore
$$T_k\cap T_{k'}\neq\varnothing \quad\Longleftrightarrow\quad k\equiv k' \pmod d.$$
It follows that sets corresponding to different residue classes modulo $d$ are disjoint.
Fix a residue class
$$r\in{0,1,\ldots,d-1}.$$
Write
$$k=r+md.$$
The largest such $k$ not exceeding $1000$ is
$$r+M_rd, \qquad M_r=\Bigl\lfloor\frac{1000-r}{d}\Bigr\rfloor .$$
Consider
$$U_r=\bigcup_{m=0}^{M_r}T_{r+md}.$$
Since different residue classes are disjoint, the total number of fortunate integers is
$$\sum_{r=0}^{d-1}|U_r|.$$
We now compute $|U_r|$.
For $k=r+md$,
$$T_k=[ak,bk]_d,$$
where $[u,v]_d$ denotes the arithmetic progression
$$u,u+d,u+2d,\ldots,v.$$
The next set in the same residue class is $T_{k+d}$, whose first element is
$$a(k+d)=ak+ad.$$
The last element of $T_k$ is
$$bk=ak+dk.$$
Their overlap consists of those progression points satisfying
$$ak+ad\le ak+dj\le ak+dk.$$
This is equivalent to
$$a\le j\le k.$$
Hence the overlap contains
$$k-a+1$$
points when $k\ge a$.
Since $d=b-a<100$ and $1000\ge a$, every transition relevant to the counting eventually has this form. More importantly, the union of consecutive sets in the same residue class remains a single arithmetic progression with step $d$.
Indeed, $T_r$ is such a progression. If the union up to $T_k$ is
$$[ar,bk]_d,$$
then
$$T_{k+d}=[a(k+d),b(k+d)]_d.$$
Because
$$a(k+d)=ak+ad\le bk+d,$$
the two progressions meet or touch, and their union is
$$[ar,b(k+d)]_d.$$
By induction over $m$,
$$U_r=[ar,\ b(r+M_rd)]_d.$$
Therefore
$$|U_r| = \frac{b(r+M_rd)-ar}{d}+1.$$
Since $d=b-a$,
$$|U_r| = \frac{dr+bM_rd}{d}+1 = r+bM_r+1.$$
Thus
$$N:=|S| = \sum_{r=0}^{d-1}(r+bM_r+1).$$
Write
$$1000=qd+s, \qquad 0\le s<d.$$
Then
$$M_r= \begin{cases} q,&0\le r\le s,\ q-1,&s<r<d. \end{cases}$$
Hence
$$\sum_{r=0}^{d-1}M_r =(s+1)q+(d-s-1)(q-1) =dq-d+s+1.$$
Using $dq+s=1000$,
$$\sum_{r=0}^{d-1}M_r =1001-d.$$
Also,
$$\sum_{r=0}^{d-1}r=\frac{d(d-1)}2.$$
Therefore
$$N = \frac{d(d-1)}2 + b(1001-d) + d.$$
Substituting $d=b-a$ gives
$$N = b(1001-b+a) +\frac{(b-a)(b-a+1)}2.$$
Hence the number of fortunate integers equals
$$\boxed{,b(1001-b+a)+\frac{(b-a)(b-a+1)}2,}.$$
Verification of Key Steps
The first delicate step is the criterion
$$T_k\cap T_{k'}\neq\varnothing \Longleftrightarrow k\equiv k' \pmod d.$$
Starting from
$$ak+dy=ak'+dy',$$
we obtain
$$a(k-k')=d(y'-y).$$
Since $\gcd(a,d)=1$, divisibility forces $d\mid(k-k')$. A careless argument that only proves necessity would miss the converse. The converse is obtained by writing $k-k'=dt$ and choosing $y'-y=at$, which indeed gives an equality of sums.
The second delicate step is proving that $U_r$ is one uninterrupted arithmetic progression. The relevant inequality is
$$a(k+d)\le bk+d.$$
After substituting $d=b-a$,
$$a(k+d)=ak+ad, \qquad bk+d=ak+dk+d.$$
Their difference is
$$dk+d-ad=d(k+1-a).$$
Since every $k$ in the residue class satisfies $k\ge r\ge0$, the induction begins at $r$ and the overlapping progression structure guarantees no gaps. Missing this check could lead to an incorrect count of components.
The third delicate step is evaluating
$$\sum M_r.$$
Writing $1000=qd+s$ gives exactly $s+1$ residues with value $q$ and the remaining $d-s-1$ residues with value $q-1$. An off-by-one error here changes the final answer by a multiple of $b$, so the count must be checked explicitly.
Alternative Approaches
Instead of grouping by the total number of coins $k$, one may parameterize all representations by the residue of the represented amount modulo $d=b-a$. Since
$$ax+by=a(x+y)+dy,$$
the residue modulo $d$ is determined by $x+y$. Because $a$ is invertible modulo $d$, each residue class of amounts corresponds to one residue class of the coin count. One then studies, for each residue class, the minimum and maximum obtainable amounts and shows that every intermediate term of the corresponding arithmetic progression occurs.
A generating-function approach is also possible. The set of achievable amounts is the support of
$$\sum_{x+y\le1000} z^{ax+by}.$$
After reorganizing by $k=x+y$, the same residue-class decomposition modulo $b-a$ emerges. The interval argument used in the main proof gives the count more directly and avoids manipulating generating functions.