CXR

Không biết khóa học này đã bắt đầu chưa nhỉ Hồi tháng 9 nghe chú Ngô Việt Trung nói là vẫn còn đang tuyển sinh

Ngày xưa ghét nhất làm bài đồ thị cứ phải chuyển chuyển thế này, có cách nào có cái trick gì bất ngờ không anh CXR ?

Bài này có thể dùng phản chứng để làm đơn giản một số bước chuyển - Sau khi đưa về trường hợp max clique size của 2 phòng chênh nhau không quá một thì chỉ cần thêm 2 bước chuyển nữa là xong. Có một vài lời giải xuất hiện ở nhiều hình thức khác nhau .. nhưng chung quy lại vẫn là xét các trường hợp rồi chuyển - cho đến giờ anh chưa thấy một lời giải trực tiếp nào cả. Cái khó chính là ở chỗ vận dụng được tính chẵn lẻ của max clique size.

Em post thử mấy ý này xem có được hok
Xét G là clique dài nhất và có 2k người
Ngoài G ta xét H là clique dài thứ 2 và ko là clique con của G, đồng thời nó có ít người chung với G nhất
Ta cho tất cả những người trong H vào phòng B và tất cả nhg người còn lại vào phòng A
Giả sử G,H có chung j người và H có i người thì clique G trong phòng A còn lại 2k-j người và biến thành Clique G'
TH1: $2k-j \geq i$
ta dễ thấy là chuyển người từ clique G' sang phòng B ko làm đổi số ng' trong độ dài clique max của phòng B, nên ta cứ chuyển đến khi nào clique G' biến hành G'' có i người. Dễ thấy phòng A, B đều có đội dài clique max là i( vì nếu tồn tại 1 clique dài hơn sẽ trái với định nghĩa của H)
TH2: $2k-j \leq i$
TH này ta xét tất cả các clique ơe phòng A
$ G_{1}, G_{2},... G{n} $, các clique này có độ dài tối đa là i theo định nghĩa của H
ta gọi $ H_{j} $ là tập người trong phòng B có thể gắn thêm vào clique $G_{j}$ để tạo ra clique dài hơn
Dễ thấy cứ 1 lần chuyển 1 người từ B sang A thì độ dài clique bên phòng B giảm đi 1, còn các clique bên phòng A tăng độ dài lên không quá 1. Từ các tập $ H_{i} $ và độ dài các $ G_{j} $ ta chọn được 1 số người trong phòng B sao cho khi chuyển xong độ dài clique max trong A bằng hoặc kém hơn độ dài clique trong B là 1( dễ thấy ít nhất có clique G' thực hiện được điều này), và chọn số người sao cho ít nhất . Ta chỉ cần xét TH kém 1.Xét các clique dài nhất trong A. Nếu có 1 ng' trong B ko thể nhóm với bất kì clique nào trong đó thì chuyển sang phòng A-xong. Nếu ko ta chuyển 1 ng' bất kì từ B sang A. Chọn tất cả các clique có m+1 ng' lúc này trong A. Ta thấy có thể chọn 1 ng' trong mỗi clique trên chuyển sang B đẻ đọ dại clique bên đó ko đổi( Nếu ko sẽ tạo ra 1 clique dài hơn H và nhỏ hơn G vô lý)
Vậy bài toán được CM

Tôi không hiểu tại sao trong trường hợp cuối cùng lại kết luận đc là độ dài lớn nhất bên B không đổi. Trong quá trình chuyển đổi sao cho max A = max B - 1, có thể max B lúc này đã là khá nhỏ (giả sử i = 2l+1 thì sau khi chuyển nốt một người nữa sang B có thể max B lúc này chỉ là l). Và nếu chuyển một số người bên A (lúc này max A = l+1) quay lại bên B mà tạo nên clique to hơn thì kết hợp với những ai (bên A) để tạo thành clique dài hơn H?

Có lẽ bạn cần giải thích cặn kẽ hơn điểm cuối cùng (làm một số tính toán). Theo marking scheme mà tôi may mắn được nhìn thấy thì đây chính là điểm mấu chốt của lời giải. Hình như bạn cũng chưa dùng giả thuyết rằng độ dài lớn nhất của clique trong đồ thị là chẵn

Hi hi, sao anh dọa em nó thế Mà anh có tham ra chấm bài này không vậy? h..m có lời giải ko dùng kết quả combinatorial nullstellenstaz à?

Ngoài cách dùng định lý không điểm rời rạc ra, bài này còn có thể giải đc bằng sai phân (một chú Đức và một chút Italy làm thế) .. cách này rất hay và tự nhiên - mọi người thử nghĩ xem

Tại sao bây giờ thi lại có 7 bài nhỉ, thi trong mấy ngày vậy mọi người?