olymmath

IMO 2019 Problem 3

A social network has 20192019 users, some pairs of whom are friends. Whenever user AA is friends with user BB , user BB is also friends with user AA . Events of the following kind may happen repeatedly, one at a time:

  • Three users AA , BB , and CC such that AA is friends with both BB and CC , but BB and CC are not friends, change their friendship statuses such that BB and CC are now friends, but AA is no longer friends with BB , and no longer friends with CC . All other friendship statuses are unchanged.

Initially, 10101010 users have 10091009 friends each, and 10091009 users have 10101010 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

Dataset text AI-MO AoPS. Quoted with source.

Official text: IMO 2019 official English paper, page 1.

Also ISL 2019 C5.

Solutions

Official solution Solution 1 by the IMO Problem Selection Committee

The terms of the source let olymmath link to this solution but not copy it. Read the solution (IMO official site).

Similar problems

These problems have the most words in common with this statement.

Locator imo/2019/p3 · Tag SWY1DN3VKW · Edit this page on GitHub · Keys: j next, k previous