MathDB
Problems
Contests
International Contests
International Olympiad of Metropolises
2019 IOM
2
2
Part of
2019 IOM
Problems
(1)
Hacking the social network
Source: International Olympiad of Metropolises 2019 P2
9/3/2019
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
m
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
m
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
combinatorics
Kvant