INAMO 2022/7 wrote: 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$. First of all, let's just write everything without commas because it's annoying. The answer is $\boxed{2025}$, achieved by considering the following configuration: \begin{align*} A_i &= \underbrace{11 \cdots 1}_{i - 1 \ \text{ones}} \underbrace{00 \cdots 0}_{2023 - i \ \text{zeroes}} \ \text{for } 1 \le i \le 2023 \\ A_{2024} &= \underbrace{1010\cdots10}_{1011 \ 10s} \\ A_{2025} &= \underbrace{0101\cdots01}_{1011 \ 01s} \end{align*}To check that this indeed works, note that any valid operations on $A_{2024}$ and $A_{2025}$ will only change it to themselves and furthermore, all of the $A_i$s have different number of $1$s. It suffices to prove that $n = 2026$ doesn't work. Let us define the following sets for $1 \le i \le 2023$: \[ \mathcal{S}_i = \{ \text{the set of binary strings with } i - 1 \text{ number of ones} \} \]The crucial part of this problem lies on the following fact. Claim. There is a sequence of valid operation transforming any binary string $X \in \mathcal{S}_i$ into $A_i$ as long as $X \notin \{ A_{2024}, A_{2025} \}$. Proof. Note that this is trivial when $i \in \{ 1, 2023 \}$. We'll prove this for $2 \le i \le 2022$. Let us WLOG that $i \ge 1011$ as the case $i < 1011$ is similar (by considering strings of zeroes instead of ones). Consider a contiguous substring of $X$ consisting only of ones, which is of the maximal length $k$. As $1011 \le i \le 2022$ and $X \notin \{ A_{2024}, A_{2025} \}$, we have $k \ge 2$ since the number of ones is greater or equal to number of zeroes (where $k = 1$ in this case forces $X \in \{ A_{2024}, A_{2025} \})$. Note that for $k \ge 2$, we can apply operation as follows: \[ 0 \underbrace{11 \cdots 1}_{k \ \text{ones}} \stackrel{\text{Operation}}{\to} \underbrace{11 \cdots 1}_{k \ \text{ones}} 0 \]Therefore, we can shift all of the $1$s beside $\underbrace{11 \cdots 1}_{k \ \text{ones}}$ to the leftest part of the binary string and we will get $\underbrace{11 \cdots 1}_{\ge k \text{ ones}} X'$ for some binary string $X'$ that starts with a zero. We can thus repeat the process (applying inductive hypothesis essentially, if you need rigor) on $X'$ until you are left with a string of all zeroes -- in which case we already get $A_i$. The only possible cases that might stumble us is when $X'$ is a string of 010101, in which case do the following two operations and apply inductive hypothesis: \[ \textcolor{red}{\underbrace{11 \cdots 1}_{\ell \text{ ones}} 0}10101... \stackrel{\text{Operation}}{\to} \textcolor{blue}{0 \underbrace{11 \cdots 1}_{\ell + 1 \text{ ones}}} 010101... \stackrel{\text{Operation}}{\to} \underbrace{11 \cdots 1}_{\ell + 1 \text{ ones}} 00101...\]and thus you get a string $\underbrace{11 \cdots 1}_{\ell \ \text{ones }} X'$ where $X'$ is not of the form $0101 \cdots$ or $1010 \cdots$. By the above claim, for any $X, Y \notin \{ A_{2024}, A_{2025} \}$, we can transform $X \in \mathcal{S}_i$ into $A_i$, and by reversing the operations, transforming $A_i$ to $Y \in \mathcal{S}_i$. This implies that $n = 2026$ fails, because by Pigeon Hole Principle on any $2024$ binary strings excluding $A_{2024}, A_{2025}$, two of them will lie on the same set $\mathcal{S}_i$ and using the above claim, we are done.

Define $A_x = 1010 \cdots \ \ A_y = 0101\cdots$ Claim. $A_x$ and $A_y$ not related to any other $A_i$ Proof. Notice that every block $A_x$ and $A_y$ that have an unequal number of zeroes and one will always be a palindrome. So, if we flip that block, we will always get the same output of $A_x$ or $A_y$, therefore $A_x$ and $A_y$ are not related to any other $A_i$ Claim. Let $S_{i,j}$ be a set of all $A$ with $i$ number of zeroes and $j$ number of ones. $\forall A_k, A_l \in S_{i,j}, \ A_k$ and $A_l$ are related Proof. (need stronger proof) Notice that it is true for $S_{0,1}, S_{1,0}$. For the sake of induction, said it is true for $S_{i, j-1}$ and $S_{i-1,j}$. Notice that every element of $S_{i,j}$ can be formed by adding 1 to the front or the back to every member of $S_{i,j-1}$ or by adding 0 to the front or the back of every member to $S_{i-1,j}$. So to prove that every member of $S_{i,j}$ are related to the other, we need to prove that there are a member of $S_{i, j-1}$ and $S_{i-1,j}$ that are related or the same after the addition. Let $A_n = 00\cdot0011\cdot11$ and $A_m = 00\cdot0011\cdot11$ such that $A_n \in S_{i,j-1} \ ; \ A_m \in S_{i-1,j}$. Clearly, after addition (call it $A_n'$ and $A_m'$) $A_n' = A_m'$ so both are related. Thus, by induction for all $i, j$, every member $S_{i,j}$ are related to each other. Finishing. Let $A_{i,j}$ be one of the member of $S_{i,j}$. For $k > 2$ we have \[A_{0,k}, A_{1,k-1}, \cdots, A_{k,0}, A_x, A_y\]are not related to each other. So, 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$ is 2025

