Problem: Let $k > 1$ be a fixed positive integer.
Prove that if $n$ is a sufficiently large positive integer,
there exists a sequence of integers with the following properties:
\begin{itemize}
  \item Each element of the sequence is between $1$ and $n$, inclusive.
  \item For any two different contiguous subsequences of the sequence with
    length between $2$ and $k$ inclusive,
    the multisets of values in those two subsequences is not the same.
  \item The sequence has length at least $0.499n^2$.
\end{itemize}

\end{enumerate}

Solution: For any positive integer $n$,
define an $(n,k)$-good sequence to be a finite sequence of integers
each between $1$ and $n$ inclusive satisfying the
second property in the problem statement.
The problems asks to show that,
for all sufficiently large integers $n$,
there is an $(n,k)$-good sequence of length at least $0.499n^2$.

Fix $k\ge 2$ and consider some prime power $n=p^m$ with $p>k+1$. Consider some $0 < g < \frac{n}{k}-1$ with $\gcd (g, n)=1$ and let $a$ be the smallest positive integer with $g^a \equiv \pm 1\pmod n$.

\begin{claim*}
  [Main claim]
  For $k,n,g,a$ defined as above,
  there is an $(n,k)$-good sequence of length $a(n+2)+2$.
\end{claim*}

To prove the main claim,
we need some results about the structure of $\mathbb Z / n\mathbb Z$.
Specifically, we'll first show that any nontrivial arithmetic sequence
is uniquely recoverable.

\begin{lemma*}
  Consider any arithmetic progression of length $i\le k$ whose common difference is relatively prime to $n$, and let $S$ be the set of residues it takes modulo $n$. Then there exists a unique integer $0 < d \le \frac{n}{2}$ and a unique integer $0 \le a < n$ such that \[S = \{ a, a+d, \dots, a+(i-1)d\}.\]
\end{lemma*}

\begin{proof}
  [Proof of lemma]
  We'll split into cases, based on if $i$ is odd or not.
  \begin{itemize}
    \ii \textit{Case 1:} $i$ is odd, so $i=2j+1$ for some $j$. Then the middle term of the arithmetic progression is the average of all residues in $S$, which we can uniquely identify as some $u$ (and we know $n$ is coprime to $i$, so it is possible to average the residues). We need to show that there is only one choice of $d$, up to $\pm$, so that $S = \{ u-jd, u-(j-1)d, \dots, u+jd\}$.

    Let $X$ be the sum of squares of the residues in $S$, so we have \[X\equiv (u-jd)^2 + (u-(j-1)d)^2 + \dots + (u+jd)^2 = (2j+1)u^2 + d^2\frac{j(j+1)(2j+1)}{3},\] which therefore implies \[3(X - (2j+1)u^2)(j(j+1)(2j+1))^{-1} \equiv d^2,\] thus identifying $d$ uniquely up to sign as desired.

    \ii \textit{Case 2:} $i$ is even, so $i=2j$ for some $j$. Once again we can compute the average $u$ of the residues in $S$, and we need to show that there is only one choice of $d$, up to $\pm$, so that $S = \{ u-(2j-1)d, u-(2j-3)d, \dots, u+(2j-1)d \}$. Once again we compute the sum of squares $X$ of the residues in $S$, so that \[X \equiv (u-(2j-1)d)^2 + (u-(2j-3)d)^2 + \dots + (u + (2j-1)d)^2 = 2ju^2 + \frac{(2j-1)2j(2j+1)}{3}\] which therefore implies \[3(X-2ju^2) ((2j-1)2j(2j+1))^{-1} \equiv d^2,\] again identifying $d$ uniquely up to sign as desired.
  \end{itemize}

  Thus we have shown that given the set of residues an arithmetic progression takes on modulo $n$, we can recover that progression up to sign. Here we have used the fact that given $d^2 \pmod n$, it is possible to recover $d$ up to sign provided that $n$ is of the form $p^m$ with $p\neq 2$ and $\gcd (d,n)=1$.
\end{proof}

Now, we will proceed by chaining many arithmetic sequences together.

\begin{definition*}
For any integer $l$ between $0$ and $a-1$, inclusive, define $C_l$ to be the sequence $0, g^l, g^l, 2g^l, 3g^l, \dots, (n-1)g^l, (n-1)g^l$ taken $\pmod n$. (This is just a sequence where the $i$th term is $(i-1)g^l$, except the terms $g^l, (n-1)g^l$ is repeated once.)
\end{definition*}

\begin{definition*}
Consider the sequence $S_n$ of residues mod $n$ defined as follows:
\begin{itemize}
  \item The first term of $S_n$ is $0$.
  \item For each $0\le l < a$, the next $n+2$ terms of $S_n$ are the terms of $C_l$ in order.
  \item The next and final term of $S_n$ is $0$.
