Saudi Arabian Mathematical Competitions, 2015

Note that if the sequence $S$ ends with zero then all digits of $S$ will be zero.

Now suppose that the sequence $S$ ends with one. Let $k$ be the number of $1$'s in $S$ then $1 \leq k \leq 2015$. Let $\alpha = \frac{2015}{k} \geq 1$. We consider the sequence $S_{k} = a_{1} a_{2} \ldots a_{2015}$ where $a_{i} = 1$ if and only if $i \in \{ \lceil \alpha \rceil, \lceil 2 \alpha \rceil, \ldots, \lceil k \alpha \rceil \}$.

One can check that this sequence has exactly $k$ ones and satisfies all the given conditions.

Now we need to prove that those are all possible sequences.

Suppose that $S$ is a sequence with exactly $k$ ones and also satisfying all the given conditions. We will show that we have only one possible arrangement for $k$ ones and $(2015 - k)$ zeros.

Let $\beta = \frac{2015 - k}{2015}$. Starting from the right, we will show that for any $1 \leq s \leq 2015$, among the first $s$ rightmost digits, there are exactly $\lfloor \beta s \rfloor$ zeros.

It is clear that the statement holds for $s = 1$ since the rightmost digit is a unit.

Suppose that the statement holds for $s$. We consider two cases.

Case 1. If $\lfloor \beta(s+1) \rfloor = \lfloor \beta s \rfloor + 1$. We need to show that the $(s+1)^{\text{th}}$ rightmost digit of $S$ is zero. Otherwise, it follows that we have exactly $\lfloor \beta(s+1) \rfloor - 1$ in the $(s+1)$ rightmost digits and any $s+1$ consecutive digits, there are at most $\lfloor \beta(s+1) \rfloor$ zeros. We divide the sequence from the right into $t$ segments of length $s+1$ and possibly one leftmost segment of length $s'$ with $0 \leq s' \leq s$.

The number of zeros is at most
$$\begin{aligned} \lfloor \beta(s+1) \rfloor - 1 & + (t-1) \lfloor \beta(s+1) \rfloor + \left\lfloor \beta s' \right\rfloor \\ & \leq \beta \left( t(s+1) + s' \right) - 1 = 2014 - k \end{aligned}$$
which is a contradiction.

Case 2. If $\lfloor \beta(s+1) \rfloor = \lfloor \beta s \rfloor$. We need to show that the $(s+1)^{\text{th}}$ rightmost digit of $S$ is a unit. Otherwise, it follows that for any $s+1$ consecutive digits, there are at least $\lfloor \beta(s+1) \rfloor + 1$ zeros. We divide the sequence from the right into $t$ segments of length $s+1$ and possibly one leftmost segment of length $s'$ with $0 \leq s' \leq s$. Note that in the first $s'$ rightmost digits, we have exactly $\left\lfloor \beta s' \right\rfloor$ zeros. If in the leftmost segment of length $s'$ we have $\left\lfloor \beta s' \right\rfloor + 1$ then the number of zeros is at least
$$t (\lfloor \beta(s+1) \rfloor + 1) + \left\lfloor \beta s' \right\rfloor > \beta ( t(s+1) + s' ) = 2015 - k$$
which is a contradiction.

We deduce that, in each segment of length $s'$ we have exactly $\left\lfloor \beta s' \right\rfloor$ zeros. We divide the sequence into segments of length $s'$ and possible one shorter segment from the left. Using the same argument as in the previous case, we do not have enough zeros, which is again a contradiction.

Therefore, the statement holds for all $1 \leq s \leq 2015$, which implies that for any $0 \leq k \leq 2015$, there exists a unique binary sequence with $k$ units satisfying the given conditions.