Problem

Source: BdMO 2022 Secondary P7

Tags: combinatorics



Sabbir noticed one day that everyone in the city of BdMO has a distinct word of length $10$, where each letter is either $A$ or $B$. Sabbir saw that two citizens are friends if one of their words can be altered a few times using a special rule and transformed into the other ones word. The rule is, if somewhere in the word $ABB$ is located consecutively, then these letters can be changed to $BBA$ or if $BBA$ is located somewhere in the word consecutively, then these letters can be changed to $ABB$ (if wanted, the word can be kept as it is, without making this change.) For example $AABBA$ can be transformed into $AAABB$ (the opposite is also possible.) Now Sabbir made a team of $N$ citizens where no one is friends with anyone. What is the highest value of $N.$