Let be a string of characters, of which are and are . We call [i]good[/i] if, for each such that , the sub-string made from the first characters of has an odd number of distinct permutations. How many good strings are there? Which strings are good?
Solution
1. Lemma Proof:
We need to prove that for all , is even.
By Lucas' Theorem, for any non-negative integers and and a prime , the binomial coefficient modulo can be determined by the base- representations of and . Specifically,
where and are the base- representations of and , respectively.
For , , and , we have:
where is the binary representation of .
Since and , but for , it follows that:
for any that is not a power of 2. Therefore, is even for all .
2. Application to the Problem:
We need to determine the number of good strings of length 99 with 66 's and 33 's such that for each (where ), the substring made from the first characters of has an odd number of distinct permutations.
The number of distinct permutations of a substring of length with 's is given by . For this to be odd, must be odd.
3. Analysis of Substrings:
- For , the substring must have 0 's because is even for any . Thus, the first 64 characters must all be 's.
- For , the substring must have 1 because is odd.
- For , the substring must have 1 because is even, so the 66th character must be .
- For , the substring must have 2 's because is odd.
- For , the substring must have 2 's because is even, so the 68th character must be .
Continuing this pattern, we find that the string must have the form:
where the first 64 characters are 's, followed by alternating 's and 's.
4. Conclusion:
The only good string that satisfies the conditions is:
The final answer is