Problem of the Month
Solution to Problem 5: February 2024

The binomial coefficient $(\binom{n + 1}{2})$ is equal to $\frac{(n + 1)!}{2! (n - 1)!}$ , and since $\frac{(n + 1)!}{(n - 1)!} = (n + 1) n$ , we get that $(\binom{n + 1}{2}) = \frac{n (n + 1)}{2}$ . By the well-known formula for the sum of the first $n$ positive integers, we have $1 + 2 + 3 + \dots + (n - 1) + n = \frac{n (n + 1)}{2}$ , and so the answer to (i) is $(\binom{n + 1}{2})$ .

For (ii), we will consider the possible values of $x$ . Note that since $x$ and $y$ are non-negative and $x + y \leq n - 1$ , we must have that $0 \leq x \leq n - 1$ .

If $x = 0$ and $x + y \leq n - 1$ , then $y$ can be any of the integers from $0$ through $n - 1$ , for a total of $n$ possibilities.

If $x = 1$ , then $y$ can be any of the integers from $0$ through $n - 1 - 1 = n - 2$ , for a total of $n - 1$ possibilities.

In general, if $x = k$ for some $k$ with $0 \leq k \leq n - 1$ , then $y$ can be any integer from $0$ through $n - 1 - k$ . There are a total of $n - k$ integers from $0$ through $n - 1 - k$ .

Therefore, the number of pairs is $n + (n - 1) + (n - 2) + \dots + [n - (n - 1)]$ , but this is just the sum $1 + 2 + 3 + \dots + n$ written in reverse order. By part (i), we conclude that the number of non-negative integer pairs $(x, y)$ with $x + y \leq n - 1$ is $(\binom{n + 1}{2})$ .

For (iii), observe that if $x$ and $y$ are non-negative integers with $x + y \leq n - 1$ , then there is exactly one non-negative integer $z$ for which $x + y + z = n - 1$ . Therefore, the number of non-negative integer pairs $(x, y)$ with $x + y \leq n - 1$ is exactly the same as the number of non-negative integer triples $(x, y, z)$ with $x + y + z = n - 1$ .
Suppose the $r$ distinguishable cups are labelled Cup $1$ , Cup $2$ , and so on, up to Cup $r$ . Suppose the $n$ balls are placed in the $r$ cups. If we let $x_{k}$ be equal to the number of balls in Cup $k$ (noting that it is possible that $x_{k} = 0$ ), then we will have $x_{1} + x_{2} + \dots + x_{r} = n$ since there are $n$ balls in total. On the other hand, if we have a non-negative integer solution $(x_{1}, x_{2}, \dots, x_{r})$ to $x_{1} + x_{2} + \dots + x_{r} = n$ , then if we place $x_{k}$ balls in Cup $k$ for each $k$ , then we will have distributed exactly $n$ balls among the $r$ cups. Finally, observe that every placement of $n$ balls in the $r$ cups leads to a distinct solution to $x_{1} + x_{2} + \dots + x_{r} = n$ , and every solution to this equation gives a distinct way to distribute $n$ balls in the $r$ cups. This shows that the answers to questions (i) and (ii) are equal.

We will now show that the answer to question (ii) (and hence, the answer to question (i)), is $(\binom{n + r - 1}{r - 1})$ .

We need to reimagine the distribution of balls into cups as a choice of some objects. To give an idea of how it works, we will focus on the special case with $n = 10$ and $r = 4$ . That is, we want to count the number of ways to place $10$ indistinguishable balls in $4$ distinguishable cups.

Imagine laying the $10$ balls in a row. We want to place them among $4$ cups, which means we want to break the $10$ balls into $4$ groups (where some of the groups could be empty). We can do this by placing three partitions somewhere among the $10$ balls that are now lined up in a row. For example, the partitions could be placed as shown in the diagram below. Each ball is represented by a circle and each partition is represented by a vertical line.

This corresponds to placing $2$ balls in Cup $1$ , $3$ balls in Cup $2$ , $1$ ball in Cup $3$ , and $4$ balls in Cup $4$ . For a different example, we could place the partitions as follows.

In this case, two of the partitions are next to each other with no balls between them. This corresponds to the third cup having no balls in it.

In fact, any arrangement of $10$ indistinguishable balls and $3$ indistinguishable partitions will corresponds to an ordered list of four non-negative integers that have a sum of $10$ .

