16. Let $f(n)$ denote the number of positive integral solutions of the equation $4 x+3 y+2 z=n$. Find $f(2009)-f(2000)$.
(2 marks)
設 $f(n)$ 表示方程 $4 x+3 y+2 z=n$ 的正整數解數目。求 $f(2009)-f(2000)$ 。 (2 分)
16. 1000
16. Note that if $(a, b, c)$ is a positive integer solution to the equation $4 x+3 y+2 z=2009$, then $(a-1, b-1, c-1)$ is a non-negative integer solution to the equation $4 x+3 y+2 z=2000$. Conversely, every positive integer solution to $4 x+3 y+2 z=2000$ corresponds to a positive integer solution to $4 x+3 y+2 z=2009$.
Hence positive integer solutions to the two equations are in one-to-one correspondence except for solutions to $4 x+3 y+2 z=2009$ with at least one variable equal to 1 , in which case the corresponding solutions to $4 x+3 y+2 z=2000$ have at least one variable being 0 . The number of such solutions is exactly equal to the value of $f(2009)-f(2000)$. To count this number, we note that
- if $x=1$, the equation becomes $3 y+2 z=2005$ and so $y$ may be equal to $1,3,5, \ldots, 667$ so that $z$ is a positive integer, i.e. there are $\frac{667-1}{2}+1=334$ solutions in this case;
- if $y=1$, the equation becomes $4 x+2 z=2006$, or $2 x+z=1003$, which has 501 positive integer solutions (corresponding to $x=1,2, \ldots, 501$ ); and
- if $z=1$, the equation becomes $4 x+3 y=2007$ and so $y$ may be equal to $1,5,9, \ldots, 665$ so that $z$ is a positive integer, i.e. there are $\frac{665-1}{4}+1=167$ solutions in this case.
Two of these solutions have been double-counted (corresponding to $x=y=1$ and $y=z=1$ ). It follows that the answer is $334+501+167-2=1000$.