Maths Olympiad Prep

Library / /36 of 48

Combinatorics Difficulty 8.9 Shortlist Prove it China

Given positive integers aa, bb, cc which are pairwise coprime. Let f(n)f(n) represent the number of nonnegative integer solutions (x,y,z)(x, y, z) of the equation ax+by+cz=na x + b y + c z = n. Prove: there exist real constants α\alpha, β\beta, γ\gamma, such that for every nonnegative real number nn,
f(n)(αn2+βn+γ)<a+b+c12. |f(n) - (\alpha n^2 + \beta n + \gamma)| < \frac{a+b+c}{12}.

Solution

Consider the generating function of {f(n)}\{f(n)\}:
G(t)=n=0f(n)tn=(1+ta+t2a+)(1+tb+t2b+)(1+tc+t2c+)=1(1ta)(1tb)(1tc). \begin{align*} G(t) &= \sum_{n=0}^{\infty} f(n) t^n \\ &= (1 + t^a + t^{2a} + \dots)(1 + t^b + t^{2b} + \dots)(1 + t^c + t^{2c} + \dots) \\ &= \frac{1}{(1 - t^a)(1 - t^b)(1 - t^c)}. \end{align*}
Since aa, bb, cc are pairwise coprime, the denominator (1ta)(1tb)(1tc)(1-t^a)(1-t^b)(1-t^c) contains no repeated factors other than (1t)3(1-t)^3. Let ω=e2πi/a\omega = e^{2\pi i/a}, τ=e2πi/b\tau = e^{2\pi i/b}, ρ=e2πi/c\rho = e^{2\pi i/c} be the primitive aa, bb, ccth roots of unity, respectively. Consider the partial fraction decomposition
1(1ta)(1tb)(1tc)=h0(1t)+h1(1t)2+h2(1t)3+k=1a1dk1ωkt+k=1b1ek1τkt+k=1c1fk1ρkt, \frac{1}{(1 - t^a)(1 - t^b)(1 - t^c)} = \frac{h_0}{(1 - t)} + \frac{h_1}{(1 - t)^2} + \frac{h_2}{(1 - t)^3} \\ + \sum_{k=1}^{a-1} \frac{d_k}{1 - \omega^k t} + \sum_{k=1}^{b-1} \frac{e_k}{1 - \tau^k t} + \sum_{k=1}^{c-1} \frac{f_k}{1 - \rho^k t},
in which the numerators h0h_0, h1h_1, h2h_2, d1,,da1d_1, \dots, d_{a-1}, e1,,eb1e_1, \dots, e_{b-1}, f1,,fc1f_1, \dots, f_{c-1} are all complex numbers. To find dkd_k in dk1ωkt\frac{d_k}{1 - \omega^k t}, multiply (1ωkt)(1 - \omega^k t) on both sides and let tωkt \to \omega^{-k} (or just let 1ωkt=01 - \omega^k t = 0). As all the other terms vanish, we arrive at
dk=limtωk1ωkt(1(ωkt)a)(1tb)(1tc)=1a×1(1ωkb)(1ωkc). \begin{align*} d_k &= \lim_{t \to \omega^{-k}} \frac{1 - \omega^k t}{(1 - (\omega^k t)^a)(1 - t^b)(1 - t^c)} \\ &= \frac{1}{a} \times \frac{1}{(1 - \omega^{-kb})(1 - \omega^{-kc})}. \end{align*}
In the expansion of G(t)G(t), the coefficient of tnt^n is
f(n)=h0+h1×(n+1)+h2×(n+1)(n+2)2+k=1a1dkωkn+k=1b1ekτkn+k=1c1fkρkn. f(n) = h_0 + h_1 \times (n + 1) + h_2 \times \frac{(n + 1)(n + 2)}{2} \\ + \sum_{k=1}^{a-1} d_k \omega^{kn} + \sum_{k=1}^{b-1} e_k \tau^{kn} + \sum_{k=1}^{c-1} f_k \rho^{kn}.

