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}.\]
Problem
Source:
Tags: Putnam, Putnam 2018, Hi
03.12.2018 02:00
This is a pretty funny problem: personally, I spent a lot of time wondering why these specific numbers were chosen until I had the "Aha!" moment.
03.12.2018 07:42
This is a nontrivial observation...
03.12.2018 08:23
The numbers in the problem statement kind of expose the solution... $2^{3860}$ sort of means $3860$ times of coin flips, and the $2018$-th power kind of tells you that there is 2018 independent events. So a naive way to think about it is that do coin clips until there are $2018$ heads, and see if the time that the $i$-th heads occurred minus the time that the $i-1$-th heads occured is in the set ${1,2,3,4,5,6,10}$. Then there is some work to relate this to the original problem, but it is pretty straight forward. Fun story: I did not realize that $2018/2048$ is not reduced, so I seriously thought that $2^10 = 2048$, and I somehow got that $2^{-1}+2^{-2}+\cdots+2^{-6}+2^{-10} = 2017/2048$. I am really expecting a 1 on this now oops :p
03.12.2018 08:28
jonny97 wrote: This is a nontrivial observation... I agree; I spent about an hour staring at the problem before observing it
03.12.2018 08:38
USJL wrote: The numbers in the problem statement kind of expose the solution... $2^{3860}$ sort of means $3860$ times of coin flips, and the $2018$-th power kind of tells you that there is 2018 independent events. So a naive way to think about it is that do coin clips until there are $2018$ heads, and see if the time that the $i$-th heads occurred minus the time that the $i-1$-th heads occured is in the set ${1,2,3,4,5,6,10}$. Then there is some work to relate this to the original problem, but it is pretty straight forward. Fun story: I did not realize that $2018/2048$ is not reduced, so I seriously thought that $2^{10} = 2048$, and I somehow got that $2^{-1}+2^{-2}+\cdots+2^{-6}+2^{-10} = 2017/2048$. I am really expecting a 1 on this now oops :p
03.12.2018 08:57
There's also a nice generating function solution (which I think is isomorphic to the one above). Note that $|S|$ is the coefficient of $x^{3860}$ in the expansion of $(x + x^2 + x^3 + x^4 + x^5 + x^6 + x^{10})^{2018}$. To extract this coefficient we can use the residue theorem from complex analysis: $$|S| = \frac{1}{2\pi i} \oint_{C} \frac{(z + z^2 + z^3 + z^4 + z^5 + z^6 + z^{10})^{2018}}{z^{3861}} dz$$where $C$ is any contour enclosing the origin. Choosing $C$ to be the circle of radius $\frac{1}{2}$ centered at the origin, we can use the triangle inequality to bound this as: $$ |S| = \frac{1}{2\pi} \left\lvert \oint_{|z| = \frac{1}{2}} \frac{(z + z^2 + z^3 + z^4 + z^5 + z^6 + z^{10})^{2018}}{z^{3861}} dz \right\rvert $$$$ \leq \frac{1}{2\pi} \oint_{|z| = \frac{1}{2}} \frac{|z + z^2 + z^3 + z^4 + z^5 + z^6 + z^{10}|^{2018}}{|z|^{3861}} dz$$$$ \leq \frac{1}{2\pi} \oint_{|z| = \frac{1}{2}} \frac{(|z| + |z|^2 + |z|^3 + |z|^4 + |z|^5 + |z|^6 + |z|^{10})^{2018}}{|z|^{3861}} dz$$$$ = \frac{1}{2\pi} \cdot \frac{2\pi}{2} \cdot \frac{(\frac{1}{2} + \frac{1}{2^2} + \frac{1}{2^3} + \frac{1}{2^4} + \frac{1}{2^5} + \frac{1}{2^6} + \frac{1}{2^{10}})^{2018}}{\frac{1}{2^{3861}}} = 2^{2860}\left(\frac{2018}{2048}\right)^{2018}$$as desired.
04.12.2018 23:33
This problem follows directly from a Chernoff bound: Pick the numbers at random, and let $X_1, X_2, ..., X_{2018}$ be the outcomes. Define $X = X_1 + \cdots + X_{2018}$. Then, we wish to prove that $$P(X \le 3860) \le 2^{3860} \left(\frac{2018}{2048}\right)^{2018} \cdot \frac{1}{7^{2018}}$$However, we can use Markov's inequality in way that a Chernoff bound is derived: $$P(X \le 3860) = P(2^{-X} \ge 2^{-3860}) \le \mathbb{E}[2^{-X}] \cdot 2^{3860}$$Note that $2^{-X} = 2^{-X_1} \cdots 2^{-X_{2018}}$, and each of the factors are i.i.d. Therefore, we can break the expectation across the product. $$\mathbb{E}[2^{-X_1}] = \frac{1}{7} \left( 2^{-1} + 2^{-2} + \cdots + 2^{-6} + 2^{-10}\right) = \frac{1}{7} \cdot \frac{2018}{2048}$$Raise this result to the 2018th power, and we get the desired result.
08.12.2018 20:39
So, did we ever figure out the significance of $3860$?
09.12.2018 02:35
Inversion wrote: There's also a nice generating function solution (which I think is isomorphic to the one above). Note that $|S|$ is the coefficient of $x^{3860}$ in the expansion of $(x + x^2 + x^3 + x^4 + x^5 + x^6 + x^{10})^{2018}$. To extract this coefficient we can use the residue theorem from complex analysis: $$|S| = \frac{1}{2\pi i} \oint_{C} \frac{(z + z^2 + z^3 + z^4 + z^5 + z^6 + z^{10})^{2018}}{z^{3861}} dz$$where $C$ is any contour enclosing the origin. Choosing $C$ to be the circle of radius $\frac{1}{2}$ centered at the origin, we can use the triangle inequality to bound this as: $$ |S| = \frac{1}{2\pi} \left\lvert \oint_{|z| = \frac{1}{2}} \frac{(z + z^2 + z^3 + z^4 + z^5 + z^6 + z^{10})^{2018}}{z^{3861}} dz \right\rvert $$$$ \leq \frac{1}{2\pi} \oint_{|z| = \frac{1}{2}} \frac{|z + z^2 + z^3 + z^4 + z^5 + z^6 + z^{10}|^{2018}}{|z|^{3861}} dz$$$$ \leq \frac{1}{2\pi} \oint_{|z| = \frac{1}{2}} \frac{(|z| + |z|^2 + |z|^3 + |z|^4 + |z|^5 + |z|^6 + |z|^{10})^{2018}}{|z|^{3861}} dz$$$$ = \frac{1}{2\pi} \cdot \frac{2\pi}{2} \cdot \frac{(\frac{1}{2} + \frac{1}{2^2} + \frac{1}{2^3} + \frac{1}{2^4} + \frac{1}{2^5} + \frac{1}{2^6} + \frac{1}{2^{10}})^{2018}}{\frac{1}{2^{3861}}} = 2^{2860}\left(\frac{2018}{2048}\right)^{2018}$$as desired. Can you explain why you chose that C and why you used the triangle inequality to bound it? Thanks
09.12.2018 04:23
v_Enhance wrote: So, did we ever figure out the significance of $3860$? Here is the answer given at Kiran Kedlaya's Putnam archive: Quote: Alexander Givental suggests that the value $n = 3860$ (which is otherwise irrelevant to the problem) was chosen for the following reason: as a function of $x$, the upper bound $x^{-n}(x + x^2 + \dotsb +x^6 +x^{10})^k$ is minimized when \[\frac{x(1+2x+\dotsb+6x^5+10x^9)}{x+x^2+\dotsb+x^6+x^{10}}=\frac{n}{k}.\]In order for this to hold for $x = 1/2$, $k = 2018$, one must take $n = 3860$.
05.01.2019 17:41
In this archive it is stated that inequality $a(k,n)x^n < (x+x^2 +...+x^6 +x^{10})^k$ holds for all $x$. I claim it should be "for all $x>0$." Counterexample : $2|n, 2|k+1, x=-\frac{1}{2}$
19.05.2020 17:59
Solution with hint from stroller. The key idea is the following. Note that the desired number is the coefficient of the $x^{3860}$ term in \[(x^1+x^2+x^3+x^4+x^5+x^6+x^{10})^{2018}.\]Let the desired number be $N$. Note that for positive $x$, we have \[Nx^{3860} < (x^1+x^2+x^3+x^4+x^5+x^6+x^{10})^{2018}.\]Taking $x=1/2$ and rearranging gives the desired result.
19.05.2020 18:16
GeronimoStilton wrote: Solution with hint from stroller. The key idea is the following. Note that the desired number is the coefficient of the $x^{3860}$ term in \[(x^1+x^2+x^3+x^4+x^5+x^6+x^{10})^{2018}.\]Let the desired number be $N$. Note that for positive $x$, we have \[Nx^{3860} < (x^1+x^2+x^3+x^4+x^5+x^6+x^{10})^{2018}.\]Taking $x=1/2$ and rearranging gives the desired result. Wow, that's surprisingly clean. Nice job.
13.04.2022 01:15
Let $f(x)=(x+x^2+\ldots +x^6+x^{10})^{2018}$. Then, $2^{3860}f(\frac{1}{2})$ is equal to the given expression, and is at least $a_{3860}\left(\frac{1}{2}\right)^{3860}\cdot 2^{3860}=a_{3860}$, where $a_{3860}$ is the $3860$th degree coefficient and counts the number of satisfactory tuples.
11.09.2023 20:04
sob This is the coefficient of $2^{-3860}$ in \[ (2^{-1} + 2^{-2} + 2^{-3} + 2^{-4} + 2^{-5} + 2^{-6} + 2^{-10})^{2018} = \left(\frac{2018}{2048}\right)^{2018} \]As such, it follows that the coefficient can be at most the desired result, or the bound is violated.
03.11.2024 16:59
Let $N$ be the coefficient of $x^{3860}$ in $$(x+x^2+x^3+x^4+x^5+x^6+x^{10})^{2018}.$$Note that $$Nx^{3860} < (x+x^2+x^3+x^4+x^5+x^6+x^{10})^{2018}$$for all positive $x$. If $x=\frac{1}{2}$, the conclusion follows.