Therefore, there are $10 + 3 = 13$ positions where the balls and partitions are to be placed, and every way to choose three of the positions to be partitions corresponds to an ordering of $10$ balls and $3$ partitions. Therefore, the answer to the question in this case is $(\binom{13}{3})$ .

In general, if there are $r$ cups, then we need to use $r - 1$ partitions. This means there will be $n$ balls and $r - 1$ partitions for a total of $n + r - 1$ objects. There are $r - 1$ positions that need to be chosen for the partitions. Thus, the number of ways to place $n$ indistinguishable balls in $r$ distinguishable cups is $(\binom{n + r - 1}{r - 1})$ .
First note that non-negative integers $x_{1}, x_{2}, \dots, x_{r}$ satisfy $x_{1} + x_{2} + \dots + x_{r} \leq n$ if and only if $x_{1} + x_{2} + \dots + x_{r} = m$ for some integer $m$ with $0 \leq m \leq n$ . From part (b), the number of non-negative integer solutions to $x_{1} + x_{2} + \dots + x_{r} = m$ is $(\binom{r - 1 + m}{r - 1})$ . Therefore, the number of non-negative integer solutions to $x_{1} + x_{2} + \dots + x_{r} \leq n$ is $\begin{aligned} (\binom{r - 1 + 0}{r - 1}) + (\binom{r - 1 + 1}{r - 1}) + (\binom{r - 1 + 2}{r - 1}) + \dots + (\binom{r - 1 + n}{r - 1}) \\ = (\binom{r - 1}{r - 1}) + (\binom{r}{r - 1}) + (\binom{r + 1}{r - 1}) + \dots + (\binom{r + n - 1}{r - 1}) \end{aligned}$

Now suppose $x_{0}, x_{1}, \dots, x_{r}$ are non-negative integers with $x_{0} + x_{1} + \dots + x_{r} = n$ . Then we must have $x_{1} + x_{2} + \dots + x_{r} \leq n$ . On the other hand, if $x_{1} + x_{2} + \dots + x_{r} \leq n$ , then there is a unique non-negative integer $x_{0}$ that satisfies $x_{0} + x_{1} + \dots + x_{r} = n$ . This shows that the number of non-negative integer solutions to $x_{0} + x_{1} + \dots + x_{r} = n$ is the same as the number of non-negative integer solutions to $x_{1} + x_{2} + \dots + x_{r} \leq n$ . From part (b), the number of solutions to $x_{0} + x_{1} + \dots + x_{r} = n$ is $(\binom{n + (r + 1) - 1}{(r + 1) - 1}) = (\binom{n + r}{r})$ .

We have shown that the number of non-negative integer solutions to the inequality $x_{1} + x_{2} + \dots + x_{r} \leq n$ is equal to $(\binom{r - 1}{r - 1}) + (\binom{r}{r - 1}) + (\binom{r + 1}{r - 1}) + \dots + (\binom{r + n - 1}{r - 1})$ and it is also equal to $(\binom{n + r}{r})$ , so we conclude that $(\binom{r - 1}{r - 1}) + (\binom{r}{r - 1}) + (\binom{r + 1}{r - 1}) + \dots + (\binom{r + n - 1}{r - 1}) = (\binom{n + r}{r})$ This identity is sometime called the Hockey Stick Identity. If you are interested in knowing why it has such a strange name, read about Pascal’s Triangle and try to interpret this result using Pascal’s Triangle.
The integer $k$ having the property that $k < 10^{10}$ is the same as the integer $k$ having at most $10$ decimal digits. Thus, every such integer takes the form $k = a_{9} a_{8} a_{7} \dots a_{1} a_{0}$ where $a_{9}, a_{8}, a_{7}, \dots, a_{1}, a_{0}$ are the digits of $k$ , but some of the leading digits may be equal to $0$ . For example, to represent the integer $19723$ in this way, we would write it as $0000019723$ so $a_{9} = a_{8} = a_{7} = a_{6} = a_{5} = 0$ , $a_{4} = 1$ , $a_{3} = 9$ , $a_{2} = 7$ , $a_{1} = 2$ , and $a_{0} = 3$ .

Thus, to count the non-negative integers with a digit sum of $21$ , we need to find all non-negative integer solutions to the equation $a_{9} + a_{8} + a_{7} + \dots + a_{1} + a_{0} = 21$ , but we have an additional restriction that each $a_{i}$ is a digit, meaning $0 \leq a_{i} \leq 9$ .