Observe that
k=1a1dkωknk=1a1dk=1a×k=1a111ωkb1ωkc1a×k=1a111ωk2=a2112a<a12. \begin{aligned} \left| \sum_{k=1}^{a-1} d_k \omega^{kn} \right| & \le \sum_{k=1}^{a-1} |d_k| \\ & = \frac{1}{a} \times \sum_{k=1}^{a-1} \frac{1}{|1 - \omega^{-kb}| |1 - \omega^{-kc}|} \\ & \le \frac{1}{a} \times \sum_{k=1}^{a-1} \frac{1}{|1 - \omega^k|^2} \\ & = \frac{a^2 - 1}{12a} < \frac{a}{12}. \end{aligned}
Here, the equality in the last row requires a lemma which will be proved.
Likewise, we have in the following k=1b1ekτkn<b12\left|\sum_{k=1}^{b-1} e_k \tau^{kn}\right| < \frac{b}{12} and k=1c1fkρkn<c12\left|\sum_{k=1}^{c-1} f_k \rho^{kn}\right| < \frac{c}{12}.
Taking β2=h22\beta_2 = \frac{h_2}{2}, β1=h1+32h2\beta_1 = h_1 + \frac{3}{2}h_2, β0=h0+h1+h2\beta_0 = h_0 + h_1 + h_2, it follows that
β2n2+β1n+β0f(n)k=1a1dkωkn+k=1b1ekτkn+k=1c1fkρkn<a+b+c12. \begin{aligned} |\beta_2 n^2 + \beta_1 n + \beta_0 - f(n)| & \le \left|\sum_{k=1}^{a-1} d_k \omega^{kn}\right| + \left|\sum_{k=1}^{b-1} e_k \tau^{kn}\right| + \left|\sum_{k=1}^{c-1} f_k \rho^{kn}\right| \\ & < \frac{a+b+c}{12}. \end{aligned}

Lemma (for the equality in the last row) For any positive integer mm,
k=1m11sin2kπm=m213 holds; equivalently, k=1m1cot2kπm=m23m+23. \sum_{k=1}^{m-1} \frac{1}{\sin^2 \frac{k\pi}{m}} = \frac{m^2-1}{3} \text{ holds; equivalently, } \sum_{k=1}^{m-1} \cot^2 \frac{k\pi}{m} = \frac{m^2-3m+2}{3}.
Proof of lemma For ϑA={πm,2πm,,(m1)πm}\vartheta \in A = \left\{ \frac{\pi}{m}, \frac{2\pi}{m}, \dots, \frac{(m-1)\pi}{m} \right\},
(cosϑ+isinϑ)m=cos(mϑ)+isin(mϑ)=±1, (\cos \vartheta + i \sin \vartheta)^m = \cos(m\vartheta) + i \sin(m\vartheta) = \pm 1,
where the imaginary part
Cm1sinϑcosm1ϑCm3sin3ϑcosm3ϑ+Cm5sin5ϑcosm5ϑ+=0, C_m^1 \sin \vartheta \cos^{m-1} \vartheta - C_m^3 \sin^3 \vartheta \cos^{m-3} \vartheta + C_m^5 \sin^5 \vartheta \cos^{m-5} \vartheta + \dots = 0,
or Cm1(cotϑ)m1Cm3(cotϑ)m3+Cm5(cotϑ)m5+=0C_m^1(\cot \vartheta)^{m-1} - C_m^3(\cot \vartheta)^{m-3} + C_m^5(\cot \vartheta)^{m-5} + \dots = 0. This implies that {cotkπm:k=1,2,,m1}\{\cot \frac{k\pi}{m} : k = 1, 2, \dots, m-1\} satisfy the (m1)(m-1)th degree polynomial in cot ϑ\vartheta. According to Viète's formulas, the sum of the m1m-1 roots is σ1=0\sigma_1 = 0 while the sum of their products multiplied in pairs is
σ2=Cm3Cm1=(m1)(m2)6. \sigma_2 = - \frac{C_m^3}{C_m^1} = - \frac{(m-1)(m-2)}{6}.
Consequently, the sum of the squares of the m1m-1 roots is
k=1m1cot2kπm=σ122σ2=m23m+23. \sum_{k=1}^{m-1} \cot^2 \frac{k\pi}{m} = \sigma_1^2 - 2\sigma_2 = \frac{m^2 - 3m + 2}{3}. \quad \Box

Solution:

