Putnam 2018, Problem B-6

Let $S$ be the set of sequences of length 2018 whose terms are in the set $\{1,2,3,4,5,6,10\}$ and sum to 3860. Prove that the cardinality of $S$ is at most
\[
2^{3860} \cdot \left( \frac{2018}{2048} \right)^{2018}.
\]


Solution:
Let $a(k,n)$ denote the number of sequences of length $k$ taken from the set $\{1,2,3,4,5,6,10\}$ and having sum $n$. We prove that
$$a(k,n)<2^n\left(\frac{2018}{2048}\right)^k$$
by double induction on $n+k$ and $n-k$. The claim is clearly true when $n-k\leq 0$ and in particular when $n=k=1$, the smallest case for $n+k$.

We categorize the sequences counted by $a(k,n)$ by whether they end in $1,2,3,4,5,6,10$; removing the last term of such a sequence yields a sequence counted by $a(k-1,n-1),a(k-1,n-2),a(k-1,n-3),a(k-1,n-4),a(k-1,n-5),a(k-1,n-6),a(k-1,n-10)$, respectively. Therefore,
$$\begin{aligned}
a(k,n)&=a(k-1,n-1)+\cdots\\
&\quad+a(k-1,n-6)+a(k-1,n-10)\\
&<(2^{n-1}+\cdots+2^{n-6}+2^{n-10})\left(\frac{2018}{2048}\right)^{k-1}\\
&=2^n\left(\frac{1}{2}+\cdots+\frac{1}{64}+\frac{1}{1024}\right)\left(\frac{2018}{2048}\right)^{k-1}\\
&=2^n\left(\frac{1009}{1024}\right)\left(\frac{2018}{2048}\right)^{k-1}\\
&=2^n\left(\frac{2018}{2048}\right)^k
\end{aligned}$$
where we used directly the induction hypothesis to obtain the inequality on the second line. The case $k=2018,n=3860$ yields the desired result.

Remark. K. Soundararajan suggests the following reinterpretation of this argument. The quantity $a(k,n)$ can be interpreted as the coefficient of $x^n$ in $(x+x^2+\cdots+x^6+x^{10})^k$. Since this polynomial has nonnegative coefficients, for any $x$, we have
$$a(k,n)x^n<(x+x^2+\cdots+x^6+x^{10})^k.$$
Substituting $x=\frac{1}{2}$ yields the bound stated above.

On a related note, Alexander Givental suggests that the value $n=3860$ (which is otherwise irrelevant to the problem) may have been chosen for the following reason: as a function of $x$, the upper bound $x^{-n}(x+x^2+\cdots+x^6+x^{10})^k$ is minimized when
$$\frac{x(1+2x+\cdots+6x^5+x^9)}{x+x^2+\cdots+x^6+x^{10}}=\frac{n}{k}.$$

In order for this to hold for $x=1/2,k=2018$, one must take $n=3860$.

Remark. For purposes of comparison, the stated bound is about $10^{1149}$, while the trivial upper bound given by counting all sequences of length 2018 of positive integers that sum to 3860 is
$$\binom{3859}{2017}\sim 10^{1158}.$$
The latter can be easily derived by a "stars and bars" argument: visualize each sequence of this form by representing the value $n$ by $n$ stars and inserting a bar between adjacent terms of the sequence. The resulting string of symbols consists of one star at the beginning, 2017 bar-star combinations, and 3860-2018 more stars. Using a computer, it is practical to compute the exact cardinality of $S$ by finding the coefficient of $x^{3860}$ in $(x+x^2+\cdots+x^6+x^{10})^{2018}$. For example, this can be done in Sage in a couple of seconds as follows. (The truncation is truncated modulo $x^{4000}$ for efficiency.)

```sage
P.<x> = PowerSeriesRing(ZZ, 4000)
f = (x + x^2 + x^3 + x^4 + \
     x^5 + x^6 + x^10)^2018
m = list(f)[3860]
N(m)
```
Output: 8.04809122940636e1146

This computation shows that the upper bound of the problem differs from the true value by a factor of about 150.