Switching notation slightly to match earlier parts, the answer to the question is equal to the number of solutions to the equation $x_{1} + x_{2} + \dots + x_{10} = 21$ where each $x_{i}$ is an integer with $0 \leq x_{i} \leq 9$ .

By part (b), the number of non-negative integer solutions to $x_{1} + x_{2} + \dots + x_{10} = 21$ without the restriction that $x_{i} \leq 9$ is $(\binom{21 + 10 - 1}{10 - 1}) = (\binom{30}{9})$ . The total of $(\binom{30}{9})$ includes some solutions that violate $x_{i} \leq 9$ for some $i$ . We will now count the solutions that have $x_{i} \geq 10$ for at least one $i$ so we can remove these from the count.

First, we claim that for each index $i$ , there are $(\binom{20}{9})$ solutions that have $x_{i} \geq 10$ . For example, consider a non-negative integer solution to $x_{1} + x_{2} + \dots + x_{10} = 21$ with $x_{1} \geq 10$ . If we set $y_{1} = x_{1} - 10$ then $y_{1}$ is a non-negative integer and $y_{1} + x_{2} + \dots + x_{10} = (x_{1} - 10) + x_{2} + \dots + x_{10} = (x_{1} + x_{2} + \dots + x_{10}) - 10 = 21 - 10 = 11$ Also, if we consider a non-negative integer solution to $y_{1} + x_{2} + \dots + x_{10} = 11$ , and set $x_{1} = y_{1} + 10$ , then we obtain a non-negative integer solution to $x_{1} + x_{2} + \dots + x_{10} = 21$ with $x_{1} \geq 10$ . By part (b), there are $(\binom{20}{9})$ non-negative integer solutions to $y_{1} + x_{2} + \dots + x_{10} = 11$ and so, equivalently, there are $(\binom{20}{9})$ non-negative integer solutions to $x_{1} + x_{2} + \dots + x_{10} = 21$ with $x_{1} \geq 10$ .

Similarly, for each $i$ from $1$ through $10$ , there are exactly $(\binom{20}{9})$ non-negative integer solutions to $x_{1} + x_{2} + \dots + x_{10} = 21$ with $x_{i} \geq 10$ . Note that these different sets of solutions have overlap and so the number of solutions with $x_{i} \geq 10$ for at least one $i$ is not $10 (\binom{20}{9})$ . This is an overcount. For example, the solution $x_{1} = 10$ , $x_{2} = 10$ , $x_{3} = 1$ , and $x_{4} = x_{5} = x_{6} = x_{7} = x_{8} = x_{9} = x_{10} = 0$ is double counted: once as a solution with $x_{1} \geq 10$ and once as a solution with $x_{2} \geq 10$ .

Next, we claim that for every pair of indices $i$ and $j$ , with $i \neq j$ , there are $(\binom{10}{9})$ non-negative integer solutions to $x_{1} + x_{2} + \dots + x_{10} = 21$ with $x_{i} \geq 10$ and $x_{j} \geq 10$ . Each of these solutions will be double counted in the count $10 (\binom{20}{9})$ . Note that there are no solutions to $x_{1} + x_{2} + \dots + x_{10} = 21$ that have more than two variables exceeding $9$ and so this will give us the complete picture.

For an example, consider a non-negative integer solution to $x_{1} + x_{2} + x_{3} + \dots + x_{10} = 21$ with $x_{1} \geq 10$ and $x_{2} \geq 10$ . If we set $y_{1} = x_{1} - 10$ and $y_{2} = x_{2} - 10$ then $y_{1}$ and $y_{2}$ are non-negative integers satisfying $y_{1} + y_{2} + x_{3} + \dots + x_{10} = 1$ . Similarly, a non-negative integer solution to $y_{1} + y_{2} + x_{3} + \dots + x_{10} = 1$ corresponds to a non-negative integer solution to $x_{1} + x_{2} + x_{3} + \dots + x_{10} = 21$ with $x_{1}, x_{2} \geq 10$ . By part (b), there are $(\binom{10}{9})$ non-negative integer solutions to $y_{1} + y_{2} + x_{3} + \dots + x_{10} = 1$ and so, equivalently, there are $(\binom{10}{9})$ non-negative integer solutions to $x_{1} + x_{2} + \dots + x_{10} = 21$ with $x_{1} \geq 10$ and $x_{2} \geq 10$ .

