Putnam 2018 B6

Art of Problem Solving

AoPS Online

College Math Topics in undergraduate and graduate studies

Topics in undergraduate and graduate studies

3 M G

BBookmark VNew Topic kLocked

College Math Topics in undergraduate and graduate studies

Topics in undergraduate and graduate studies

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Putnam 2018 B6

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3564 posts

62861

#1 h Dec 2, 2018, 10:57 PM • 4 Y

Y by opptoinfinity, megarnie, Adventure10, Mango247

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}.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3564 posts

62861

#2 h Dec 2, 2018, 11:00 PM • 23 Y

Y by acegikmoqsuwy2000, DVDthe1st, yayups, JasperL, arvind_r, Mathphile01, GreenKeeper, pad, abk2015, Idea_lover, adityaguharoy, AnArtist, Vietjung, Daniel_Tau, Mathcollege, mathleticguyyy, franchester, centslordm, gvole, Adventure10, Mango247, aidan0626, Sedro

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.

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3 posts

#3 h Dec 3, 2018, 4:42 AM • 4 Y

Y by Binomial-theorem, Cpi2728, Adventure10, Mango247

This is a nontrivial observation...

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

530 posts

USJL

#4 h Dec 3, 2018, 5:23 AM • 2 Y

Y by Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3564 posts

62861

#5 h Dec 3, 2018, 5:28 AM • 2 Y

Y by Adventure10, Mango247

jonny97 wrote:

This is a nontrivial observation...

I agree; I spent about an hour staring at the problem before observing it

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

530 posts

USJL

#6 h Dec 3, 2018, 5:38 AM • 2 Y

Y by Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

15 posts

#7 h Dec 3, 2018, 5:57 AM • 7 Y

Y by GreenKeeper, jackdoesmath, speck, Mathcollege, tymo, Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

759 posts

#8 h Dec 4, 2018, 8:33 PM • 5 Y

Y by stroller, Adventure10, Mango247, IAmTheHazard, MS_asdfgzxcvb

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6870 posts

#9 h Dec 8, 2018, 5:39 PM • 5 Y

Y by RAMUGAUSS, Aryan-23, v4913, gvole, Adventure10

So, did we ever figure out the significance of $3860$ ?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

20 posts

#10 h Dec 8, 2018, 11:35 PM • 2 Y

Y by Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

223 posts

#11 h Dec 9, 2018, 1:23 AM • 4 Y

Y by 62861, v_Enhance, fclvbfm934, Adventure10

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$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1900 posts

#12 h Jan 5, 2019, 2:41 PM • 2 Y

Y by Adventure10, Mango247

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}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

GeronimoStilton

1521 posts

GeronimoStilton

#13 h May 19, 2020, 2:59 PM • 1 Y

Y by skrublord420

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

883 posts

#14 h May 19, 2020, 3:16 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3217 posts

#16 h Apr 12, 2022, 10:15 PM • 1 Y

Y by centslordm

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1500 posts

#17 h Sep 11, 2023, 5:04 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3177 posts

#18 h Nov 3, 2024, 1:59 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

726 posts

#19 h Mar 10, 2025, 7:51 PM

Y by

DP sol instead of genfunc sol

Attachments:

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1484 posts

#20 h Mar 23, 2025, 8:38 PM • 1 Y

Y by MS_asdfgzxcvb

Mentioning this because it doesn't seem to be explicitly stated in the thread already: This is a standard use of the saddle-point method, so called because it turns out that the following two ideas are essentially equivalent: Given some $f(z)$ analytic at $0$ with non-negative coefficients, we can estimate the coefficient on $z^n$ for some given $n$ by

Plugging in some optimal $0 < \zeta_n$ less than the radius of convergence and ignoring all other terms (e.g. how #13 frames it)
Using the Cauchy integral formula on a circle centered at $0$ through a saddle point of $|f(z)/z^{n+1}|$ on $\mathbb R_{>0}$ and using the Estimation Lemma (e.g. how #7 frames it)

Of course, in the second idea generalizes to non circular contours; see Flajolet Sedgewick VIII.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a