Ðề tài: Đề thi IMO 2019
Xem bài viết đơn
Old 17-07-2019, 01:40 AM   #4
chemthan
Administrator

 
chemthan's Avatar
 
Tham gia ngày: Mar 2009
Bài gởi: 349
Thanks: 0
Thanked 308 Times in 161 Posts
Trích:
Nguyên văn bởi hung.vx View Post
Đề thi IMO 2019

Bài 3: Một mạng xã hội có $ 2019 $ người dùng với một số cặp là bạn bè. Nếu người dùng $ A $ là bạn bè với người dùng $ B $ thì người dùng $ B $ cũng là bạn bè với người dùng $ A $. Các sự kiện thuộc loại sau đây có thể xảy ra lặp đi lặp lại, từng lần một: Ba người dùng $ A $, $ B $ và $ C $ sao cho $ A $ là bạn bè với cả $ B $ và $ C $, nhưng $ B $ và $ C $ không phải là bạn bè, hãy thay đổi trạng thái tình bạn của họ sao cho $ B $ và $ C $ là bạn bè, nhưng $ A $ không còn là bạn với $ B $ và không còn là bạn với $ C $. Tất cả các trạng thái tình bạn khác là không thay đổi.
Ban đầu, có $ 1010 $ người dùng mà mỗi người dùng có đúng $ 1009 $ bạn và $ 1009 $ người dùng còn lại mà mỗi người có đúng $ 1010 $ bạn. Chứng minh rằng tồn tại một chuỗi các sự kiện như vậy mà sau đó mỗi người dùng là bạn với nhiều nhất một người dùng khác.
Trước hết ta chỉ chuyển trạng thái mà số thành phần liên thông của đồ thị không thay đổi. Xét trạng thái mà tại đó không thể chuyển tiếp trạng thái mà giữ nguyên số thành phần liên thông. Nếu tồn tại một "cycle" thì thành phần liên thông chứa nó phải là một "clique" hoặc nó chỉ chứa đúng cycle đó. Điều này là không thể vì ban đầu các thành phần liên thông không phải là một "clique" và tồn tại đỉnh bậc lẻ. Do đó đồ thị lúc này là một "forest". Tại mỗi đỉnh có bậc lớn hơn $1$ ta thực hiện chuyển trạng thái và sau mỗi lần thì đồ thị mới sẽ không tạo ra "cycle". Do đó ta sẽ thực hiện được cho đến khi mọi đỉnh có bậc nhỏ hơn $2$.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
chemthan is offline   Trả Lời Với Trích Dẫn
The Following User Says Thank You to chemthan For This Useful Post:
MATHSCOPE (17-07-2019)
 
[page compression: 9.86 k/10.94 k (9.87%)]