Problem 1501

1. **Define $S(n, m)$ and $P(n, m)$:**
Let $S(n, m)$ be the number of sequences of length $n$ consisting of $0$ and $1$ in which there exists a $0$ in any consecutive $m$ digits. Let $P(n, m)$ denote the number of sequences of length $n$ that contain at least one block of $m$ consecutive $1$'s.

2. **Relationship between $S(n, m)$ and $P(n, m)$:**
Clearly, $S(n, m) = 2^n - P(n, m)$. This is because $2^n$ is the total number of sequences of length $n$ consisting of $0$ and $1$, and $P(n, m)$ is the number of sequences that do not satisfy the condition of having a $0$ in any consecutive $m$ digits.

3. **Counting $P(n, m)$:**
The elements of $P(n, m)$ can be divided into disjoint sets as follows: $P_i \subset P$ where the elements of $P_i$ contain their first block of $m$ consecutive $1$'s 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|$.

4. **Counting $|P_i|$:**
By an easy counting argument, $|P_i| = 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$.

5. Prove the inequality:
We need to prove that
$$S(2015n, n) \cdot S(2015m, m) \ge S(2015n, m) \cdot S(2015m, n)$$
Using the relationship $S(n, m) = 2^n - P(n, m)$, we can rewrite the inequality in terms of $P(n, m)$:
$$(2^{2015n} - P(2015n, n)) \cdot (2^{2015m} - P(2015m, m)) \ge (2^{2015n} - P(2015n, m)) \cdot (2^{2015m} - P(2015m, n))$$

6. Simplify the inequality:
Expanding both sides, we get:
$$2^{2015n + 2015m} - 2^{2015n}P(2015m, m) - 2^{2015m}P(2015n, n) + P(2015n, n)P(2015m, m) \ge 2^{2015n + 2015m} - 2^{2015n}P(2015m, n) - 2^{2015m}P(2015n, m) + P(2015n, m)P(2015m, n)$$

7. Cancel common terms:
$$- 2^{2015n}P(2015m, m) - 2^{2015m}P(2015n, n) + P(2015n, n)P(2015m, m) \ge - 2^{2015n}P(2015m, n) - 2^{2015m}P(2015n, m) + P(2015n, m)P(2015m, n)$$

8. Rearrange the terms:
$$P(2015n, n)P(2015m, m) - P(2015n, m)P(2015m, n) \ge 2^{2015n} (P(2015m, n) - P(2015m, m)) + 2^{2015m} (P(2015n, m) - P(2015n, n))$$

9. **Use the fact that $P(n, k) < P(n, l)$ when $k < l$:**
Since $P(n, k) < P(n, l)$ when $k < l$, we have $P(2015m, n) > P(2015m, m)$ and $P(2015n, m) > P(2015n, n)$. Therefore, the right-hand side of the inequality is non-negative, and the inequality holds.

$\blacksquare$