The strategy of the government is as follows: At the first step(year) all the indicators have values equal to $1$. Let $x_i$ be the value of the $i$-th indicator at some step. We say the indicator is allowed to be reset (to make its value iquals $1$) if $x_i\geq \lceil a_i/2 \rceil$. At each step all of the indicators increase by $1$, except an indicator which is allowed to be reset and we make its value equal to $1$. If there are more than one indicator allowed to be reset, we proceed in the following way. We choose the indicator with the smallest max value $a_i$ and reset it. (if again there are two or more of them, we choose randomly one). Let's prove this process will run forever without any indicator exceeding its max value. Arguing by contradiction, suppose after some steps, the $k$-th indicator's value become $a_k+1$. Then there were $a= \lceil a_k/2\rceil$ steps this indicator was allowed for reset, but it wasn't, because some other indicators $j_1,j_2,\dots,j_s$ were reset (perhaps some of them more than once). Notice that $a_k\geq a_{j_i},i=1,2,\dots,s$, that's $a\geq a_{j_i}/2, i=1,2,\dots,s$. For $a$ consecutive steps, the $j_r$ -th indicator could be reset at most $\frac{a}{a_{j_r}/2}$ times. Hence: \[ a \leq \text{ number of resets of } j_1,\dots,j_s \text{ indicators } \leq \sum_{i=1}^{s}\frac{2a}{a_{j_i}}.\]It yields \[\frac{1}{2}\leq \sum_{i=1}^{s} \frac{1}{a_{j_i}}<\sum_{i=1}^{n} \frac{1}{a_i}\]a contradiction with the statement requirement.

Let $a_k=13$ and $a_{j_i}=5$. So a=7. We reset the indicator $j_i$ in the first step (of the 'a' steps) and in the 4. and in 7., so 3 times $\frac{a}{a_{j_i}/2}=\frac{14}{5}$ which is less than 3

If $a_k$ is even, $a= \lceil a_k/2\rceil$ is not ok

@bigs: ok, I see. Thanks for reading the details carefully. Let's fix it. We lift a bit the level, an indicator is allowed for reset. The $i$ -th Indicator is allowed to be reset when $x_i\geq \lceil a_i/2 \rceil+1$. Further, the same argument, as above, goes like: If $k$-th indicator fails, then there were $a=\lfloor a_k/2\rfloor$ steps this indicator was allowed for reset, but it wasn't, because some other indicators $j_1,j_2,\dots,j_s$ were reset. For $a$ consecutive steps, if $a\geq a_{j_r}/2, r=1,2,\dots,s$, the $j_r$ -th indicator could be reset at most $\frac{a}{a_{j_r}/2}$ times. The only case $a<a_{j_r}/2$ is $a_k$ - odd and $a_{j_r}=a_k$. In this case $j_r$ could be reset at most once: $1=\frac{a}{a_{j_r}/2}+1/a_k$. There are at most $a-1$ such cases, since when $a_k$ is odd there can be at most $\lfloor a_k/2\rfloor=a $ indicators with max value $a_k$. Thus, we get: \[ a \leq \text{ number of resets of } j_1,\dots,j_s \text{ indicators } \leq \sum_{i=1}^{s}\frac{2a}{a_{j_i}}+\frac{a-1}{a_k}.\]\[\frac{1}{2}-\frac{a-1}{2a a_k}\leq \sum_{i=1}^{s} \frac{1}{a_{j_i}}\]\[\frac{1}{2}<\frac{1}{2}+\frac{1}{2a a_k}\leq \sum_{i=1}^{s} \frac{1}{a_{j_i}} + \frac{1}{2a_k}< \sum_{i=1}^{s} \frac{1}{a_{j_i}} + \frac{1}{a_k}\]a contradiction.

dear dgrozev I have a problem with your solution. I can't see the proof of your following statement: "For $a$ consecutive steps, if $a\geq a_{j_r}/2, r=1,2,\dots,s$, the $j_r$ -th indicator could be reset at most $\frac{a}{a_{j_r}/2}$ times" thx B

As I see now, the approach in my posts above is clumsy and dirty. Here is another approach, based on a different idea. The problem can be viewed in the following way: We have an infinite table with $n$ rows, each row consists of empty squares starting from square number $0$, and going to infinity. At the beginning all squares $q_{i,0}\,,\,i=1,2,\dots,n$ are checked. We want to check some other squares, complying to the next two rules: $(i)$ There is only one checked square in each column $j, j=1,2,\dots$. $(ii)$ In every row $i,i=1,2,\dots,n$, the number of empty squares between any two consecutive checked squares is less than $a_i$. We will construct an algorithm to implement the job. WLOG suppose $a_1\le a_2\le \dots\le a_n$. We will proceed consecutively on each row, starting from the first one. First, we check the squares $q_{1,j}$ of the first row for $j=1,a_1+1,2a_1+1,\dots$. Suppose we've already finished with the first $k-1$ rows, $1<k\le n$ and let us proceed with $k$-th row. Let $q_{k,\ell}$ be the last checked square in the $k$-th row. We want to put a check somewhere on the set of squares $S:=\{q_{k,\ell+1},q_{k,\ell+2},\dots,q_{k,\ell+a_k}\} $, but complying to the rule $(i)$. For each square in $q\in S$, consider the column of the squares that are above $q$, i.e. all the squares that are in the same column as $q$ and in the rows $1,2,\dots,k-1$. We will prove that at least one of those columns consists of empty squares. For sake of contradiction, suppose it's not true and let's count the number of checked squares that are above $S$. At each row $i=1,2,\dots,k$ there are at most $\left\lfloor\frac{a_k}{a_i}\right\rfloor+1$ checked squares. On the other hand, since there is a checked square above any $q\in S$, the number of the checked squares above $S$ is at least $a_k$. Hence: $$\sum\limits_{i=1}^{k-1}\left(\left\lfloor\frac{a_k}{a_i}\right\rfloor+1 \right)\ge a_k. $$But $2\frac{a_k}{a_i}\geq \left\lfloor\frac{a_k}{a_i}\right\rfloor+1$, since $a_k\geq a_i,i=1,2,\dots,k-1$. Hence: $$2\sum\limits_{i=1}^{k-1}\frac{a_k}{a_i}\ge a_k$$$$\sum\limits_{i=1}^{k-1}\frac{1}{a_i}\ge \frac{1}{2}$$which contradicts with $\sum\limits_{i=1}^{n}\frac{1}{a_n}\le \frac{1}{2}$, since $k-1<n$. Thus, there is a column above some $q\in S$ with all squares empty, hence we can check $q$ and still complying with $(i)$. So, doing it consecutively, we will finish with the row $k$.

dgrozev wrote: At each row $i=1,2,\dots,k$ there are at most $\left\lfloor\frac{a_k}{a_i}\right\rfloor+1$ checked squares. This seems false? Shouldn't there be at least that many squares (what if everything is taken?) We can show that at most $2\left\lceil\frac{a_k}{a_i}\right\rceil$ squares need to be checked by considering blocks of $a_i$ consecutive cells, but this is too weak.

The obvious followup, which I have no answer to: given $c > \frac{1}{2}$, is there always a sequence $a_i$ whose sum of reciprocals is less than $c$ and for which the task is impossible?

Since it seems no one has posted a complete solution yet, this is the official solution pdf to the first day problems: http://2016.megapolis.educom.ru/assets/media/metropolises-2016-math-en-1-solutions.pdf @below oops ,yeah i didn’t see that somehow

Alireza_Amiri wrote: Since it seems no one has posted a complete solution ... The solution in #9 is a complete one. Anyway, thanks for the link!

This is motivated by how you show the Harmonic Series diverges by bounding with power of two denominators. The basic idea is to pretend each $a_i$ is decreased to a power of 2 when figuring out the algorithm for resetting indicators. For $r \geq 1$, let $S_r$ be the set of all $a_i$ with $2^r \leq a_i < 2^{r+1}$. We claim that