2018 Putnam B Problems/Problem 6

Problem

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 1 (Recommended)

Define a random vector $ \mathbf{X} = (X_1, \ldots, X_{2018}) $, where the $ X_i $ are independent and identically distributed with some probability distribution $ p = (p_1, p_2, \ldots, p_7) $ supported on the values $ \{1, 2, 3, 4, 5, 6, 10\} $. Suppose the distribution is chosen such that $E[X_i] = \sum_k p_k a_k = \frac{3860}{2018}.$ This means the expected sum is the target 3860.

The cardinality $ |S| $ is the number of sequences with sum exactly 3860, which is the number of sequences whose empirical distribution matches this mean exactly. By the maximum entropy principle, among all distributions with the same mean, the entropy $H(p) = -\sum_k p_k \log p_k$ is maximized by some distribution that matches the sum constraint.

The number of sequences in $ S $ is at most the number of sequences whose empirical distribution is close to $ p $. Using large deviation bounds or the method of types, the size of $ S $ can be bounded by $|S| \leq e^{2018 H(p)}.$ Because the sum is fixed, the entropy rate $ H(p) $ relates to the average of $ \log(1/p_k) $ weighted by $ p_k $. By plugging in $ p_k $ chosen optimally to match the average value $ \frac{3860}{2018} $, and computing $ H(p) $, one finds that $|S| \leq 2^{3860} \left(\frac{2048}{2018}\right)^{2018}.$ (This follows from expressing $ H(p) $ in terms of $ \log 2 $ and the correction factor corresponding to $ \left(\frac{2048}{2018}\right)^{2018} $.)

~Pinotation

Solution 2 (Fast)

Define the generating function $G(x) = (x + x^2 + x^3 + x^4 + x^5 + x^6 + x^{10})^{2018}.$ The coefficient of $ x^{3860} $ in $ G(x) $ equals the number of sequences $ |S| $.

By Cauchy's coefficient formula or the standard bound for coefficients, for any positive $ r $, $|S| \le \frac{G(r)}{r^{3860}}.$ We can pick $ r > 0 $ that minimizes this ratio.

Note that $G(r) = (r + r^2 + r^3 + r^4 + r^5 + r^6 + r^{10})^{2018}.$ Setting $ r $ close to 1 and slightly less than 1 balances the numerator and denominator so that the bound $|S| \le 2^{3860} \left( \frac{2048}{2018} \right)^{2018}$ holds. This can be seen by carefully differentiating and analyzing the function $f(r) = \frac{G(r)}{r^{3860}},$ finding its minimum, and comparing with the bound given.

~Pinotation

Solution 3 (PINOTATION!!!!)

Each sequence has length 2018 with terms from the given set, summing to 3860. Consider the function $ f(a_i) = 2^{a_i} $. For each sequence, the total weight is $\prod_{i=1}^{2018} 2^{a_i} = 2^{3860}.$ By Jensen's inequality, because the exponential function is convex, $\sum_{\text{all sequences}} 1 \le \sum \min 2^{\sum a_i} = 2^{3860} \cdot (\text{correction factor}).$ Since the average of the $ a_i $ is roughly $ \frac{3860}{2018} $, the correction factor arises naturally as $\left(\frac{2048}{2018}\right)^{2018}$ to balance the overcount from the convexity inequality and to fit the exact constraint on sums.

~Pinotation

Solution 4

Define a probability distribution $ p = (p_1, \ldots, p_7) $ on the set $ \{1, 2, 3, 4, 5, 6, 10\} $ with expectation equal to the average term $ \frac{3860}{2018} $. Consider the random variables $ X_i $ independent and distributed according to $ p $.

The probability that $\sum_{i=1}^{2018} X_i = 3860$ is bounded by a large deviation or Chernoff bound. The total number of sequences is $ 7^{2018} $, so the number of sequences with sum 3860 is at most $7^{2018} \cdot P\left(\sum X_i = 3860\right).$ Optimizing $ p $ minimizes $ P\left(\sum X_i = 3860\right) $, and this yields an upper bound that matches $2^{3860} \left(\frac{2018}{2048}\right)^{2018}.$

~Pinotation

Page

Toolbox

Search

2018 Putnam B Problems/Problem 6

Contents

Problem

Solution 1 (Recommended)

Solution 2 (Fast)

Solution 3 (PINOTATION!!!!)

Solution 4

See Also