IndoMathXdZ wrote: Therefore, we can shift all of the $1$s beside $\underbrace{11 \cdots 1}_{k \ \text{ones}}$ to the leftest part of the binary string and we will get $\underbrace{11 \cdots 1}_{\ge k \text{ ones}} X'$ for some binary string $X'$. Repeat the process on $X'$ until you are left with a string of all zeroes -- in which case we already get $A_i$. Ok so you can take the longest continuous block of 1s and shift it left, and in the course of doing so you may run into other blocks of 1s and this block will only get bigger and bigger, and finally this block will end up at the left. But what about blocks of ones to the right of that? So say you have 001100110011....1010101

hendrata01 wrote: Ok so you can take the longest continuous block of 1s and shift it left, and in the course of doing so you may run into other blocks of 1s and this block will only get bigger and bigger, and finally this block will end up at the left. But what about blocks of ones to the right of that? So say you have 001100110011....1010101 As said above, after you run out of blocks of $1$s -- all of these $1$s and all the $1$s in its left will end up to the leftest part, from which you will have $\underbrace{11 \cdots 1}_{\ge k \text{ ones}} X'$. Repeat this process on $X'$ (and by this I mean anything after the long contiguous sequence of 1 in the beginning, so $X'$ should start with a 0) and by repeat what I meant was essentially applying the "inductive hypothesis". Indeed, this need some further clarification if the remaining string is of the form $0101 \cdots$ or $1010 \cdots$, in which case do the following two operations and apply inductive hypothesis. \[ \textcolor{red}{\underbrace{11 \cdots 1}_{\ell \text{ ones}} 0}10101... \stackrel{\text{Operation}}{\to} \textcolor{blue}{0 \underbrace{11 \cdots 1}_{\ell + 1 \text{ ones}}} 010101... \stackrel{\text{Operation}}{\to} \underbrace{11 \cdots 1}_{\ell + 1 \text{ ones}} 00101...\]and thus you get a string $\underbrace{11 \cdots 1}_{\ell \ \text{ones }} X'$ where $X'$ is not of the form $0101 \cdots$ or $1010 \cdots$.

As the above posts stated, it suffices to prove that $n=2026$ doesn't work. If $A_i$ is related to $A_j$, we can say that $A_i\sim A_j$. It's easy to see that $A_i \sim A_j$ is equivalent to $A_j \sim A_i$ because we can reverse the iterations that are used to transform $A_i$ to $A_j$ and use it to transform $A_j$ to $A_i$. Claim 1. For every index $i\not= j$, if $A_i\sim B$ for some arbitrary binary sequence $B$. Then, $A_i \sim A_j$ iff $A_j \sim B$. Proof. If $A_j \sim B$, there exist a finite number of moves to transform $A_j$ to $B$ and then to $A_i$. Implying $A_i \sim A_j$, we can prove the case for $A_i \sim A_j$ by using the same argument. Claim 2. Define $B_i$ be the set of binary sequences consisted of $i-1$ zeroes and $2023-i$ ones for all $i \in \mathbb{N}_{\le2022}$ excluding $\underbrace{1,0,1,0,\cdots 1,0}_{1011 \ 10s}$ and $\underbrace{0,1,0,1,\cdots 0,1}_{1011 \ 01s}$. Then, all of the binary sequences on $B_i$ are related to each other. Proof. By the first claim, it suffices to provide a "system" such that that we can change all the sequences on $B_i$ to $\underbrace{0,0,\cdots, 0}_{i-1\ 0s}, \underbrace{1,1,\cdots, 1}_{2023-i \ 1s}$. Let an integer $k\ge2$ be the maximum number of consecutives zeroes on a string of a binary sequences with exactly $1$ one on the left end side, now the we will set such a "system". Do such an iteration on the binary sequences until the we can't find such $k$, $$1,\underbrace{0,0,\cdots,0}_{k \ 0s} \Rightarrow \underbrace{0,0,\cdots,0}_{k \ 0s},1$$Which means we will stumble upon a sequence formed by consecutives zeroes and a string of $1,0,1\cdots$ respectively. But we can do such an iteration, $$\underbrace{0,0,\cdots ,0,1}_{\text{Before}},0,1,0,\cdots \Rightarrow \underbrace{1,0,\cdots ,0,0}_{\text{After}},0,1,0,\cdots$$And then, we can continue doing the iteration before. After a finite number of iterations, we will have the desired result. By Pigeonhole Principle, we are finished.