Math Labs

Bài 3

Một mạng xã hội có 20192019 người dùng, một số cặp trong đó là bạn bè (quan hệ bạn bè là đối xứng). Các sự kiện sau có thể xảy ra lặp đi lặp lại, mỗi lần một sự kiện: ba người dùng AA, BB và CC sao cho AA là bạn của cả BB và CC, nhưng BB và CC không phải là bạn, thay đổi quan hệ bạn bè của họ sao cho BB và CC hiện là bạn của nhau, còn AA không còn là bạn của BB và cũng không còn là bạn của CC. Mọi quan hệ bạn bè khác giữ nguyên. Ban đầu, 10101010 người dùng mỗi người có 10091009 bạn, và 10091009 người dùng mỗi người có 10101010 bạn. Chứng minh rằng tồn tại một dãy các sự kiện như vậy sau đó mỗi người dùng là bạn của nhiều nhất một người dùng khác.
Bước 1 trên 6: Mô hình hóa bạn bè bằng đồ thị
Bước trướcBước tiếp
G=(V,E),∣V∣=2019,toggle(A,B,C): AB,AC∈E, BC∉E ⟼ E′=(E∖{AB,AC})∪{BC}G=(V,E),\quad |V|=2019,\qquad \text{toggle}(A,B,C):\ AB,AC\in E,\ BC\notin E\ \longmapsto\ E'=(E\setminus\{AB,AC\})\cup\{BC\}
Phân tích chi tiết

Gọi G=(V,E)G=(V,E) là đồ thị với VV là 20192019 người dùng và EE là các cặp bạn bè. Gọi thao tác đã mô tả là một phép hoán đổi tại A,B,CA,B,C: nó cần các cạnh ABAB và ACAC tồn tại nhưng BCBC thì không, và nó thay EE bằng E′=(E∖{AB,AC})∪{BC}E'=(E\setminus\{AB,AC\})\cup\{BC\}. Mục tiêu trở thành đạt tới một đồ thị mà mọi đỉnh có bậc nhiều nhất 11.