Friends From BdMO


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 one's 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 even 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\)?


Proof Based Problems  


  0 Upvote                    0 Downvote


Solution

Disclaimer: The solutions we've shared are just one exciting approach, and there are surely many other wonderful methods out there. We’d love to hear your alternative solutions in the community thread below, so let's keep the creativity flowing!

For a word, call the person who has that word its $owner$.

There are 10 letters in each word and 2 ways to choose each of them.

So, the total number of word is $2^{10}$.

We will divide these words into a few $friendly~groups$ such that if two words are in the same group, their $owner$s are friends i.e. the words can be changed from 1 to another.

And, if two words are in different $friendly~groups$, it is not possible to change one of them to the other. So, their $owner$s are not friends.


Now, if $N$ has 2 person from the same $friendly~group$, they will know each other which is not allowed.

Again, if $N$ does not have any person from a $friendly~group$, adding one person from that $friendly~group$ to $N$ will not violate the rules but increase the number of people in the group.

So, the highest number of persons in $N$ is the number of friendly groups.


Defining the process $'lefting'$

Take a word, choose a $ABB$ and turn it into $BBA$ until its not possible,

After the process, in the word we get, all pairs of $B$ are on the leftmost side and single $B$ ($ABA$) are in the rest of the word.

Example: 

$AAABBABBBA \rightarrow AABBAABBBA $

$\rightarrow ABBAAABBBA \rightarrow BBAAAABBBA $

$\rightarrow BBAAABBABA \rightarrow BBAABBAABA $

$\rightarrow BBABBAAABA \rightarrow BBBBAAAABA$.

Call the last word $'lefted'$ version of the first word.

Claim: Each $friendly~group$ has an unique $'lefted'$ word and all $'lefted'$ words are assigned to an $friendly~group$. (I.e. there is a bijection between the $friendly groups$ and $lefted$ words.)

Step 1:

if two words are in different groups, they have different $lefted$ words. If it is not true, it will be possible to go from one of them to the other which should not be possible.

Step 2: 

if two words are in the same group, they have the same $lefted$ word. This is because two different $lefted$ words are not interchangeable.

Step 3:

all $lefted$ words are assigned. All the $friendly group$s combined has all 1024 words and the $lefted$ ones are part of that. So, the $lefted$ word is assigned to the $friendly~group$ it is in.

So, the number of $friendly~group$ is the number of $lefted$ words.


Call a word that has all its $B$ isolated, i.e. it doesn't have any pairs of $B$ a $single$ word.

For an integer $n$, let

$l(n) =$ The number of $lefted$ words of length $n$.

$s(n) =$ The number of $single$ words of length $n$.

We need $l(10)$.

Claim: $s(n) = s(n-1)+s(n-2)$

Proof: Take a $single$ word of length $n-1$ and add a $A$ to its left. All $single$ words of length $n$ starting with $A$ are in this part.

Take a $single$ word of length $n-2$ and add a $BA$ to its left. All $single$ words of length $n$ starting with $B$ are in this part.

They start with different letters so there is no overcount.

Also all words start with either $A$ or $B$ so they all are counted.

Claim: $l(n) = l(n-1) + s(n-1)$

Proof: Take a $lefter$ word of length $n-1$ and add a $B$ to its left. All $lefted$ words of length $n$ starting with $B$ are in this part.

Take a $single$ word of length $n-1$ and add a $A$ to its left. All $single$ words of length $n$ starting with $A$ are in this part. (Because if the primary word were not single, after adding the $A$, it could be $lefted$ and so the new word would not be a $lefted$ word.)

They start with different letters so there is no overcount.

Also all words start with either $A$ or $B$ so they all are counted.

For the counting part:

So, the answer is 232

This is a proof based problem added for learning purposes and does not accept submissions.

You can view the solution by clicking on the solution tab.