Bài 3

Trong một cuộc thi toán, một số thí sinh là bạn của nhau. Quan hệ bạn bè luôn có tính hai chiều. Gọi một nhóm thí sinh là một nhóm bạn nếu mỗi hai người trong nhóm đều là bạn. (Đặc biệt, mọi nhóm có ít hơn hai thí sinh đều là một nhóm bạn.) Số thành viên của một nhóm bạn được gọi là kích thước của nhóm. Biết rằng trong cuộc thi này, kích thước lớn nhất của một nhóm bạn là số chẵn, hãy chứng minh có thể xếp các thí sinh vào hai phòng sao cho kích thước lớn nhất của một nhóm bạn nằm trong phòng này bằng kích thước lớn nhất của một nhóm bạn nằm trong phòng kia.

Bước 1 trên 4: Khởi tạo nhóm bạn lớn nhất M trong Phòng A và chuyển dần đến khi c(A) <= c(B)

Bước trước Bước tiếp

Hiểu nôm na

Ban đầu đặt toàn bộ $M$ vào Phòng $A$ cho $c(A) = 2m \ge c(B)$ ; chuyển từng người từ $A$ sang $B$ làm giảm $c(A)$ đi $1$ và tăng $c(B)$ nhiều nhất $1$ ở mỗi bước, nên khi lần đầu điều kiện $c(A) > c(B)$ không còn đúng, $c(B)$ bằng $k$ hoặc $k+1$ , và $k \ge m$ vì $M$ có kích thước chẵn $2m$ .

|M| = 2m, \\quad \\text{stop when } k = c(A) \\le c(B) \\le k+1, \\quad k = |A| = |A \\cap M| \\ge m

Đồ thị tình bạn K4 minh họa: cả bốn đỉnh tạo thành một nhóm bạn lớn nhất có kích thước chẵn; hình không mã hóa cách chia phòng.

Phân tích chi tiết

Gọi $c(X)$ là kích thước nhóm bạn lớn nhất trong phòng $X$ . Cố định nhóm bạn lớn nhất $M$ có kích thước $|M| = 2m$ , đặt $A = M$ và $B$ là các thí sinh còn lại, nên $c(A) = 2m \ge c(B)$ . Khi $c(A) > c(B)$ , chuyển một người từ $A$ sang $B$ ; mỗi lần chuyển làm giảm $c(A) = |A|$ đi $1$ và tăng $c(B)$ nhiều nhất $1$ . Khi dừng với $k = c(A) = |A| = |A \cap M|$ , ta có $k \le c(B) \le k+1$ . Hơn nữa $k \ge m$ : nếu không thì $|A \cap M| \le m-1$ và $|B \cap M| \ge m+1$ , dẫn đến $c(B) - c(A) \ge (m+1) - (m-1) = 2$ , trái với $c(B) \le c(A)+1$ lúc dừng. Nếu $c(B) = k$ thì xong; từ đây giả sử $c(B) = k+1$ (với $k \ge m \ge |B \cap M|$ ).