Let $k\geq 1$ and define $N(k)$ to be the minimal $N$ such that any string $s\in \{1,\ldots,k\}^N$ contains two adjacent blocks such that each is a rearrangement of the other. Estimate $N(k)$.

Erdős originally conjectured that $N(k)=2^k-1$, but this was disproved by Erdős and Bruijn. It is not even known whether $N(4)$ is finite.