ELMO 2021 Problem 5

Let $n$ and $k$ be positive integers. Two infinite sequences $\{s_i\}_{i\geq 1}$ and $\{t_i\}_{i\geq 1}$ are equivalent if, for all positive integers $i$ and $j$ , $s_i = s_j$ if and only if $t_i = t_j$ . A sequence $\{r_i\}_{i\geq 1}$ has equi-period $k$ if $r_1, r_2, \ldots$ and $r_{k+1}, r_{k+2}, \ldots$ are equivalent.

Suppose $M$ infinite sequences with equi-period $k$ whose terms are in the set $\{1, \ldots, n\}$ can be chosen such that no two chosen sequences are equivalent to each other. Determine the largest possible value of $M$ in terms of $n$ and $k$ .