Câu hỏi 7
Có một quần thể $P$ gồm $10000$ vi khuẩn; một số cặp là bạn của nhau (quan hệ bạn bè là đối xứng). Mỗi vi khuẩn có ít nhất một người bạn. Nếu gán cho mỗi vi khuẩn một màng có màu sao cho hai vi khuẩn là bạn không có cùng màu, thì có thể làm được bằng $2021$ màu, nhưng không thể bằng $2020$ màu hoặc ít hơn.
Hai vi khuẩn bạn nhau $A,B$ có thể quyết định nhập lại thành một vi khuẩn duy nhất, có tập bạn bè chính là hợp của các tập bạn bè của $A,B$. Không được nhập hai vi khuẩn không phải là bạn. Biết rằng bất kể thực hiện một lần nhập hay hai lần nhập liên tiếp như thế nào, quần thể thu được đều có thể được gán $2020$ màu hoặc ít hơn sao cho hai vi khuẩn là bạn không có cùng màu. Có đúng là trong mọi quần thể $P$ như vậy, mỗi vi khuẩn có ít nhất $2021$ người bạn không?
Đề xuất bởi Bulgaria.
Hai vi khuẩn bạn nhau $A,B$ có thể quyết định nhập lại thành một vi khuẩn duy nhất, có tập bạn bè chính là hợp của các tập bạn bè của $A,B$. Không được nhập hai vi khuẩn không phải là bạn. Biết rằng bất kể thực hiện một lần nhập hay hai lần nhập liên tiếp như thế nào, quần thể thu được đều có thể được gán $2020$ màu hoặc ít hơn sao cho hai vi khuẩn là bạn không có cùng màu. Có đúng là trong mọi quần thể $P$ như vậy, mỗi vi khuẩn có ít nhất $2021$ người bạn không?
Đề xuất bởi Bulgaria.