By symmetry, assume abca \le b \le c. If a=b=c=1a = b = c = 1, f(n)f(n) is the number of ways of writing nn as three nonnegative integers, which is Cn+22C_{n+2}^2, and by taking α=12\alpha = \frac{1}{2}, β=32\beta = \frac{3}{2}, γ=1\gamma = 1, the error is constantly 0. In the following, assume c>1c > 1. For nonnegative integer mm, let g(m)g(m) represent the number of nonnegative integer solutions (x,y)(x, y) of ax+by=ma x + b y = m.
First, we try to find g(m)g(m). Let xka(modb)x \equiv k a \pmod b, mb(moda)m \equiv \ell b \pmod a, where
k{0,1,,b1},{0,1,,a1}. k \in \{0, 1, \dots, b-1\}, \quad \ell \in \{0, 1, \dots, a-1\}.
Evidently, xk(modb)x \equiv k \pmod b, y(moda)y \equiv \ell \pmod a. Suppose x=k+ubx = k + u b, y=+vay = \ell + v a.
Then
m=ka+b+(u+v)ab, m = k a + \ell b + (u + v) a b,
giving u+v=m(ka+b)abu + v = \frac{m - (k a + \ell b)}{a b}, and the number of pairs (u,v)(u,v) is
m(ka+b)ab+1 \frac{m - (k a + \ell b)}{a b} + 1 (note that m(ka+b)ab\frac{m - (k a + \ell b)}{a b} is an integer greater than 2-2; when m(ka+b)ab=1\frac{m - (k a + \ell b)}{a b} = -1 the conclusion is still valid). Therefore,
g(m)=m(ka+b)ab+1. g(m) = \frac{m - (k a + \ell b)}{a b} + 1.
Next, consider f(n)f(n). In the Diophantine equation ax+by+cz=na x + b y + c z = n, if zz is given (cznc z \le n), then the number of nonnegative solutions of ax+by=ncza x + b y = n - c z is g(ncz)g(n - c z). Hence,
f(n)=i=0n/cg(nic). f(n) = \sum_{i=0}^{\lfloor n/c \rfloor} g(n - i c).
For each integer ii, define ki{0,1,,b1}k_i \in \{0, 1, \dots, b-1\} and i{0,1,,a1}\ell_i \in \{0, 1, \dots, a-1\} such that
nic=kia(modb),nic=ib(moda). n - i c = k_i a \pmod{b}, \quad n - i c = \ell_i b \pmod{a}.
We have
f(n)=i=0ncg(nic)=i=0nc((nic)kia+ibab+1)=nc(nab+1)c2abnc(nc+1)(1bi=0ncki+1ai=0nci). \begin{aligned} f(n) &= \sum_{i=0}^{\lfloor \frac{n}{c} \rfloor} g(n - i c) \\ &= \sum_{i=0}^{\lfloor \frac{n}{c} \rfloor} \left( \frac{(n - i c) - k_i a + \ell_i b}{a b} + 1 \right) \\ &= \lfloor \frac{n}{c} \rfloor \cdot \left( \frac{n}{a b} + 1 \right) - \frac{c}{2 a b} \lfloor \frac{n}{c} \rfloor \left( \lfloor \frac{n}{c} \rfloor + 1 \right) - \left( \frac{1}{b} \sum_{i=0}^{\lfloor \frac{n}{c} \rfloor} k_i + \frac{1}{a} \sum_{i=0}^{\lfloor \frac{n}{c} \rfloor} \ell_i \right). \end{aligned}
Note that aa, bb, cc are pairwise coprime. Hence, for i=0,1,,b1i = 0, 1, \dots, b-1, the integers nicn - i c cover a complete system of residues modulo bb; so do the integers kiak_i a and the integers kik_i. In addition, when ii shifts by a multiple of bb, kik_i does not change.
Now we turn to i=0n/c(kib12)\sum_{i=0}^{\lfloor n/c \rfloor} \left( k_i - \frac{b-1}{2} \right): notice that the summands add up to 0 as ii goes over a complete system of residues modulo bb. Therefore, i=0n/c(kib12)=i=0s(kib12)\sum_{i=0}^{\lfloor n/c \rfloor} \left( k_i - \frac{b-1}{2} \right) = \sum_{i=0}^{s} \left( k_i - \frac{b-1}{2} \right), where ss is the least nonnegative residue of nc\lfloor \frac{n}{c} \rfloor modulo bb. In i=0s(kib12)\sum_{i=0}^{s} \left( k_i - \frac{b-1}{2} \right), the summands are distinct and are all from {1b2,3b2,,b32,b12}\left\{ \frac{1-b}{2}, \frac{3-b}{2}, \dots, \frac{b-3}{2}, \frac{b-1}{2} \right\} (the positive and negative elements are symmetric). This indicates that i=0s(kib12)\left| \sum_{i=0}^{s} \left( k_i - \frac{b-1}{2} \right) \right| cannot exceed the sum of the positive elements 22+42++b32+b12=b218\frac{2}{2} + \frac{4}{2} + \dots + \frac{b-3}{2} + \frac{b-1}{2} = \frac{b^2-1}{8} when bb is odd, or 12+32++b32+b12=b28\frac{1}{2} + \frac{3}{2} + \dots + \frac{b-3}{2} + \frac{b-1}{2} = \frac{b^2}{8} when bb is even. Hence,
i=0n/c(kib12)b28.1 \left| \sum_{i=0}^{\lfloor n/c \rfloor} \left( k_i - \frac{b-1}{2} \right) \right| \le \frac{b^2}{8}. \qquad \textcircled{1}
Likewise,
i=0n/c(ia12)a28.2 \left| \sum_{i=0}^{\lfloor n/c \rfloor} \left( \ell_i - \frac{a-1}{2} \right) \right| \le \frac{a^2}{8}. \qquad \textcircled{2}
From ① and ②, it follows that
(1bi=0ncki+1bi=0ncli)(nc+1)(b12b+a12a)1bi=0nc(kib12)+1ai=0nc(ia12)b8+a8.3 \begin{aligned} & \left| \left( \frac{1}{b} \sum_{i=0}^{\lfloor \frac{n}{c} \rfloor} k_i + \frac{1}{b} \sum_{i=0}^{\lfloor \frac{n}{c} \rfloor} l_i \right) - \left( \lfloor \frac{n}{c} \rfloor + 1 \right) \left( \frac{b-1}{2b} + \frac{a-1}{2a} \right) \right| \\ & \le \frac{1}{b} \left| \sum_{i=0}^{\lfloor \frac{n}{c} \rfloor} \left( k_i - \frac{b-1}{2} \right) \right| + \frac{1}{a} \left| \sum_{i=0}^{\lfloor \frac{n}{c} \rfloor} \left( \ell_i - \frac{a-1}{2} \right) \right| \\ & \le \frac{b}{8} + \frac{a}{8}. \end{aligned} \qquad \textcircled{3}
Let rr be the least nonnegative residue of nn modulo cc. Then
nc(nab+1)c2abnc(nc+1)(nc+1)(b12b+a12a)=(nr)(n+ab)abc(nr)(nr+c)2abc(2abab)(nr+c)2abc=n2(a+b+c)n(2abc+ac+bc)r(r+a+bc)2abc.4 \begin{aligned} & \lfloor \frac{n}{c} \rfloor \cdot \left( \frac{n}{a b} + 1 \right) - \frac{c}{2 a b} \lfloor \frac{n}{c} \rfloor \cdot \left( \lfloor \frac{n}{c} \rfloor + 1 \right) - \left( \lfloor \frac{n}{c} \rfloor + 1 \right) \left( \frac{b-1}{2b} + \frac{a-1}{2a} \right) \\ & = \frac{(n-r)(n+ab)}{abc} - \frac{(n-r)(n-r+c)}{2abc} - \frac{(2ab-a-b)(n-r+c)}{2abc} \\ & = \frac{n^2 - (a+b+c)n - (2abc+ac+bc) - r(r+a+b-c)}{2abc}. \end{aligned} \qquad \textcircled{4}
As rr takes values 0,1,,c10, 1, \dots, c-1, denote the maximum and the minimum of r(r+a+bc)r(r+a+b-c) as A+BA+B and ABA-B, respectively. By ③ and ④,
f(n)n2(a+b+c)n(2abc+ac+bc)A2abca+b8+B2abc. \left| f(n) - \frac{n^2 - (a+b+c)n - (2abc+ac+bc) - A}{2abc} \right| \le \frac{a+b}{8} + \frac{B}{2abc}.
Let α=12abc\alpha = \frac{1}{2abc}, β=a+b+c2abc\beta = -\frac{a+b+c}{2abc},
γ=2abc+ac+bc+A2abc. \gamma = -\frac{2abc + ac + bc + A}{2abc}.
We will justify the problem statement
f(n)(αn2+βn+γ)<a+b+c125 |f(n) - (\alpha n^2 + \beta n + \gamma)| < \frac{a+b+c}{12} \qquad \textcircled{5}
for different aa, bb, cc values. \square

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.