Similarly, for each pair $i$ and $j$ , with $i \neq j$ , there are $(\binom{10}{9})$ solutions to $x_{1} + x_{2} + \dots + x_{10} = 21$ with $x_{i} \geq 10$ and $x_{j} \geq 10$ .

Since there are $(\binom{10}{2})$ ways to choose two indices, there are $(\binom{10}{2}) (\binom{10}{9}) = 45 (\binom{10}{9})$ non-negative integer solutions that have two variables exceeding $9$ . From this, we conclude that the number of non-negative integer solutions to $x_{1} + x_{2} + \dots + x_{10} = 21$ that have $x_{i} \geq 10$ for at least one $i$ is given by $10 (\binom{20}{9}) - 45 (\binom{10}{9})$ .

Therefore, the total number of non-negative integer solutions to $x_{1} + x_{2} + \dots + x_{10} = 21$ with $x_{i} \leq 9$ for all $i$ can be calculated as follows: $\begin{aligned} (\binom{30}{9}) - 10 (\binom{20}{9}) + 45 (\binom{10}{9}) & = 14 307 150 - 10 (167 960) + 45 (10) \\ = 14 307 150 - 1 679 600 + 450 \\ = 12 628 000 \end{aligned}$
By the same convention as the previous problem, we can recognize every positive integer less than $10^{8}$ as an $8$ -digit integer by possibly prepending some $0$ s. Thus, we wish to count the number of solutions to the equation $x_{1} - x_{2} + x_{3} - x_{4} + x_{5} - x_{6} + x_{7} - x_{8} = 0$ where the $x_{i}$ are integers with $0 \leq x_{i} \leq 9$ for each $i$ .

We can rearrange this equation to get $x_{1} + x_{3} + x_{5} + x_{7} = x_{2} + x_{4} + x_{6} + x_{8}$ , so we want to count non-negative integer solutions to this equation where $x_{i} \leq 9$ for each $i$ .

Since $0 \leq x_{i} \leq 9$ , we must have that $0 \leq x_{1} + x_{3} + x_{5} + x_{7} \leq 36$ and $0 \leq x_{2} + x_{4} + x_{6} + x_{8} \leq 36$ . For each $n$ from $0$ through $36$ , let $A_{n}$ denote the number of non-negative integer solutions to $x_{1} + x_{3} + x_{5} + x_{7} = n$ with $x_{i} \leq 9$ for $i = 1$ , $i = 3$ , $i = 5$ , and $i = 7$ . Since all of the $8$ variables have the exact same restrictions, we also have that $A_{n}$ is the number of non-negative integer solutions to $x_{2} + x_{4} + x_{6} + x_{8} = n$ where each variable is no larger than $9$ . Thus, for each $n$ from $0$ through $36$ , there are $A_{n}^{2}$ solutions to the equation with each side equal to $n$ . Therefore, the answer to the question is $A_{0}^{2} + A_{1}^{2} + A_{2}^{2} + \dots + A_{36}^{2}$ Now suppose that $0 \leq n \leq 36$ and $x_{1} + x_{3} + x_{5} + x_{7} = n$ with $0 \leq x_{i} \leq 9$ for each $i$ . Then $(9 - x_{1}) + (9 - x_{3}) + (9 - x_{5}) + (9 - x_{7}) = 36 - n$ , and observe that since $0 \leq x_{i} \leq 9$ , we have $0 \leq 9 - x_{i} \leq 9$ , and since $0 \leq n \leq 36$ , we have $0 \leq 36 - n \leq 36$ . You should convince yourself that this shows that the number of solutions to $x_{1} + x_{3} + x_{5} + x_{7} = n$ is the same as the number of solutions to $x_{1} + x_{3} + x_{5} + x_{7} = 36 - n$ . In other words, $A_{n} = A_{36 - n}$ . When $n = 18$ , we also have $36 - n = 18$ , so the total we seek is equal to $2 (A_{0}^{2} + A_{1}^{2} + A_{2}^{2} + \dots + A_{17}^{2}) + A_{18}^{2}$ For $n = 0$ through $n = 9$ , if $x_{1} + x_{3} + x_{5} + x_{7} = n$ , then $x_{i} \leq 9$ for each $i$ since the total is at most $9$ . This means the number of solutions to $x_{1} + x_{3} + x_{5} + x_{7} = n$ where $x_{i} \leq 9$ for each $i$ is equal to the number of non-negative integer solutions without restriction. By part (b), if $0 \leq n \leq 9$ , then $A_{n} = (\binom{n + 3}{3})$ .