\end{itemize}
\end{definition*}

 We claim that $S_n$ constitutes a $k$-good string with respect to the alphabet of residues modulo $n$. We first make some initial observations about $S_n$.

\begin{lemma*}
  $S_n$ has the following properties:
  \begin{itemize}
    \item $S_n$ has length $a(n+2)+2$.
    \item If a contiguous subsequence of $S_n$ of length $\le k$ contains two of the same residue $\pmod n$, those two residues occur consecutively in the subsequence.
  \end{itemize}
\end{lemma*}
\begin{proof}
  [Proof of lemma]
  The first property is clear since each $C_l$ has length $n+2$, and there are $a$ of them, along with the $0$s at beginning and end.

  To prove the second property, consider any contiguous subsequence $S_n[i:i+k-1]$ of length $k$ which contains two of the same residue modulo $n$. If $S_n [i:i+k-1]$ is wholly contained within some $C_l$, it's clear that the only way $S_n[i:i+k-1]$ could repeat residues if it repeats one of the two consecutive values $g^l,g^l$ or $(n-1)g^l, (n-1)g^l$, so assume that is not the case.

  Now, it must be true that $S_n[i:i+k-1]$ consists of one contiguous subsequence of the form \[(n-k_1)g^{l-1}, (n-(k_1-1))g^{l-1}, \dots, (n-1)g^{l-1}, (n-1)g^{l-1},\] which are the portions of $S_n[i:i+k-1]$ contained in $C_{l-1}$, and then a second contiguous subsequence of the form \[0, g^l, g^l, 2g^l, \dots, k_2g^l,\] which are the portions of $S_n[i:i+k-1]$ contained in $C_l$, and we obviously have $k_2+k_1=k-3$. For $S_n[i:i+k-1]$ to contain two of the same residue in non-consecutive positions, there would have to exist some $0<u \le k_1, 0<v\le k_2$ with $(n-u)g^{l-1} \equiv vg^l \pmod n$, meaning that $u + gv \equiv 0\pmod n$. But we know since $k_1 + k_2 < k$ that $ 0 < u +gv < k+kg < n$, so this is impossible, as desired.
\end{proof}
Now we can prove the main claim.

\begin{proof}
  [Proof of main claim]
Consider any multiset $M$ of $2\le i\le k$ residues $\pmod n$ which corresponds to some unknown contiguous subsequence of $S_n$. We will show that it is possible to uniquely identify which contiguous subsequence $M$ corresponds to, thereby showing that $S_n$ has no twins of length $i$ for each $2\le i\le k$, and then the result will follow.

First suppose $M$ contains some residue twice. By the last lemma there are only a few possible cases: \begin{itemize}
    \item $M$ contains multiple copies of the residue $0$. In this case we know $M$ contains the beginning of $S_n$, so the corresponding contiguous subsequence is just the first $i$ terms of $S_n$.
    \item $M$ contains multiple copies of multiple residues. By the last lemma and the structure of $S_n$, we can easily see that $M$ must contain two copies of $-g^{i-1}$ and two copies of $g^i$ for some $0 \le i < a$ that can be identified uniquely, and $M$ must contain portions of both $C_{i-1}, C_i$. It follows $M$'s terms can be partitioned into two portions, the first one being  \[-i_1g^{i-1}, -(i_1-1)g^{i-1}, \dots, -g^{i-1}, -g^{i-1},\] and the second one being \[0, g^i, g^i, 2g^i, \dots, i_2 g^i\] for some $i_1,i_2$ with $i_1+i_2 = i-3$, and we just need to uniquely identify $i_1, i_2$. Luckily, by dividing the residues in $M$ by $g^{i-1}$, we know we can partition $M$'s terms into \[-i_1, -(i_1-1), \dots, -1, -1\] as well as \[0, g, g, 2g, \dots, i_2g. \] Now since $i_2g \le kg < n-k$ and $-i_1 \equiv n - i_1 \ge n-k$ it is easy to see that $i_1,i_2$ can be identified uniquely, as desired.
    \item $M$ contains multiple copies of only one residue $g^i$, for some $0\le i < a$ that can be identified uniquely. Then by the last lemma $M$ must be located at the beginning of $C_i$ and possibly contain the last few terms of $C_{i-1}$, so $M$ must be of the form $g^i, g^i, 2g^i, \dots, i_1g^i$, along with possibly the term $0$ or the terms $0, -g^{i-1}$. So when we divide $M$ by $g^{i-1}$ we should be left with terms of the form $g, g, 2g, \dots, i_1g$ along with possibly $0$ or $0,-1$. Since $i_1g \le kg < n-k$, we can easily disambiguate these cases and uniquely identify the contiguous subsequence corresponding to $M$.
    \item $M$ contains multiple copies of only one residue $-g^i$, for some $0 \le i < a$ that can be identified uniquely. Then by the last lemma $M$ must be located at the end of $C_i$ and possibly the first terms of $C_{i + 1}$, so $M$ must be of the form $-g^i, -g^i, -2g^i, \dots, -i_1g^i$, along with possibly the term $0$ or the terms $0, g^{i+1}$. So when we divide $M$ by $g^{i-1}$ we should be left with terms of the form $-1,-1,-2, \dots, -i_1$, along with possibly $0$ or $0, g$. Since $-i_1\equiv n-i_1 \ge \frac{n}{2}$ and $g < \frac{n}{2}$, we can disambiguate these cases and uniquely identify the contiguous subsequence corresponding to $M$.
