
4. Find the number of ordered triples $(x, y, z)$ of nonnegative integers satisfying the conditions:

(i) $x \leq y \leq z$;

(ii) $x+y+z \leq 100$.


Solution: We count by brute force considering the cases $x=0, x=1, \ldots, x=33$. Observe that the least value $x$ can take is zero, and its largest value is 33 .

$\underline{\mathbf{x}=0}$ If $y=0$, then $z \in\{0,1,2, \ldots, 100\}$; if $\mathrm{y}=1$, then $z \in\{1,2, \ldots, 99\}$; if $y=2$, then $z \in\{2,3, \ldots, 98\}$; and so on. Finally if $y=50$, then $z \in\{50\}$. Thus there are altogether $101+99+97+\cdots+1=51^{2}$ possibilities.

$\underline{\mathbf{x}=1}$. Observe that $y \geq 1$. If $y=1$, then $z \in\{1,2, \ldots, 98\}$; if $y=2$, then $z \in$ $\{2,3, \ldots, 97\}$; if $y=3$, then $z \in\{3,4, \ldots, 96\}$; and so on. Finally if $y=49$, then $z \in\{49,50\}$. Thus there are altogether $98+96+94+\cdots+2=49 \cdot 50$ possibilities.

General case. Let $x$ be even, say, $x=2 k, 0 \leq k \leq 16$. If $y=2 k$, then $z \in$ $\{2 k, 2 k+1, \ldots, 100-4 k\}$; if $y=2 k+1$, then $z \in\{2 k+1,2 k+2, \ldots, 99-4 k\}$; if $y=2 k+2$, then $z \in\{2 k+2,2 k+3, \ldots, 99-4 k\}$; and so on.

Finally, if $y=50-k$, then $z \in\{50-k\}$. There are altogether

$$
(101-6 k)+(99-6 k)+(97-6 k)+\cdots+1=(51-3 k)^{2}
$$

possibilities.

Let $x$ be odd, say, $x=2 k+1,0 \leq k \leq 16$. If $y=2 k+1$, then $z \in\{2 k+1,2 k+$ $2, \ldots, 98-4 k\}$; if $y=2 k+2$, then $z \in\{2 k+2,2 k+3, \ldots, 97-4 k\}$; if $y=2 k+3$, then $z \in\{2 k+3,2 k+4, \ldots, 96-4 k\}$; and so on.

Finally, if $y=49-k$, then $z \in\{49-k, 50-k\}$. There are altogether

$$
(98-6 k)+(96-6 k)+(94-6 k)+\cdots+2=(49-3 k)(50-3 k)
$$

possibilities.

The last two cases would be as follows:

$\underline{\mathbf{x}=32}$ : if $y=32$, then $z \in\{32,33,34,35,36\}$; if $y=33$, then $z \in\{33,34,35\}$; if $\overline{y=34}$, then $z \in\{34\}$; altogether $5+3+1=9=3^{2}$ possibilities.

$\underline{\mathbf{x}=33}$ : if $y=33$, then $z \in\{33,34\}$; only $2=1.2$ possibilities.

Thus the total number of triples, say $\mathrm{T}$, is given by,

$$
T=\sum_{k=0}^{16}(51-3 k)^{2}+\sum_{k=0}^{16}(49-3 k)(50-3 k)
$$

Writing this in the reverse order, we obtain

$$
\begin{aligned}
T & =\sum_{k=1}^{17}(3 k)^{2}+\sum_{k=0}^{17}(3 k-2)(3 k-1) \\
& =18 \sum_{k=1}^{17} k^{2}-9 \sum_{k=1}^{17} k+34 \\
& =18\left(\frac{17 \cdot 18 \cdot 35}{6}\right)-9\left(\frac{17 \cdot 18}{2}\right)+34 \\
& =30,787
\end{aligned}
$$

Thus the answer is 30787 .

## $\underline{\text { Aliter }}$

It is known that the number of ways in which a given positive integer $n \geq 3$ can be expressed as a sum of three positive integers $x, y, z$ (that is, $x+y+z=n$ ), subject to the condition $x \leq y \leq z$ is $\left\{\frac{n^{2}}{12}\right\}$, where $\{a\}$ represents the integer closest to $a$. If zero values are allowed for $x, y, z$ then the corresponding count is $\left\{\frac{(n+3)^{2}}{12}\right\}$, where now $n \geq 0$.

Since in our problem $n=x+y+z \in\{0,1,2, \ldots, 100\}$, the desired answer is

$$
\sum_{n=0}^{100}\left\{\frac{(n+3)^{2}}{12}\right\}
$$

For $n=0,1,2,3, \ldots, 11$, the corrections for \{\} to get the nearest integers are

$$
\frac{3}{12}, \frac{-4}{12}, \frac{-1}{12}, 0, \frac{-1}{12}, \frac{-4}{12}, \frac{3}{12}, \frac{-4}{12}, \frac{-1}{12}, 0, \frac{-1}{12}, \frac{-4}{12}
$$

So, for 12 consecutive integer values of $n$, the sum of the corrections is equal to

$$
\left(\frac{3-4-1-0-1-4-3}{12}\right) \times 2=\frac{-7}{6}
$$

Since $\frac{101}{12}=8+\frac{5}{12}$, there are 8 sets of 12 consecutive integers in $\{3,4,5, \ldots, 103\}$ with $99,100,101,102,103$ still remaining. Hence the total correction is

$$
\left(\frac{-7}{6}\right) \times 8+\frac{3-4-1-0-1}{12}=\frac{-28}{3}-\frac{1}{4}=\frac{-115}{12}
$$

So the desired number $T$ of triples $(x, y, z)$ is equal to

$$
\begin{aligned}
T & =\sum_{n=0}^{100} \frac{(n+3)^{2}}{12}-\frac{115}{12} \\
& =\frac{\left(1^{2}+2^{2}+3^{2}+\cdots+103^{2}\right)-\left(1^{2}+2^{2}\right)}{12}-\frac{115}{12} \\
& =\frac{103 \cdot 104 \cdot 207}{6 \cdot 12}-\frac{5}{12}-\frac{115}{12} \\
& =30787
\end{aligned}
$$
