Happy Thanksgiving! Please note that there are no classes November 25th-December 1st.

MIT PRIMES/Art of Problem Solving

CROWDMATH 2021: Extremal combinatorics

a
p
Extremal Combinatorics J
Asymptotically Optimal Construction for General C
j B k k N
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
EdwinNational
36 posts
#1
This topic is linked to equalsn.
Y by
We give an explicit construction with $n$ letters $1, 2, \ldots n$, and show that it has leading constant $\frac{1}{2}$:
Note: $S_x$ is a sequence $S$ repeated $x$ times. We call each $S$ in the construction a $\textit{snippit}$.
Construction

Proof that the construction works
This post has been edited 1 time. Last edited by EdwinNational, Jan 30, 2021, 5:02 AM
Reason: forgot to say what x was in the construction
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
penrose43
26 posts
#2 • 1 Y
Y by Mango247
Quote:
The sequence itself has length ${n \choose 2}(2x)$

Isn't the length of the sequence half that since we have ${n \choose 2}$ pairs and each pair is repeated $x$ times?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
EdwinNational
36 posts
#3
Y by
Quote:
Isn't the length of the sequence half that since we have ${n \choose 2}$ pairs and each pair is repeated $x$ times?
Each pair has length $2$ because it has two letters(so a pair $ij$ repeated $x$ times should have length $2x$).
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
penrose43
26 posts
#4
Y by
Ohh, right! My bad. That looks like it works then! :)
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
JGeneson
1096 posts
#5
Y by
EdwinNational wrote:
We give an explicit construction with $n$ letters $1, 2, \ldots n$, and show that it has leading constant $\frac{1}{2}$:
Note: $S_x$ is a sequence $S$ repeated $x$ times. We call each $S$ in the construction a $\textit{snippit}$.
Construction

Proof that the construction works
penrose43 wrote:
Ohh, right! My bad. That looks like it works then! :)

This does not work. Look at the letters $n-1$ and $n$. Their alternation has length $2x+2(n-2)$ in this construction.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
LoneShadow379
1 post
#6
Y by
You haven't counted the (1,i), (2,i), (3,i)... terms - for instance, (2,i) would come between (1,j) and (2,j) and thus contribute to the alternating sequence
Z K Y
N Quick Reply
G
H
=
Page Feed | J
Linked Item Topics
G
Topic
First Poster
Last Poster
H
Asymptotically Optimal Construction for General C
EdwinNational   5
N Jul 13, 2022 by LoneShadow379
We give an explicit construction with $n$ letters $1, 2, \ldots n$, and show that it has leading constant $\frac{1}{2}$:
Note: $S_x$ is a sequence $S$ repeated $x$ times. We call each $S$ in the construction a $\textit{snippit}$.
Construction

Proof that the construction works
5 replies
EdwinNational
Jan 30, 2021
LoneShadow379
Jul 13, 2022
J
No more topics!
H
J
H
Asymptotically Optimal Construction for General C
EdwinNational   5
N Jul 13, 2022 by LoneShadow379
We give an explicit construction with $n$ letters $1, 2, \ldots n$, and show that it has leading constant $\frac{1}{2}$:
Note: $S_x$ is a sequence $S$ repeated $x$ times. We call each $S$ in the construction a $\textit{snippit}$.
Construction

Proof that the construction works
5 replies
EdwinNational
Jan 30, 2021
LoneShadow379
Jul 13, 2022
J