# Difference between revisions of "2019 IMO Problems/Problem 3"

(Created page with "== Problem == A social network has <math>2019</math> users, some pairs of whom are friends. Whenever user <math>A</math> is friends with user <math>B</math>, user <math>B</mat...") |
(→Problem) |
||

Line 3: | Line 3: | ||

Three users <math>A</math>, <math>B</math>, and <math>C</math> such that <math>A</math> is friends with both <math>B</math> and <math>C</math>, but <math>B</math> and <math>C</math> are not friends, change their friendship statuses such that <math>B</math> and <math>C</math> are now friends, but <math>A</math> is no longer friends with <math>B</math>, and no longer friends with <math>C</math>. All other friendship statuses are unchanged. | Three users <math>A</math>, <math>B</math>, and <math>C</math> such that <math>A</math> is friends with both <math>B</math> and <math>C</math>, but <math>B</math> and <math>C</math> are not friends, change their friendship statuses such that <math>B</math> and <math>C</math> are now friends, but <math>A</math> is no longer friends with <math>B</math>, and no longer friends with <math>C</math>. All other friendship statuses are unchanged. | ||

Initially, <math>1010</math> users have <math>1009</math> friends each, and <math>1009</math> users have <math>1010</math> friends each. Prove that there exists a sequence of such events after which each user is friends with at most one other user. | Initially, <math>1010</math> users have <math>1009</math> friends each, and <math>1009</math> users have <math>1010</math> friends each. Prove that there exists a sequence of such events after which each user is friends with at most one other user. | ||

+ | |||

+ | =VIDEO SOLUTION = | ||

+ | https://youtu.be/p16MaqdvBQQ |

## Latest revision as of 02:58, 16 September 2020

## Problem

A social network has users, some pairs of whom are friends. Whenever user is friends with user , user is also friends with user . Events of the following kind may happen repeatedly, one at a time: Three users , , and such that is friends with both and , but and are not friends, change their friendship statuses such that and are now friends, but is no longer friends with , and no longer friends with . All other friendship statuses are unchanged. Initially, users have friends each, and users have friends each. Prove that there exists a sequence of such events after which each user is friends with at most one other user.