Maths Olympiad Prep

Library / /103 of 520

Combinatorics Difficulty 6.5 National olympiad Find the answer

Let SS be a string of 9999 characters, 6666 of which are AA and 3333 are BB. We call SS [i]good[/i] if, for each nn such that 1n991\le n \le 99, the sub-string made from the first nn characters of SS has an odd number of distinct permutations. How many good strings are there? Which strings are good?

A number or a short expression. Spacing and $ signs are ignored.

Solution

1. Lemma Proof:
We need to prove that for all i{1,2,,2n1}i \in \{1, 2, \dots, 2^n - 1\}, (2ni){2^n \choose i} is even.

By Lucas' Theorem, for any non-negative integers mm and nn and a prime pp, the binomial coefficient (mn){m \choose n} modulo pp can be determined by the base-pp representations of mm and nn. Specifically,
(mn)j=0k(mjnj)(modp) {m \choose n} \equiv \prod_{j=0}^k {m_j \choose n_j} \pmod{p}
where m=mkmk1m0m = m_k m_{k-1} \cdots m_0 and n=nknk1n0n = n_k n_{k-1} \cdots n_0 are the base-pp representations of mm and nn, respectively.

For p=2p = 2, m=2nm = 2^n, and ii, we have:
(2ni)j=0n1(1ij)(mod2) {2^n \choose i} \equiv \prod_{j=0}^{n-1} {1 \choose i_j} \pmod{2}
where i=in1in2i0i = i_{n-1} i_{n-2} \cdots i_0 is the binary representation of ii.

Since (10)=1{1 \choose 0} = 1 and (11)=1{1 \choose 1} = 1, but (1ij)=0{1 \choose i_j} = 0 for ij>1i_j > 1, it follows that:
(2ni)0(mod2) {2^n \choose i} \equiv 0 \pmod{2}
for any ii that is not a power of 2. Therefore, (2ni){2^n \choose i} is even for all i{1,2,,2n1}i \in \{1, 2, \dots, 2^n - 1\}.

2. Application to the Problem:
We need to determine the number of good strings SS of length 99 with 66 AA's and 33 BB's such that for each nn (where 1n991 \leq n \leq 99), the substring made from the first nn characters of SS has an odd number of distinct permutations.

The number of distinct permutations of a substring of length nn with bb BB's is given by (nb){n \choose b}. For this to be odd, (nb){n \choose b} must be odd.

3. Analysis of Substrings:
- For n=64n = 64, the substring must have 0 BB's because (64x){64 \choose x} is even for any x{1,2,,33}x \in \{1, 2, \dots, 33\}. Thus, the first 64 characters must all be AA's.
- For n=65n = 65, the substring must have 1 BB because (651)=65{65 \choose 1} = 65 is odd.
- For n=66n = 66, the substring must have 1 BB because (661)=66{66 \choose 1} = 66 is even, so the 66th character must be AA.
- For n=67n = 67, the substring must have 2 BB's because (672){67 \choose 2} is odd.
- For n=68n = 68, the substring must have 2 BB's because (682){68 \choose 2} is even, so the 68th character must be AA.

Continuing this pattern, we find that the string must have the form:
A64BABABBAB A^{64} B A B A B \cdots B A B
where the first 64 characters are AA's, followed by alternating BB's and AA's.

4. Conclusion:
The only good string that satisfies the conditions is:
A64BABABBAB A^{64} B A B A B \cdots B A B

The final answer is A64BABABBAB \boxed{ A^{64} B A B A B \cdots B A B }

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.