Problem

Source: Middle European Mathematical Olympiad T-4

Tags: invariant, induction, modular arithmetic, binomial coefficients, combinatorics proposed, combinatorics



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