\end{itemize}
Thus in all cases where $M$ contains a repeated residue, we can identify the unique contiguous subsequence of $S_n$ corresponding to $M$.

When $M$ does not contain a repeated residue, it follows that $M$ cannot contain both of the $g^i$ terms or $(n-1)g^i$ terms at the beginning or end of each $C_i$. It follows that $M$ is either entirely contained in some $C_i$ or contained in the union of the end of some $C_i$ with the beginning of some $C_{i+1}$, meaning $M$ corresponds to a contiguous subsequence of $(-g^i, 0, g^{i+1})$. In the first case, since each $C_i$ is an arithmetic progression when the repeated terms are ignored, Lemma 1 implies that we can uniquely determine the location of $M$, and in the second case, it is easy to tell which contiguous subsequence of $(-g^i, 0, g^{i+1})$ corresponds to $M$.

Therefore, in all cases, for any multiset $M$ corresponding to some contiguous subsequence of $S_n$ of length $i\le k$, we can uniquely identify the contiguous subsequence, meaning $S_n$ is $k$-good with respect to the alphabet of residues modulo $n$, as desired.
\end{proof}

Now we will finish the problem. We observe the following.

\begin{claim*}
Fix $k$ and let $p>k+1$ be a prime. Then for $n=p^2$ we can find a $(n,k)$-good sequence of length $\frac{p(p-1)(p^2+2)}{2}$.
\end{claim*}
\begin{proof}
  [Proof of last claim]
Let $g$ be the smallest primitive root modulo $n=p^2$, so that $a = \frac{p(p-1)}{2}$. As long as we can show that $g < \frac{n}{k}-1$, we can apply the previous claim to get the desired bound.

We will prove a stronger statement that $g<p$. Indeed, consider any primitive root $g_0 \pmod p$. Then $g_0+ap$ has order $p-1$ modulo $p$, so its order modulo $p^2$ is divisible by $p-1$, hence $g_0+ap$ is a primitive root modulo $p^2$ as long as $(g_0+ap)^{p-1}\not\equiv 1\pmod {p^2}$. Now \[(g_0 + ap)^{p-1} = \sum_i g_0^{p-1-i}(ap)^i \binom{p-1}{i} \equiv g_0^{p-1} + g_0^{p-2}(ap) \pmod {p^2}.\] In particular, of the values $g_0, g_0+p, \dots, g_0+p(p-1)$, only one has order $p-1$ and the rest are primitive roots.

So for each $0<g_0<p$ which is a primitive root modulo $p$, either $g_0$ is a primitive root modulo $p^2$ or $g_0$ has order $p-1$ but $g_0+p, g_0+2p, \dots, g_0+p(p-1)$ are all primitive roots. By considering all choices of $g_0$, we either find a primitive root $\pmod {p^2}$ which is between $0$ and $p$, or we find that all residues $\pmod {p^2}$ of order $p-1$ are between $0$ and $p$. But if $\text{ord}_{p^2} (a) = p-1$ then $\text{ord}_{p^2} (a^{-1}) = p-1$, and two residues between $0,p$ cannot be inverses modulo $p^2$ (because with the exception of $1$, they cannot multiply to something $\ge p^2+1$), so there is always a primitive root between $0,p$ as desired.
\end{proof}

Now for arbitrarily large $n$ we can choose $p<\sqrt{n}$ with $\frac{p}{\sqrt{n}}$ arbitrarily close to $1$; by the previous claim, we can get an $(n,k)$-good sequence of length at least $\frac{p-1}{p} \cdot \frac{p^4}{2}$ for any constant, so for sufficiently large $n,p$ we get $(n,k)$-good sequences of length $0.499n^2$.