Maths Olympiad Prep

Library / /274 of 520

Number theory Difficulty 5.3 AIME, harder Find the answer

7. Given that pp and qq are coprime positive integers, and nn is a non-negative integer. How many different integers can be expressed in the form ip+jqi p + j q, where ii and jj are non-negative integers, and i+jni + j \leqslant n.
(Li Weiguo, Contributed)

A number or a short expression. Spacing and $ signs are ignored.

Solution

7. If we denote A(p,q,n)=p˙+jqi,j0,i+jnA(p, q, n)=|\dot{p}+j q| i, j \geqslant 0, i+j \leqslant n, then the number of elements in A(p,q,n)A(p, q, n) is
A(p,q,n)={(n+1)(n+2)2,n<p;p(2np+3)2,np. |A(p, q, n)|=\left\{\begin{array}{ll} \frac{(n+1)(n+2)}{2}, & n < p; \\ \frac{p(2 n-p+3)}{2}, & n \geqslant p. \end{array}\right.

According to the definition, we have
A(p,q,n)\A(p,q,n1)={ip+(ni)qi=1,2,,n}. \begin{array}{l} A(p, q, n) \backslash A(p, q, n-1) \\ =\{i p+(n-i) q \mid i=1,2, \cdots, n\}. \end{array}

Notice that ip+(ni)q=p(i+q)+q(npi)i p+(n-i) q=p(i+q)+q(n-p-i), and
(i+q)+(npi)=np+qn1(i+q)+(n-p-i)=n-p+q \leqslant n-1, then
ip+(ni)qA(p,q,n1)npi0. i p+(n-i) q \in A(p, q, n-1) \Leftrightarrow n-p-i \geqslant 0.

Therefore, A(p,q,n)\A(p,q,n1)A(p, q, n) \backslash A(p, q, n-1)
={p˙+(ni)qi=np+1,np+2,,n,np;p˙+(ni)qi=0,1,,n,n<p. =\left\{\begin{array}{l} |\dot{p}+(n-i) q| i=n-p+1, n-p+2, \cdots, n \mid, n \geqslant p; \\ |\dot{p}+(n-i) q| i=0,1, \cdots, n \mid, n < p. \end{array}\right.

Let an=A(p,q,n)a_{n}=|A(p, q, n)|, then
anan1={p,np;n+1,n<p. a_{n}-a_{n-1}=\left\{\begin{array}{cc} p, & n \geqslant p; \\ n+1, & n < p. \end{array}\right.

Noting that a0=1a_{0}=1, for n<pn < p, we have
an=a0+(a1a0)++(anan1)=1+2++(n+1)=(n+1)(n+2)2; \begin{array}{l} a_{n}=a_{0}+\left(a_{1}-a_{0}\right)+\cdots+\left(a_{n}-a_{n-1}\right) \\ =1+2+\cdots+(n+1)=\frac{(n+1)(n+2)}{2}; \end{array}

Therefore, for npn \geqslant p, we have
an=ap1+(apap1)++(anan1)=ap1+(np+1)p=p(2np+3)2. \begin{array}{l} a_{n}=a_{p-1}+\left(a_{p}-a_{p-1}\right)+\cdots+\left(a_{n}-a_{n-1}\right) \\ =a_{p-1}+(n-p+1) p=\frac{p(2 n-p+3)}{2}. \end{array}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.