2 A clue " $k$ digits, sum is $n$ " gives a number $k$ and the sum of $k$ distinct, nonzero digits. An answer for that clue consists of $k$ digits with sum $n$. For example, the clue "Three digits, sum is 23 " has only one answer: $6,8,9$. The clue "Three digits, sum is 8 " has two answers: $1,3,4$ and $1,2,5$.
If the clue "Four digits, sum is $n$ " has the largest number of answers for any four-digit clue, then what is the value of $n$ ? How many answers does this clue have? Explain why no other four-digit clue can have more answers.
Solution: The sum of 20 has 12 answers, and this is the largest number of answers for any four-digit clue.
We could simply list all the possible sets of four digits and then count. There are 126 such sets.
Alternatively, define $A(s, n, k)$ to be the number of options with sum $s$ using exactly $n$ digits whose largest digit is less than or equal to $k$. Then the question is to find the maximum of $A(s, 4,9)$ for all values of $s$.
By symmetry, since we can replace each digit $d$ with $10-d$, we know that $A(s, 4,9)=A(40-s, 4,9)$, so we only need to investigate values of $s$ from the minimum, $1+2+3+4=10$, through 20 . (This also implies we only need to list the 69 sets of four digits whose sum is less than or equal to 20 in order to prove that 20 has the most answers. In fact, we can use even fewer than that, since by adding 1 to the largest digit we can see that $A(s, n, 9) \leq A(s+1, n, 9)$ as long as there are no ways of writing $s$ using the digit 9 ; for sums of four digits this shows we only need to investigate sums of 15 through 20 .)
To compute $A(s, n, k)$ in general, we note that any sum must either use a digit equal to $k$ or not. If there is a digit equal to $k$, then there are $A(s-k, n-1, k-1)$ ways to finish the sum. If there is no digit $k$, then there are $A(s, n, k-1)$ ways to finish the sum. Thus, $A(s, n, k)=A(s-k, n-1, k-1)+A(s, n, k-1)$.
We also know that $A(s, n, k)$ is 0 in a lot of cases, including any where $k<n$, and $A(s, 1, k)$ is equal to 1 when $0<s<k$ and 0 otherwise, because we must have one digit that equals $s$.
Thus, we can fill in the following tables, beginning with $n=2$, and then $n=3$, and then finally $n=4$.
\begin{tabular}{l||rrrrrrrrrrrrrrr}
$n=2$ & $s=3$ & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 \\
\hline$k=2$ & 1 & & & & & & & & & & & & & & \\
$k=3$ & 1 & 1 & 1 & & & & & & & & & & & & \\
$k=4$ & 1 & 1 & 2 & 1 & 1 & & & & & & & & & & \\
$k=5$ & 1 & 1 & 2 & 2 & 2 & 1 & 1 & & & & & & & & \\
$k=6$ & 1 & 1 & 2 & 2 & 3 & 2 & 2 & 1 & 1 & & & & & & \\
$k=7$ & 1 & 1 & 2 & 2 & 3 & 3 & 3 & 2 & 2 & 1 & 1 & & & & \\
$k=8$ & 1 & 1 & 2 & 2 & 3 & 3 & 4 & 3 & 3 & 2 & 2 & 1 & 1 & & \\
$k=9$ & 1 & 1 & 2 & 2 & 3 & 3 & 4 & 4 & 4 & 3 & 3 & 2 & 2 & 1 & 1 \\
\hline
\end{tabular}
\begin{tabular}{l||rrrrrrrrrrrrrrrrrrr}
$n=3$ & $s=6$ & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 \\
\hline$k=3$ & 1 & & & & & & & & & & & & & & & & & \\
$k=4$ & 1 & 1 & 1 & 1 & & & & & & & & & & & & & & \\
$k=5$ & 1 & 1 & 2 & 2 & 2 & 1 & 1 & & & & & & & & & & & \\
$k=6$ & 1 & 1 & 2 & 3 & 3 & 3 & 3 & 2 & 1 & 1 & & & & & & & & \\
$k=7$ & 1 & 1 & 2 & 3 & 4 & 4 & 5 & 4 & 4 & 3 & 2 & 1 & 1 & & & & & \\
$k=8$ & 1 & 1 & 2 & 3 & 4 & 5 & 6 & 6 & 6 & 6 & 5 & 4 & 3 & 2 & 1 & 1 & & \\
$k=9$ & 1 & 1 & 2 & 3 & 4 & 5 & 7 & 7 & 8 & 8 & 8 & 7 & 7 & 5 & 4 & 3 & 2 & 1 & 1 \\
\hline
\end{tabular}
\begin{tabular}{r||rrrrrrrrrrr}
$n=4$ & $s=10$ & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 \\
\hline$k=4$ & 1 & & & & & & & & & & \\
$k=5$ & 1 & 1 & 1 & 1 & & & & & & & \\
$k=6$ & 1 & 1 & 2 & 2 & 3 & 2 & 2 & 1 & 1 & & \\
$k=7$ & 1 & 1 & 2 & 3 & 4 & 4 & 5 & 4 & 4 & 3 & 2 \\
$k=8$ & 1 & 1 & 2 & 3 & 5 & 5 & 7 & 7 & 8 & 7 & 7 \\
$k=9$ & 1 & 1 & 2 & 3 & 5 & 6 & 8 & 9 & 11 & 11 & 12 \\
\hline
\end{tabular}

We see that 20 has 12 answers, while 19 and 18 have only 11 answers (and similarly 21 and 22 also have 11 answers), and the remaining numbers have even fewer answers.