In a social network with a fixed finite setback of users, each user had a fixed set of followers among the other users. Each user has an initial positive integer rating (not necessarily the same for all users). Every midnight, the rating of every user increases by the sum of the ratings that his followers had just before midnight. Let $m$ be a positive integer. A hacker, who is not a user of the social network, wants all the users to have ratings divisible by $m$. Every day, he can either choose a user and increase his rating by 1, or do nothing. Prove that the hacker can achieve his goal after some number of days. Vladislav Novikov
Problem
Source: International Olympiad of Metropolises 2019 P2
Tags: combinatorics, Kvant
03.09.2019 16:38
Straightforward exercise for anyone used to linear algebra Number the persons $1$ through $n$ and consider the $n\times n$ $(0,1)$-matrix given by $A=(a_{ij})_{1\le i,j\le n}$ with $a_{ij}=1$ if $j$ follows $i$ and $0$ otherwise. The main observation is that if in midnight the column vector given by the user's rating is $x$, the next midnight it will be $Ax.$ Let $e_i\in\mathcal{M}_{n,1}$ be the column vector with $1$ in position $i$ and $0$ in all other positions. The hacker can add one $e_i$ to $x$ at midnight, or can do nothing. Let $a_1,a_2,...,a_n$ be the initial user's ratings reduced modulo $m$ and $b_i=m-a_i$ for each $i$. By PHP, there are distinct numbers $p>c_1>c_2>...>c_{b_1+...+b_n}$ such that $A^p\equiv A^{c_j}(\text{mod}~m)$ for any $j$. Then $$(a_i\cdot A^p+A^{c_{b_1+...+b_{i-1}+1}}+....+A^{c_{b_1+....+b_i}})e_i\equiv 0(\text{mod}~m)$$for each $i=\overline{1,n}.$ Thus the hacker can add $e_i$ in midnights $p-c_{b_1+...+b_{i-1}+1},...,p-c_{b_1+....+b_i}$ for each $i$, and by the above it can easily be seen to be enough, since the resulting vector would be $$A^px+\sum_{i=1}^{n}(A^{c_{b_1+...+b_{i-1}+1}}+....+A^{c_{b_1+....+b_i}})e_i=\sum_{i=1}^{n} (a_i\cdot A^p+A^{c_{b_1+...+b_{i-1}+1}}+....+A^{c_{b_1+....+b_i}})e_i\equiv 0(\text{mod}~m).$$
03.09.2019 17:50
Can someone explain me more about what above said?