37th Iranian Mathematical Olympiad

Let the answer be $f(n,k)$. We will prove by induction on $n+k$ that $$f(n,k)=\sum _{i=0}^{k-1}\left(\genfrac{}{}{0ex}{}{n}{i}\right).$$ Case $n=k=1$ is obvious.

Assume that $S$ is the maximum set of the desired sequences and let $T$ be the set of all binary sequences of length $n-1$. Define the sets $A,B,C$ as follows: $$\begin{array}{rl}A& =\{a\in T\mid \text{there exists }b\in S\text{ with }b=\overline{0a},\text{ but there is no }c\in S\text{ with }c=\overline{1a}\}\\ B& =\{a\in T\mid \text{there exists }b\in S\text{ with }b=\overline{1a},\text{ but there is no }c\in S\text{ with }c=\overline{0a}\}\\ C& =\{a\in T\mid \text{there exists }b,c\in S\text{ with }b=\overline{0a},c=\overline{1a}\}.\end{array}$$ Clearly, $f(n,k)=|A|+|B|+2|C|$. Because we can't choose $k$ bits from the last $n-1$ bits of the sequences that produce all the binary sequences of length $k$, we have $|A|+|B|+|C|\le f(n-1,k)$. Now consider the set $C$. If $|C|\ge f(n-1,k-1)$, we can fix $k-1$ bits from the last $n-1$ bits to produce all sequences of length $k-1$. So because of the definition of $C$, by fixing these $k-1$ bits and the first bit, all sequences of length $k$ are produced, which is a contradiction. So we have $$f(n,k)=|A|+|B|+2|C|\le f(n-1,k)+f(n-1,k-1).$$ By induction and using Pascal's identity we get $$\begin{array}{rl}f(n,k)& \le \sum _{i=0}^{k-1}\left(\genfrac{}{}{0ex}{}{n-1}{i}\right)+\sum _{i=0}^{k-2}\left(\genfrac{}{}{0ex}{}{n-1}{i}\right)\\ & =1+\sum _{i=1}^{k-1}\left(\genfrac{}{}{0ex}{}{n-1}{i}\right)+\sum _{i=0}^{k-2}\left(\genfrac{}{}{0ex}{}{n-1}{i}\right)\\ & =1+\sum _{i=1}^{k-1}\left(\left(\genfrac{}{}{0ex}{}{n-1}{i}\right)+\left(\genfrac{}{}{0ex}{}{n-1}{i-1}\right)\right)\\ & =\left(\genfrac{}{}{0ex}{}{n}{0}\right)+\sum _{i=1}^{k-1}\left(\genfrac{}{}{0ex}{}{n}{i}\right)=\sum _{i=0}^{k-1}\left(\genfrac{}{}{0ex}{}{n}{i}\right).\end{array}$$ For the equality example, simply choose all binary sequences with at most $k-1$ zeros. This way, by fixing any $k$ bits, the sequence with $k$ zeros will never be produced and we're done. ■