Problem

Source: Indonesian MO 2022 No 7

Tags: combinatorics, INAMO 2022



Let $A$ be the sequence of zeroes and ones (binary sequence). The sequence can be modified by the following operation: we may pick a block or a contiguous subsequence where there are an unequal number of zeroes and ones, and then flip their order within the block (so block $a_1, a_2, \ldots, a_r$ becomes $a_r, a_{r-1}, \ldots, a_1$). As an example, let $A$ be the sequence $1,1,0,0,1$. We can pick block $1,0,0$ and flip it, so the sequence $1,\boxed{1,0,0},1$ becomes $1,\boxed{0,0,1},1$. However, we cannot pick block $1,1,0,0$ and flip their order since they contain the same number of $1$s and $0$s. Two sequences $A$ and $B$ are called related if $A$ can be transformed into $B$ using a finite number the operation mentioned above. Determine the largest natural number $n$ for which there exists $n$ different sequences $A_1, A_2, \ldots, A_n$ where each sequence consists of 2022 digits, and for every index $i \neq j$, the sequence $A_i$ is not related to $A_j$.