For $n = 10$ through $n = 18$ , there are still $(\binom{n + 3}{3})$ unrestricted solutions, but here the count includes solutions with $x_{i} \geq 10$ for some $i$ . Note that since the total is at most $18$ , it is not possible for more than one variable to exceed $9$ . Similar to the argument in part (d), for each $i$ , there are $(\binom{n + 3 - 10}{3})$ solutions with $x_{i} \geq 10$ . Since there are $4$ variables, there are $4 (\binom{n + 3 - 10}{3})$ solutions with a variable exceeding $9$ . Therefore, $A_{n} = (\binom{n + 3}{3}) - 4 (\binom{n + 3 - 10}{3})$ .

We now just need to compute the total. $\begin{aligned} 2 (A_{0}^{2} + \dots + A_{9}^{2}) + 2 (A_{10}^{2} + \dots + A_{17}^{2}) + A_{18}^{2} \\ = 2 ({(\binom{3}{3})}^{2} + \dots + {(\binom{12}{3})}^{2}) + 2 ({((\binom{13}{3}) - 4 (\binom{3}{3}))}^{2} + \dots + {((\binom{20}{3}) - 4 (\binom{10}{3}))}^{2}) + {((\binom{21}{3}) - 4 (\binom{11}{3}))}^{2} \\ = 2 (1^{2} + 4^{2} + 10^{2} + 20^{2} + 35^{2} + 56^{2} + 84^{2} + 120^{2} + 165^{2} + 220^{2}) \\ + 2 (79524 + 121104 + 172225 + 230400 + 291600 + 350464 + 400689 + 435600) \\ + 448900 \\ = 4816030 \end{aligned}$
Let $x = a - 1$ , $y = b - 1$ , and $z = c - 1$ . Then we have $0 \leq x < y < z \leq 2023$ and $x + y + z = 2024$ . Thus, we want to count the number of non-negative integer solutions to $x + y + z = 2024$ where $x < y < z \leq 2023$ . Suppose $T$ is the number of non-negative integer solutions to $x + y + z = 2024$ where $x$ , $y$ , and $z$ are all distinct and no larger than $2023$ . Since there are six different arrangements of three distinct integers, exactly one of which puts them in increasing order, the answer to the given question is $\frac{1}{6} T$ .

To compute $T$ , we note that by part (b) there are $(\binom{2026}{2})$ non-negative integer solutions to $x + y + z = 2024$ where there are no restrictions on the non-negative integers $x$ , $y$ , and $z$ . We now need to remove those solutions where at least two of the variables are equal as well as any that have at least one of $x$ , $y$ , and $z$ greater than $2023$ .

If one of $x$ , $y$ , and $z$ is greater than $2023$ , then the condition $x + y + z = 2024$ and the fact that $x$ , $y$ , and $z$ are non-negative integers implies that one of the variables equals $2024$ and the other two equal $0$ . Thus, any solutions with a variable greater than $2023$ will also have two variables equal to each other, so we can just count the number of solutions with at least two variables equal and subtract this total from $(\binom{2026}{2})$ . Since $2024$ is not a multiple of $3$ , it is impossible that $x = y = z$ . Therefore, we need to count the number of solutions where exactly two variables are equal.

To count the number of solutions to $x + y + z = 2024$ with two variables equal, we will count the number of solutions with $x = y$ and triple the result since there are three choices of which two variables are equal.

We now want to count non-negative integer solutions to $2 x + z = 2024$ . This equation implies that $z$ is even, or that $z = 2 w$ for some non-negative integer $w$ . Thus, we need to count the number of solutions to $2 x + 2 w = 2024$ or $x + w = 1012$ . By part (b), this is $1013$ , so the number of solutions to the equation with two variables equal to each other is $3 \times 1013 = 3039$ .

We now have that $T = (\binom{2026}{2}) - 3039$ , and so the number of solutions is $\frac{1}{6} ((\binom{2026}{2}) - 3039) = \frac{1}{6} (1013 \times 2025 - 3039) = 1013 (337) = 341381$

Problem of the MonthSolution to Problem 5: February 2024

Problem of the Month
Solution to Problem 5: February 2024