Let $m, n$ be positive integers. Let $S(n,m)$ be the number of sequences of length $n$ and consisting of $0$ and $1$ in which there exists a $0$ in any consecutive $m$ digits. Prove that \[S(2015n,n).S(2015m,m)\ge S(2015n,m).S(2015m,n)\]
Problem
Source: Turkey TST 2015
Tags: Turkey, TST, combinatorics, algebra, Set partition
15.04.2015 17:21
Let $P(n,m)$ denote the number of strings in which there exists atleast one block of m 1's (let $P$ be the set of all such elements).Clearly $S(n,m)=2^{n}-P(n,m)$. We shall count $P(n,m)$. Note that the elements of $P$ can be divided into disjoint sets as follows:$P_i \subset P$ and the elements of $P_i$ contain their first block of m consecutive 1's from left starting from the (i+1)th position and ending in the (i+m)th position.Clearly $|P|=\sum_{i=0}^{n-m-1}{|P_i|}$.Now by easy counting argument $P_i(n,m)=2^{n-m-1}-2^{n-k-m}P(i-1,m)$.Thus $P(n,m)=(n-m+1)2^{n-m-1}-\sum_{k=0}^{n-m}{2^{n-k-m}P(k-1,m)}$. with $P(-1,m)=1$ Thus we get $S(n,m)$ from here and now its a calculative argument with equality when $m=n$.(use the trivial facts that $P(n,k)<P(n,l)$ when $k<l$ etc
16.12.2018 17:33
Here is my way to calculate $S(n,m)$: