In Happy City there are $2014$ citizens called $A_1, A_2, \dots , A_{2014}$. Each of them is either happy or unhappy at any moment in time. The mood of any citizen $A$ changes (from being unhappy to being happy or vice versa) if and only if some other happy citizen smiles at $A$. On Monday morning there were $N$ happy citizens in the city. The following happened on Monday during the day: the citizen $A_1$ smiled at citizen $A_2$, then $A_2$ smiled at $A_3$, etc., and, finally, $A_{2013}$ smiled at $A_{2014}$. Nobody smiled at anyone else apart from this. Exactly the same repeated on Tuesday, Wednesday and Thursday. There were exactly $2000$ happy citizens on Thursday evening. Determine the largest possible value of $N$.
Problem
Source: Middle European Mathematical Olympiad T-4
Tags: invariant, induction, modular arithmetic, binomial coefficients, combinatorics proposed, combinatorics
21.09.2014 18:16
Suppose every unhappy citizen carries a $0$ and every happy citizen carries a $1$ initially. When $A$ smiles to $B$, the number that $B$ carries is added by the number that $A$ carries. Then we can see the invariant that every happy citizen carries an odd number and every unhappy citizen carries an even number. Thus replace the citizen $A_c$ on the evening of day $d$ by the number they carry $a_{d,c}$. It follows that if $A_i$ is a happy citizen, $a_{0,i} = 1$, otherwise $a_{0,i} = 0$. Also note that our construction means $a_{d,c} = a_{d,c-1} + a_{d-1,c}$ for all $d \ge 1, c \in [2,2014]$, since when $A_{c-1}$ smiles to $A_c$, $A_{c-1}$ won't get a smile from anyone else for the day and thus they are carrying the number $a_{d,c-1}$, and $A_c$ hasn't got a smile from anyone else for the day and thus they are carrying the number $a_{d-1,c}$, and $A_c$ won't get a smile from anyone else for the day and thus the number they will carry at the end of the day becomes $a_{d,c}$ by definition. We can prove that $a_{d,c} = \sum_{i=1}^c \binom{c-i+d-1}{d-1} a_{0,i}$ for all $d \ge 1, c \in [1,2014]$ by double induction on $d$, then on $c$ inside. The proof is simple but a bit messy with adding binomial coefficients and I'm not in the mood of listing its steps; this is left for the reader. Thus $a_{4,c} = \sum_{i=1}^c \binom{c-i+3}{3} a_{0,i}$ for all $c \in [1,2014]$. Note that we're only concerned with its parity, so we can remove any term whose binomial coefficient is even, and cancel the binomial coefficient if it's odd. Observe that $\binom{c-i+3}{3} = \dfrac{(c-i+3)(c-i+2)(c-i+1)}{6}$, and thus the only way it can be odd is if $c-i \equiv 0 \pmod 4$. In other words, $a_{d,c} \equiv \sum_{i=0}^{\text{as large as possible}} a_{0,c-4i} \pmod 2$; we only take $a_{0,c}$, then 4 steps before it $a_{0,c-4}$, then 4 steps before it $a_{0,c-8}$, and so on, until the index goes out of bounds. So we can treat each index modulo 4 separately. Group the citizens $A_i$ together if they have the same remainder modulo 4. Note that $a_{4,i+4} \equiv a_{0,i+4} + (a_{0,i} + a_{0,i-4} + \ldots) \equiv a_{0,i+4} + a_{4,i} \pmod 2$, so if $A_{i+4}$ was happy at the beginning, then $A_i$ and $A_{i+4}$ have different happiness at the end. Thus the number of happy people among $A_1, A_5, \ldots, A_{2013}$ in the beginning determines the number of times the happiness of people in the chain $A_1, A_5, \ldots, A_{2013}$ changes at the end, and similarly with the other three groups. Since there are $2000$ happy people at the end, we have $2014-2000 = 14$ unhappy people and so at most $2 \cdot 14 = 28$ happiness changes. However, since $A_1, A_2, A_3, A_4$ can start happy without affecting the number of happiness changes, we can have at most $28+4 = \boxed{32}$ happy people in the beginning. This is so convoluted that I'm sure I can rephrase this better somehow, but that's the general idea.