portrait portrait
2019/10/08 17:52
高中/數學   
主  題: 出  處:其他
題目難易:

一個有2019名用戶的社交網絡,這些用戶中有些是好友關係。這裡的好友關係是相互的。下述事件在他們中反覆發生,且一段時間內只發生一次:

 

有三個用戶A,B,C,滿足A是B,C的共同好友,但是B,C相互之間不是好友。當事件發生時,B,C成為好友,並且A與B,C同時解除好友關係,其他好友關係保持不變。

 

開始時,有1010個用戶每人有1009個好友,另外的1009個用戶每人有1010個好友。證明:存在一個事件序列,使得其發生之後每個用戶最多有一個好友。

(原作者於 2022/02/07 14:48 重新編輯過)
分享
訂閱
你目前尚未登入,登入後方能觀看解答!
我要登入