Bài 12: Cho một ngôi trường có $n$ khóa học và $n$ học sinh. Các học sinh đăng kí vào lớp học, không có $2$ học sinh nào tham gia các khóa học hoàn toàn giống nhau. CMR: ta có thể đóng cửa một khoá học sao cho vẫn không có hai học sinh nào tham gia các khoá học hoàn toàn giống nhau.
Bài 12:
Xét đồ thị với mỗi học sinh là 1 đỉnh , 2 đỉnh được nối với nhau nếu khi đóng lớp học thứ i (i=1,n) thì 2 học sinh ấy tham gia các khóa học hoàn toàn giống nhau. Và tô màu của đoạn thẳng đó là màu i
Giả sử ngược lại , không thể đóng cửa 1 khóa học nào mà k tồn tại 2 hs tham gia các khóa học hoàn toàn giống nhau , khi đó tất cả các màu (1,2,..n) đều xuất hiện . xét các đỉnh nối các màu đó ( Ta có thể bỏ các cạnh cùng màu sao cho mỗi màu xuất hiện 1 lần)
Vì $\leq n$ đỉnh , n cạnh luôn tồn tại 1 chu trình
Giả sử chu trình đó là A1 -(i1) -> A2 -(i2) ->A3 ..... Ak - (ik)-> A1
k mất tính tổng quát có thể giả sử A1 tham gia nhiều lớp học hơn A2
Khi đó A2 k tham gia lớp học i1
$\Rightarrow$ A3 k tham gia lớp học i1
$\Rightarrow$ .... Ak k tham gia lớp học i1 $\Rightarrow$ A1 k tham gia lớp học i1
$\Rightarrow$ vô lý
Vậy ta có dpcm
- namcpnh, LNH và chardhdmovies thích