Friends From BdMO

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