IMO 2019 zadatak 3
Kvaliteta:
Avg: 0,0Težina:
Avg: 0,0Neka društvena mreža ima korisnika i neki parovi korisnika su prijatelji. Ako je
prijatelj korisniku
, onda je i
prijatelj korisniku
. Sljedeći događaji mogu se ponavljati jedan za drugim, ali ne istovremeno:
Tri korisnika ,
i
, takva da su
i
prijatelji korisniku
, ali
i
nisu prijatelji, mijenjaju svoje statuse prijateljstava tako da su
i
sada prijatelji, ali
više nije prijatelj korisniku
, niti korisniku
. Svi ostali statusi prijateljstava ostaju nepromijenjeni.
Na početku, korisnika ima po
prijatelja i
korisnika ima po
prijatelja. Dokaži da postoji niz opisanih događaja nakon kojega svaki korisnik ima najviše jednog prijatelja.
Izvor: Međunarodna matematička olimpijada 2019, problem 3