Европейская математическая олимпиада среди девочек (EGMO) 2012. Великобритания

Mugbook әлеуметтік желісінде шексіз көп адам тіркелген. Кейбір (әртүрлі) жұптар бір-бірімен дос болып тіркелген, бірақ әрбір қолданушының дос саны шектеулі. Әр адамда кем дегенде бір дос бар. (Достық — симметриялы: егер $A$ — $B$-нің досы болса, онда $B$ де — $A$-ның досы.)
   Әр адам өз достарының біреуін ең жақын досы ретінде таңдайды. Егер $A$ — $B$-ны ең жақын досы десе, бұл $B$ де $A$-ны ең жақын досы деп атайды дегенді білдірмейді. Біреуді ең жақын дос деп атаған адам 1-ең жақын дос деп аталады. Жалпы, $n>1$ натурал саны үшін бір адам $n$-ең жақын дос деп аталады, егер ол $(n-1)$-ең жақын дос болып табылатын адам тарапынан ең жақын дос ретінде таңдалса. Кез келген $k$ натурал саны үшін $k$-ең жақын дос болатын адам танымал деп аталады.
   (a) Әрбір танымал адам басқа бір танымал адамның ең жақын досы екенін дәлелдеңіз.
   (b) Егер қолданушылардың дос саны шексіз болуы мүмкін болса, кейбір танымал адам басқа танымал адамның ең жақын досы болмауы мүмкін екенін дәлелдеңіз.