Page 1 of 1

IMO 2019/P3

Posted: Thu Jul 18, 2019 11:02 pm
by tanmoy
A social network has $2019$ users, some pairs of whom are friends. Whenever user $A$ is friends with user $B$, user $B$ is also friends with user $A$. Events of the following kind may happen repeatedly, one at a time:
  • Three users $A$, $B$, and $C$ such that $A$ is friends with both $B$ and $C$, but $B$ and $C$ are not friends, change their friendship statuses such that $B$ and $C$ are now friends, but $A$ is no longer friends with $B$, and no longer friends with $C$. All other friendship statuses are unchanged.
Initially, $1010$ users have $1009$ friends each, and $1009$ users have $1010$ friends each. Prove that there exists a sequence of such events after which each user is friends with at most one other user.

Proposed by Adrian Beker, Croatia

Re: IMO 2019/P3

Posted: Thu Oct 17, 2019 3:05 am
by Ragib Farhat Hasan
GRAPH THEORY... is printed all over this problem as a hint, isn't it?

Re: IMO 2019/P3

Posted: Thu Oct 17, 2019 3:06 am
by Ragib Farhat Hasan
Anyone looking for a classic Graph Theory problem?

Look no further!!!

Re: IMO 2019/P3

Posted: Thu Oct 17, 2019 3:08 am
by Ragib Farhat Hasan
BTW, why haven't anyone responded with their solutions? :?

Re: IMO 2019/P3

Posted: Thu Oct 17, 2019 3:16 am
by Ragib Farhat Hasan
DAMN!!!!!!! This forum has got so dead...

It needs a serious waking call...

Maybe we should consider calling Thanos... to invade this forum. :twisted:

Maybe then the "Avengers" (admins, moderators and former-active members) might turn their focus to this forum, again. :lol:

(P.S: I don't know whether anyone will ever see this, but if in case anyone does, do leave a reply! :D )

Re: IMO 2019/P3

Posted: Tue Nov 12, 2019 8:27 am
by samiul_samin
Ragib Farhat Hasan wrote:
Thu Oct 17, 2019 3:16 am
DAMN!!!!!!! This forum has got so dead...

It needs a serious waking call...

Maybe we should consider calling Thanos... to invade this forum. :twisted:

Maybe then the "Avengers" (admins, moderators and former-active members) might turn their focus to this forum, again. :lol:

(P.S: I don't know whether anyone will ever see this, but if in case anyone does, do leave a reply! :D )
This forum can become alive by new active members .Former active members are now (mostly)engineers.