There are N advertisement boards of which M consecutive boards should have at least K advertisements. How to find number of ways in which this is possible keeping cost minimum. Eg: N=6,M=3,K=2 which has 6 possible ways: {1 1 0 1 1 0}, {0 1 1 0 1 1}, {0 1 1 1 1 0}, {1 0 1 1 1 0}, {0 1 1 1 0 1}, {1 0 1 1 0 1} [1=Ad,0=No Ad] and when N=3,M=2,K=1 has only 1 possible way: {0,1,0} [since cost should be minimum(use least no of ads)]
N>=M>=K>=1
First, let's deal with the case $N\leq M$. Clearly $K$ advertisements placed in any way will suffice as the minimum cost. There are ${N+K-1 \choose K}$ ways to arrange them in any way.
Now, let's deal with $N > M$.
Hint: Show that you need at least $\lfloor \frac{N}{M} \rfloor K$ advertisements.
Hint: Construct an explicit example to show that $\lfloor \frac{N}{M} \rfloor K$ advertisements is sufficient.
This shows that $\lfloor \frac{N}{M} \rfloor K$ advertisements is the minimum cost.
Let $N_i$ denote the number of advertisements on the $i$th board.
Hint: Show that $N_i = N_{i+M}$, where the indices make sense.
Hint: If $N = mM + d$, then show that $N_1 = N_2 = \ldots N_d = 0 $.
This means that we must place $K$ advertisements in the remaining $M-d$ spots.
Hint: Show that any arrangement of $K$ advertisements into these $M-d$ spots will work.
Hint: Show that there are thus ${M-d+K -1 \choose K}$ ways to arrange them.
With $N=3, M=2, K=1$, we get $d=1$, and the answer of ${2-1+1-1 \choose 1} = 1$.
