Combination problem [closed]

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$.