›
›

Nguyên lý chuồng bồ câu - Trần Vĩnh Đức

pdf 69 trang phuongnguyen 6800
Download
Bạn đang xem 20 trang mẫu của tài liệu "Nguyên lý chuồng bồ câu - Trần Vĩnh Đức", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfnguyen_ly_chuong_bo_cau_tran_vinh_duc.pdf

Nội dung text: Nguyên lý chuồng bồ câu - Trần Vĩnh Đức

  1. Nguyên lý chuồng bồ câu Nguyên lý chuồng bồ câu1 Trần Vĩnh Đức HUST Ngày 17 tháng 2 năm 2014 1 Tham khảo: R. A. Brualdi, Introductory Combinatorics,. Fifth. Edition. . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 1 / 44
  2. Nội dung 1 Nguyên lý chuồng bồ câu 2 Nguyên lý chuồng chim bồ câu dạng tổng quát 3 Định lý Ramsey 4 Chứng minh định lý Ramsey 5 Ví dụ và tổng quát hĩa . . . . . .
  3. Nguyên lý chuồng bồ câu | Nguyên lý chuồng bồ câu .Định. lý Nếu bỏ n + 1 đối tượng vào n hộp thì cĩ ít nhất một hộp cĩ nhiều hơn hoặc. bằng hai đối tượng. .Ví. dụ .Trong 13 người cĩ ít nhất 2 người sinh cùng tháng. . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 3 / 44
  4. Nguyên lý chuồng bồ câu | Nguyên lý chuồng bồ câu .Ví. dụ Cho m số nguyên a1, a2, , am, luơn tồn tại các số nguyên k và ℓ với 0 ≤ k < ℓ ≤ m sao cho ak+1 + ak+2 + ··· + aℓ chia hết cho m. Nĩi cách khác, luơn cĩ dãy liên tiếp các ai sao cho tổng của chúng chia hết cho m. . . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 4 / 44
  5. Nếu cĩ một tổng chia m vậy ta cĩ Đpcm. Nếu khơng cĩ tổng nào chia hết cho m, cĩ nghĩa rằng phần dư của chúng cho m là một trong các số 1, 2, , m − 1. Vậy thì cĩ hai số k, ℓ và k < ℓ sao cho a1 + ··· + ak và a1 + ··· + aℓ cĩ cùng phần dư là r khi chia cho m: a1 + a2 + ··· + ak = bm + r, a1 + a2 + ··· + aℓ = cm + r Trừ hai tổng này ta được ak+1 + ··· + aℓ = (c − b)m. Vậy ak+1 + ak+2 + ··· + aℓ chia hết cho m. Nguyên lý chuồng bồ câu | Nguyên lý chuồng bồ câu .Chứng. minh. Ta xét m tổng a1, a1 + a2, , a1 + a2 + ··· + am. . . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 5 / 44
  6. Nếu khơng cĩ tổng nào chia hết cho m, cĩ nghĩa rằng phần dư của chúng cho m là một trong các số 1, 2, , m − 1. Vậy thì cĩ hai số k, ℓ và k < ℓ sao cho a1 + ··· + ak và a1 + ··· + aℓ cĩ cùng phần dư là r khi chia cho m: a1 + a2 + ··· + ak = bm + r, a1 + a2 + ··· + aℓ = cm + r Trừ hai tổng này ta được ak+1 + ··· + aℓ = (c − b)m. Vậy ak+1 + ak+2 + ··· + aℓ chia hết cho m. Nguyên lý chuồng bồ câu | Nguyên lý chuồng bồ câu .Chứng. minh. Ta xét m tổng a1, a1 + a2, , a1 + a2 + ··· + am. Nếu cĩ một tổng chia m vậy ta cĩ Đpcm. . . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 5 / 44
  7. Nguyên lý chuồng bồ câu | Nguyên lý chuồng bồ câu .Chứng. minh. Ta xét m tổng a1, a1 + a2, , a1 + a2 + ··· + am. Nếu cĩ một tổng chia m vậy ta cĩ Đpcm. Nếu khơng cĩ tổng nào chia hết cho m, cĩ nghĩa rằng phần dư của chúng cho m là một trong các số 1, 2, , m − 1. Vậy thì cĩ hai số k, ℓ và k < ℓ sao cho a1 + ··· + ak và a1 + ··· + aℓ cĩ cùng phần dư là r khi chia cho m: a1 + a2 + ··· + ak = bm + r, a1 + a2 + ··· + aℓ = cm + r Trừ hai tổng này ta được ak+1 + ··· + aℓ = (c − b)m. Vậy ak+1 + ak+2 + ··· + aℓ chia hết cho m. . . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 5 / 44
  8. Nguyên lý chuồng bồ câu | Nguyên lý chuồng bồ câu .Ví. dụ Trong một tháng 30 ngày một đội bĩng chuyền phải thi đấu mỗi ngày ít nhất một trận, nhưng khơng chơi quá 45 trận. Chứng minh rằng cĩ những. ngày liên tiếp trong tháng đội chơi đúng 14 trận. . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 6 / 44
  9. Nguyên lý chuồng bồ câu | Nguyên lý chuồng bồ câu .Chứng. minh. Gọi ai là tổng số trận thi đấu của đội cho đến ngày thứ i. Khi đĩ a1, a2, , a30 là một dãy tăng chặt và thỏa mãn 1 ≤ ai ≤ 45. Và a1 + 14, a2 + 14, , a30 + 14 cũng là dãy tăng chặt và thỏa mãn 15 ≤ ai + 14 ≤ 59 Dãy sau gồm 60 số nguyên dương a1, a2, , a30, a1 + 14, a2 + 14, , a30 + 14 nhưng đều nhỏ hơn 59. Vậy phải cĩ hai trong các số này bằng nhau. Nhưng vì hai dãy trên đều cĩ các phần tử phân biệt, vậy cĩ số hai số i, k sao cho ai = ak + 14. Cĩ nghĩa rằng cĩ một giai đoạn từ ngày k đến ngày i đội thi đấu đúng 14 trận. . . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 7 / 44
  10. Nguyên lý chuồng bồ câu | Nguyên lý chuồng bồ câu .Ví. dụ Một cờ thủ cĩ 11 tuần để chuẩn bị đấu giải. Anh ta quyết tâm chơi mỗi ngày một trận, nhưng để giữ sức anh ta quyết khơng chơi quá 12 trận một tuần. Chứng minh rằng cĩ một giai đoạn (gồm những ngày liên tiếp) .anh ta chơi đúng 21 trận. . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 8 / 44
  11. Nguyên lý chuồng bồ câu | Nguyên lý chuồng bồ câu .Ví. dụ Chọn 101 số từ 200 số nguyên 1, 2, , 200. Chứng minh rằng trong các .số vừa chọn cĩ hai số sao cho một số chia hết cho số kia. . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 9 / 44
  12. Nguyên lý chuồng bồ câu | Nguyên lý chuồng bồ câu .Chứng. minh. Bằng cách chia liên tiếp cho 2 ta thấy rằng mọi số nguyên cĩ thể viết dưới dạng 2k × a, với k ≥ 0 và a là số lẻ. Với các số nguyên giữa 1 và 100, a là một trong 100 số 1, 3, , 199. Vậy trong 101 số được chọn cĩ ít nhất hai số viết được dưới dạng 2r × a và 2s × a và r > s. Vậy số thứ nhất chia hết cho số thứ hai. Chú ý rằng số 101 là giá trị nhỏ nhất cĩ thể chọn vì ta cĩ thể chọn 100 số từ 1, 2, , 100 mà khơng cĩ số nào là ước của số nào (ví dụ, 100 số 101, 102, , 199, 200). . . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 10 / 44
  13. Nguyên lý chuồng bồ câu | Nguyên lý chuồng bồ câu Hai số nguyên là nguyên tố cùng nhau nếu ước chung lớn nhất của chúng là 1. Vậy 12 và 35 là nguyên tố cùng nhau, nhưng 12 và 15 thì khơng phải. .Ví. dụ (Định lý phần dư Trung Hoa) Xét m và n là hai số nguyên tố cùng nhau, và xét a và b là hai số nguyên với 0 ≤ a ≤ m và 0 ≤ b ≤ n − 1. Vậy cĩ một số nguyên x sao cho x chia cho m dư a và x chia cho n dư b; cĩ nghĩa rằng x cĩ thể viết dưới dạng . x = pm + a và x = qn + b. . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 11 / 44
  14. Nguyên lý chuồng bồ câu | Nguyên lý chuồng bồ câu Chứng minh. Xét dãy n số nguyên a, m + a, 2m + a, , (n − 1)m + a (1) Ta sẽ chỉ ra rằng các phần dư của n số này chia cho n là khác nhau từng đơi một. Thậy vậy, giả sử ngược lại rằng cĩ hai số 0 ≤ i < j ≤ n − 1 sao cho im + a và jm + a cĩ cùng phần dư là r khi chia cho n. Cĩ nghĩa rằng im + a = qin + r và jm + a = qjn + r. Trừ hai vế ta được (j − i)m = (qj − qi)n. Vậy n là ước của (j − i)m. Vì m và n nguyên tố cùng nhau nên n phải là ước của j − i, nhưng vì i < j < n − 1, nên điều này mâu thuẫn. Vậy phần dư của các số trong dãy (1) chia cho n là đơi một phân biệt. . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 12 / 44
  15. Nguyên lý chuồng bồ câu | Nguyên lý chuồng bồ câu Vậy theo nguyên lý chuồng chim bồ câu, phần dừ của các số trong dãy (1) chia cho n phải là 0, 1, , n − 1 trong đĩ cĩ số b. Xét x là số nguyên dạng pm + a chia cho n dư b. Khi đĩ số x = pm + a và x = qn + b là số thỏa mãn yêu cầu. . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 13 / 44
  16. Nội dung 1 Nguyên lý chuồng bồ câu 2 Nguyên lý chuồng chim bồ câu dạng tổng quát 3 Định lý Ramsey 4 Chứng minh định lý Ramsey 5 Ví dụ và tổng quát hĩa . . . . . .
  17. Nguyên lý chuồng bồ câu | Nguyên lý chuồng chim bồ câu dạng tổng quát .Định. lý Xét các số nguyên dương q1, q2, , qn. Nếu q1 + q2 + ··· + qn − n + 1 đối tượng được đặt trong n chiếc hộp, vậy hộp thứ nhất chứa ít nhất q1 đối tượng, hoặc hộp thứ hai chứa ít nhất q2 đối tượng, , hoặc hộp thứ .n chứa ít nhất qn đối tượng. . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 15 / 44
  18. Nguyên lý chuồng bồ câu | Nguyên lý chuồng chim bồ câu dạng tổng quát Nguyên lý chuồng chim bồ câu Nguyên lý chuồng chim bồ câu là trường hợp riêng khi q1 = q2 = ··· = qn = 2 Tức là nếu cĩ 2 + 2 + ··· + 2 − n + 1 = 2n − n + 1 = n + 1 đối tượng đặt trong n chiếc lồng, thì cĩ lồng chứa ít nhất hai đối tượng. . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 16 / 44
  19. Nguyên lý chuồng bồ câu | Nguyên lý chuồng chim bồ câu dạng tổng quát .Hệ. quả Xét hai số nguyên dương r và n. Nếu n(r − 1) + 1 đối tượng được đặt trong n chiếc hộp, vậy cĩ hộp chứa ít nhất r đối .tượng. Đây là trường hợp khi q1 = q2 = ··· = qn = r . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 17 / 44
  20. Nguyên lý chuồng bồ câu | Nguyên lý chuồng chim bồ câu dạng tổng quát Nguyên lý trung bình 1 Hệ quả trước cĩ thể phát biểu dưới dạng nguyên lý trung bình .Nguyên. lý trung bình Nếu trung bình của các số nguyên khơng âm m1, m2, , mn lớn hơn r − 1, tức là m + m + ··· + m 1 2 n > r − 1. n Vậy. cĩ ít nhất một số mi lớn hơn hoặc bằng r. . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 18 / 44
  21. Nguyên lý chuồng bồ câu | Nguyên lý chuồng chim bồ câu dạng tổng quát Nguyên lý trung bình 2 Một nguyên lý trung bình khác .Nguyên. lý trung bình Nếu trung bình của các số nguyên khơng âm m1, m2, , mn nhỏ hơn hơn r + 1, tức là m + m + ··· + m 1 2 n < r + 1. n .Vậy cĩ ít nhất một số mi nhỏ hơn hoặc bằng r. . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 19 / 44
  22. Nguyên lý chuồng bồ câu | Nguyên lý chuồng chim bồ câu dạng tổng quát .Ví. dụ Một giỏ quả gồm ba loại táo, chuối, và cam. Hỏi trong giỏ cần ít nhất bao nhiêu quả để chắc rằng trong đĩ cĩ ít nhất 8 quả táo hoặc ít nhất 6 .quả chuối hoặc ít nhất 9 quả cam? . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 20 / 44
  23. Nguyên lý chuồng bồ câu | Nguyên lý chuồng chim bồ câu dạng tổng quát .Ví. dụ Cĩ hai đĩa kích thước khác nhau. Mỗi đĩa chia thành 200 sector. Trên đĩa lớn, ta chọn ngẫu nhiên 100 sector và sơn chúng màu đỏ; 100 sector cịn lại sơn màu xanh. Trên đĩa nhỏ ta sơn hoặc màu xanh hoặc mầu đỏ một cách ngẫu nhiên lên mỗi sector. Đặt đĩa nhỏ lên trên đĩa lớn sao cho đồng tâm. Chứng minh rằng ta cĩ thể điều chỉnh hai đĩa sao cho số lượng sector của đĩa nhỏ cĩ màu trùng .với sector tương ứng của đĩa lớn ít nhất là 100. . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 21 / 44
  24. Nguyên lý chuồng bồ câu | Nguyên lý chuồng chim bồ câu dạng tổng quát .Ví. dụ (Erdưs và Szekeres, 1935) Hãy chứng minh rằng trong mọi dãy gồm n2 + 1 số thực a1, a2, , an2+1 đều chứa một dãy con khơng giảm gồm n + 1 số hoặc một dãy con .khơng tăng gồm n + 1 số. . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 22 / 44
  25. Nội dung 1 Nguyên lý chuồng bồ câu 2 Nguyên lý chuồng chim bồ câu dạng tổng quát 3 Định lý Ramsey 4 Chứng minh định lý Ramsey 5 Ví dụ và tổng quát hĩa . . . . . .
  26. Nguyên lý chuồng bồ câu | Định lý Ramsey Lý thuyết Ramsey Lý thuyết Ramsey, theo tên của Frank Plumpton Ramsey, một nhà tốn học người Anh. Nĩi chung, lý thuyết Ramsey giải quyết những bài tốn về sự phân bố các tập con của một tập. Hình: F. P. Ramsey (1903-1930) . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 24 / 44
  27. Viết lại khẳng định trên một cách ngắn gọn dùng ký hiệu ”mũi tên” như sau: K6 → K3, K3 với ý nghĩa K6= “6 đối tượng và 15 cặp khơng thứ tự của các đối tượng này” K3, K3 = “Ba đối tượng quen nhau từng đơi một”, “Ba đối tượng khơng quen nhau từng đơi một” Nguyên lý chuồng bồ câu | Định lý Ramsey .Khẳng. định Trong sáu người bất kỳ luơn tồn tại ba người sao cho hoặc là họ quen .nhau từng đơi một hoặc họ khơng quen nhau từng đơi một. . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 25 / 44
  28. với ý nghĩa K6= “6 đối tượng và 15 cặp khơng thứ tự của các đối tượng này” K3, K3 = “Ba đối tượng quen nhau từng đơi một”, “Ba đối tượng khơng quen nhau từng đơi một” Nguyên lý chuồng bồ câu | Định lý Ramsey .Khẳng. định Trong sáu người bất kỳ luơn tồn tại ba người sao cho hoặc là họ quen .nhau từng đơi một hoặc họ khơng quen nhau từng đơi một. Viết lại khẳng định trên một cách ngắn gọn dùng ký hiệu ”mũi tên” như sau: K6 → K3, K3 . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 25 / 44
  29. K3, K3 = “Ba đối tượng quen nhau từng đơi một”, “Ba đối tượng khơng quen nhau từng đơi một” Nguyên lý chuồng bồ câu | Định lý Ramsey .Khẳng. định Trong sáu người bất kỳ luơn tồn tại ba người sao cho hoặc là họ quen .nhau từng đơi một hoặc họ khơng quen nhau từng đơi một. Viết lại khẳng định trên một cách ngắn gọn dùng ký hiệu ”mũi tên” như sau: K6 → K3, K3 với ý nghĩa K6= “6 đối tượng và 15 cặp khơng thứ tự của các đối tượng này” . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 25 / 44
  30. Nguyên lý chuồng bồ câu | Định lý Ramsey .Khẳng. định Trong sáu người bất kỳ luơn tồn tại ba người sao cho hoặc là họ quen .nhau từng đơi một hoặc họ khơng quen nhau từng đơi một. Viết lại khẳng định trên một cách ngắn gọn dùng ký hiệu ”mũi tên” như sau: K6 → K3, K3 với ý nghĩa K6= “6 đối tượng và 15 cặp khơng thứ tự của các đối tượng này” K3, K3 = “Ba đối tượng quen nhau từng đơi một”, “Ba đối tượng khơng quen nhau từng đơi một” . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 25 / 44
  31. Nguyên lý chuồng bồ câu | Định lý Ramsey Kn = “một tập n đối tượng và mọi cặp khơng thứ tự (cạnh) các đối tượng này” . . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 26 / 44
  32. Vậy K6 → K3, K3 cĩ nghĩa là “Dù cĩ tơ xanh đỏ các cạnh của K6 ta luơn tìm được một K3 cĩ tồn cạnh đỏ hoặc một K3 tồn cạnh xanh” Nguyên lý chuồng bồ câu | Định lý Ramsey Nếu ta xem mỗi cặp khơng thứ tự như một cạnh. Cặp đối tượng quen nhau xem như cạnh tơ màu xanh. Cặp đối tượng khơng quen nhau như các cạnh tơ màu đỏ. . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 27 / 44
  33. “Dù cĩ tơ xanh đỏ các cạnh của K6 ta luơn tìm được một K3 cĩ tồn cạnh đỏ hoặc một K3 tồn cạnh xanh” Nguyên lý chuồng bồ câu | Định lý Ramsey Nếu ta xem mỗi cặp khơng thứ tự như một cạnh. Cặp đối tượng quen nhau xem như cạnh tơ màu xanh. Cặp đối tượng khơng quen nhau như các cạnh tơ màu đỏ. Vậy K6 → K3, K3 cĩ nghĩa là . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 27 / 44
  34. Nguyên lý chuồng bồ câu | Định lý Ramsey Nếu ta xem mỗi cặp khơng thứ tự như một cạnh. Cặp đối tượng quen nhau xem như cạnh tơ màu xanh. Cặp đối tượng khơng quen nhau như các cạnh tơ màu đỏ. Vậy K6 → K3, K3 cĩ nghĩa là “Dù cĩ tơ xanh đỏ các cạnh của K6 ta luơn tìm được một K3 cĩ tồn cạnh đỏ hoặc một K3 tồn cạnh xanh” . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 27 / 44
  35. − Bây giờ, nếu tồn tại một cạnh nối giữa a b a hoặc a − c hoặc b − c cĩ màu đỏ, vậy ta được một K3 đỏ. p b Nếu khơng thì ta được K3 xanh liên quan đến a, b, c. . . c Nguyên lý chuồng bồ câu | Định lý Ramsey Chứng minh K6 → K3, K3 Xét một đối tượng p của K6. Vì cĩ 5 cạnh liên quan đến p cĩ mầu đỏ hoặc xanh nên cĩ ít nhất 3 cạnh cùng màu. Ta giả sử 3 cạnh này cùng màu đỏ. (Nếu màu xanh ta lập luận tương tự.) Cĩ ba đối tượng a, b, c nối với p qua ba cạnh đỏ này. . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 28 / 44
  36. Nguyên lý chuồng bồ câu | Định lý Ramsey Chứng minh K6 → K3, K3 Xét một đối tượng p của K6. Vì cĩ 5 cạnh liên quan đến p cĩ mầu đỏ hoặc xanh nên cĩ ít nhất 3 cạnh cùng màu. Ta giả sử 3 cạnh này cùng màu đỏ. (Nếu màu xanh ta lập luận tương tự.) Cĩ ba đối tượng a, b, c nối với p qua ba cạnh đỏ này. − Bây giờ, nếu tồn tại một cạnh nối giữa a b a hoặc a − c hoặc b − c cĩ màu đỏ, vậy ta được một K3 đỏ. p b Nếu khơng thì ta được K3 xanh liên quan đến a, b, c. . . c . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 28 / 44
  37. Nguyên lý chuồng bồ câu | Định lý Ramsey Khẳng định K5 → K3, K3 là sai vì cĩ cách tơ màu cạnh K5 khơng tạo ra K3 đỏ hoặc K3 xanh. Ví dụ, cách tơ như trong hình dưới đây: nét liền tương ứng màu đỏ, nét đứt tương ứng màu xanh. . . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 29 / 44
  38. Nĩi cách khác, cho trước số nguyên m và n, luơn cĩ số nguyên dương p sao cho, nếu tơ màu xanh hoặc đỏ lên cạnh của Kp thì luơn tìm được hoặc một Km đỏ hoặc một Kn xanh. Rõ ràng, với mọi q ≥ p ta luơn cĩ Kp → Km, Kn ⇒ Kq → Km, Kn. Nguyên lý chuồng bồ câu | Định lý Ramsey .Định. lý (Ramsey, dạng đơn giản) Với hai số nguyên m ≥ 2 và n ≥ 2, luơn tồn tại một số nguyên dương p sao cho → . Kp Km, Kn . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 30 / 44
  39. Rõ ràng, với mọi q ≥ p ta luơn cĩ Kp → Km, Kn ⇒ Kq → Km, Kn. Nguyên lý chuồng bồ câu | Định lý Ramsey .Định. lý (Ramsey, dạng đơn giản) Với hai số nguyên m ≥ 2 và n ≥ 2, luơn tồn tại một số nguyên dương p sao cho → . Kp Km, Kn Nĩi cách khác, cho trước số nguyên m và n, luơn cĩ số nguyên dương p sao cho, nếu tơ màu xanh hoặc đỏ lên cạnh của Kp thì luơn tìm được hoặc một Km đỏ hoặc một Kn xanh. . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 30 / 44
  40. Nguyên lý chuồng bồ câu | Định lý Ramsey .Định. lý (Ramsey, dạng đơn giản) Với hai số nguyên m ≥ 2 và n ≥ 2, luơn tồn tại một số nguyên dương p sao cho → . Kp Km, Kn Nĩi cách khác, cho trước số nguyên m và n, luơn cĩ số nguyên dương p sao cho, nếu tơ màu xanh hoặc đỏ lên cạnh của Kp thì luơn tìm được hoặc một Km đỏ hoặc một Kn xanh. Rõ ràng, với mọi q ≥ p ta luơn cĩ Kp → Km, Kn ⇒ Kq → Km, Kn. . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 30 / 44
  41. Dễ thấy r(m, n) = r(n, m). .Ví. dụ Ta cĩ r(3, 3) = 6 vì . K6 → K3, K3 và K5 ̸→ K3, K3. Nguyên lý chuồng bồ câu | Định lý Ramsey Số Ramsey Số nguyên p nhỏ nhất sao cho Kp → Km, Kn gọi là số Ramsey r(m, n). . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 31 / 44
  42. .Ví. dụ Ta cĩ r(3, 3) = 6 vì . K6 → K3, K3 và K5 ̸→ K3, K3. Nguyên lý chuồng bồ câu | Định lý Ramsey Số Ramsey Số nguyên p nhỏ nhất sao cho Kp → Km, Kn gọi là số Ramsey r(m, n). Dễ thấy r(m, n) = r(n, m). . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 31 / 44
  43. K6 → K3, K3 và K5 ̸→ K3, K3. Nguyên lý chuồng bồ câu | Định lý Ramsey Số Ramsey Số nguyên p nhỏ nhất sao cho Kp → Km, Kn gọi là số Ramsey r(m, n). Dễ thấy r(m, n) = r(n, m). .Ví. dụ Ta cĩ r(3, 3) = 6 vì . . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 31 / 44
  44. Nguyên lý chuồng bồ câu | Định lý Ramsey Số Ramsey Số nguyên p nhỏ nhất sao cho Kp → Km, Kn gọi là số Ramsey r(m, n). Dễ thấy r(m, n) = r(n, m). .Ví. dụ Ta cĩ r(3, 3) = 6 vì . K6 → K3, K3 và K5 ̸→ K3, K3. . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 31 / 44
  45. 2 r(3,4) = r(4,3) = ? 3 r(3,5) = r(5,3) = ? Nguyên lý chuồng bồ câu | Định lý Ramsey .Bài. tập Tính các số Ramsey sau 1 r(2, n) = r(n,2) = ? . . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 32 / 44
  46. 3 r(3,5) = r(5,3) = ? Nguyên lý chuồng bồ câu | Định lý Ramsey .Bài. tập Tính các số Ramsey sau 1 r(2, n) = r(n,2) = ? 2 r(3,4) = r(4,3) = ? . . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 32 / 44
  47. Nguyên lý chuồng bồ câu | Định lý Ramsey .Bài. tập Tính các số Ramsey sau 1 r(2, n) = r(n,2) = ? 2 r(3,4) = r(4,3) = ? 3 r(3,5) = r(5,3) = ? . . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 32 / 44
  48. Nội dung 1 Nguyên lý chuồng bồ câu 2 Nguyên lý chuồng chim bồ câu dạng tổng quát 3 Định lý Ramsey 4 Chứng minh định lý Ramsey 5 Ví dụ và tổng quát hĩa . . . . . .
  49. Nguyên lý chuồng bồ câu | Chứng minh định lý Ramsey .Định. lý (Ramsey, dạng đơn giản) Với hai số nguyên m ≥ 2 và n ≥ 2, luơn tồn tại một số nguyên dương p sao cho → . Kp Km, Kn . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 34 / 44
  50. Bước cơ sở: Nếu m = 2 thì r(2, n) = n, nếu n = 2 thì r(m, 2) = m. Nguyên lý chuồng bồ câu | Chứng minh định lý Ramsey Chứng minh định lý Ramsey Ta chỉ ra sự tồn tại của r(m, n) bằng quy nạp theo cả m và n. . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 35 / 44
  51. Nguyên lý chuồng bồ câu | Chứng minh định lý Ramsey Chứng minh định lý Ramsey Ta chỉ ra sự tồn tại của r(m, n) bằng quy nạp theo cả m và n. Bước cơ sở: Nếu m = 2 thì r(2, n) = n, nếu n = 2 thì r(m, 2) = m. . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 35 / 44
  52. Nguyên lý chuồng bồ câu | Chứng minh định lý Ramsey Chứng minh định lý Ramsey Ta chỉ ra sự tồn tại của r(m, n) bằng quy nạp theo cả m và n. Bước cơ sở: Nếu m = 2 thì r(2, n) = n, nếu n = 2 thì r(m, 2) = m. . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 35 / 44
  53. Đặt p = r(m − 1, n) + r(m, n − 1) Ta sẽ chỉ ra rằng Kp → Km, Kn. Nguyên lý chuồng bồ câu | Chứng minh định lý Ramsey Bước quy nạp Giả sử rằng m ≥ 3 và n ≥ 3 và tồn tại cả r(m, n − 1) và r(m − 1, n) . . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 36 / 44
  54. Ta sẽ chỉ ra rằng Kp → Km, Kn. Nguyên lý chuồng bồ câu | Chứng minh định lý Ramsey Bước quy nạp Giả sử rằng m ≥ 3 và n ≥ 3 và tồn tại cả r(m, n − 1) và r(m − 1, n) . Đặt p = r(m − 1, n) + r(m, n − 1) . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 36 / 44
  55. Nguyên lý chuồng bồ câu | Chứng minh định lý Ramsey Bước quy nạp Giả sử rằng m ≥ 3 và n ≥ 3 và tồn tại cả r(m, n − 1) và r(m − 1, n) . Đặt p = r(m − 1, n) + r(m, n − 1) Ta sẽ chỉ ra rằng Kp → Km, Kn. . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 36 / 44
  56. Vậy |Rx| + |Bx| = p − 1 = r(m − 1, n) + r(m, n − 1) − 1 chỉ ra rằng (1) |Rx| ≥ r(m − 1, n), hoặc (2) |Bx| ≥ r(m, n − 1). Nguyên lý chuồng bồ câu | Chứng minh định lý Ramsey Chứng minh Kp → Km, Kn Xét một điểm x của Kp. Đăt Rx là tập điểm nối với x bằng một cạnh màu đỏ, và Bx là tập điểm nối với x bởi một cạnh màu xanh. . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 37 / 44
  57. Nguyên lý chuồng bồ câu | Chứng minh định lý Ramsey Chứng minh Kp → Km, Kn Xét một điểm x của Kp. Đăt Rx là tập điểm nối với x bằng một cạnh màu đỏ, và Bx là tập điểm nối với x bởi một cạnh màu xanh. Vậy |Rx| + |Bx| = p − 1 = r(m − 1, n) + r(m, n − 1) − 1 chỉ ra rằng (1) |Rx| ≥ r(m − 1, n), hoặc (2) |Bx| ≥ r(m, n − 1). . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 37 / 44
  58. hoặc m − 1 điểm của Kq (cũng thuộc Kp) cĩ tồn cạnh màu đỏ. Ta cĩ Km−1 đỏ, và tất cả m − 1 điểm này đều nối với x bằng cạnh màu đỏ. Vậy ta cĩ Km đỏ. hoặc n điểm của Kq tồn cạnh màu xanh. Vậy ta cĩ một Kn xanh. Nguyên lý chuồng bồ câu | Chứng minh định lý Ramsey Nếu |Rx| ≥ r(m − 1, n), ta đặt q = |Rx| vậy q ≥ r(m − 1, n). Xét Kq trên các điểm của Rx, ta thấy rằng . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 38 / 44
  59. hoặc n điểm của Kq tồn cạnh màu xanh. Vậy ta cĩ một Kn xanh. Nguyên lý chuồng bồ câu | Chứng minh định lý Ramsey Nếu |Rx| ≥ r(m − 1, n), ta đặt q = |Rx| vậy q ≥ r(m − 1, n). Xét Kq trên các điểm của Rx, ta thấy rằng hoặc m − 1 điểm của Kq (cũng thuộc Kp) cĩ tồn cạnh màu đỏ. Ta cĩ Km−1 đỏ, và tất cả m − 1 điểm này đều nối với x bằng cạnh màu đỏ. Vậy ta cĩ Km đỏ. . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 38 / 44
  60. Nguyên lý chuồng bồ câu | Chứng minh định lý Ramsey Nếu |Rx| ≥ r(m − 1, n), ta đặt q = |Rx| vậy q ≥ r(m − 1, n). Xét Kq trên các điểm của Rx, ta thấy rằng hoặc m − 1 điểm của Kq (cũng thuộc Kp) cĩ tồn cạnh màu đỏ. Ta cĩ Km−1 đỏ, và tất cả m − 1 điểm này đều nối với x bằng cạnh màu đỏ. Vậy ta cĩ Km đỏ. hoặc n điểm của Kq tồn cạnh màu xanh. Vậy ta cĩ một Kn xanh. . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 38 / 44
  61. Nguyên lý chuồng bồ câu | Chứng minh định lý Ramsey Nếu |Rx| ≥ r(m − 1, n), ta đặt q = |Rx| vậy q ≥ r(m − 1, n). Xét Kq trên các điểm của Rx, ta thấy rằng hoặc m − 1 điểm của Kq (cũng thuộc Kp) cĩ tồn cạnh màu đỏ. Ta cĩ Km−1 đỏ, và tất cả m − 1 điểm này đều nối với x bằng cạnh màu đỏ. Vậy ta cĩ Km đỏ. hoặc n điểm của Kq tồn cạnh màu xanh. Vậy ta cĩ một Kn xanh. . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 38 / 44
  62. Nguyên lý chuồng bồ câu | Chứng minh định lý Ramsey Lập luận tương tự với |Bx| ≥ r(m, n − 1). Ta kết luận bằng quy nặp rằng số r(m, n) tồn tại với mọi m, n ≥ 2. . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 39 / 44
  63. Nội dung 1 Nguyên lý chuồng bồ câu 2 Nguyên lý chuồng chim bồ câu dạng tổng quát 3 Định lý Ramsey 4 Chứng minh định lý Ramsey 5 Ví dụ và tổng quát hĩa . . . . . .
  64. Nguyên lý chuồng bồ câu | Ví dụ và tổng quát hĩa Cận trên của số Ramsey Chứng minh định lý Ramsey cũng chỉ ra rằng r(m, n) ≤ r(m − 1, n) + r(m, n − 1) với m, n ≥ 3. (2) Xét ( ) m + n − 2 f(m, n) = . m − 1 Dùng đẳng thức Pascal ta được ( ) ( ) ( ) m + n − 2 m + n − 3 m + n − 3 = + m − 1 m − 1 m − 2 Vậy ta được cơng thức tương tự như (2): f(m, n) = f(m − 1, n) + f(m, n − 1). . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 41 / 44
  65. Nguyên lý chuồng bồ câu | Ví dụ và tổng quát hĩa Cận trên của số Ramsey (tiếp) Vì r(2, n) = n = f(2, n) và r(m, 2) = m = f(m, 2), ta cĩ ( ) ( ) m + n − 2 m + n − 2 r(m, n) ≤ = m − 1 n − 1 . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 42 / 44
  66. Nguyên lý chuồng bồ câu | Ví dụ và tổng quát hĩa Một vài số Ramsey r(3, 3) = 6, 40 ≤ r(3, 10) = r(10, 3) ≤ 43, r(3, 4) = r(4, 3) = 9, r(4, 4) = 18, r(3, 5) = r(5, 3) = 14, r(4, 5) = r(5, 4) = 25, r(3, 6) = r(6, 3) = 18, 35 ≤ r(4, 6) ≤ 49, r(3, 7) = r(7, 3) = 23, 43 ≤ r(5, 5) ≤ 49, r(3, 8) = r(8, 3) = 28, 58 ≤ r(5, 6) = r(6, 5) ≤ 87, ≤ ≤ . r(3, 9) = r(9, 3) = 36, . 102 r(6, 6) 165. . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 43 / 44
  67. Ví dụ r(3, 3, 3) = 17. Mở rộng tự nhiên cho m màu → ··· Kp Kn1 , Kn2 , , Knm . Nguyên lý chuồng bồ câu | Ví dụ và tổng quát hĩa Tổng quát hố Nếu n1, n2 và n3 là ba số nguyên dương lớn hơn hoặc bằng hai, vậy cĩ tồn tại số nguyên p sao cho → Kp Kn1 , Kn2 , Kn3 Cĩ nghĩa rằng nếu mỗi cạnh của Kp tơ bởi xanh, đỏ, hoặc vàng thì cĩ Kn1 tơ màu xanh hoặc cĩ Kn2 tơ màu vàng hoặc Kn3 tơ màu đỏ. . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 44 / 44
  68. Mở rộng tự nhiên cho m màu → ··· Kp Kn1 , Kn2 , , Knm . Nguyên lý chuồng bồ câu | Ví dụ và tổng quát hĩa Tổng quát hố Nếu n1, n2 và n3 là ba số nguyên dương lớn hơn hoặc bằng hai, vậy cĩ tồn tại số nguyên p sao cho → Kp Kn1 , Kn2 , Kn3 Cĩ nghĩa rằng nếu mỗi cạnh của Kp tơ bởi xanh, đỏ, hoặc vàng thì cĩ Kn1 tơ màu xanh hoặc cĩ Kn2 tơ màu vàng hoặc Kn3 tơ màu đỏ. Ví dụ r(3, 3, 3) = 17. . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 44 / 44
  69. Nguyên lý chuồng bồ câu | Ví dụ và tổng quát hĩa Tổng quát hố Nếu n1, n2 và n3 là ba số nguyên dương lớn hơn hoặc bằng hai, vậy cĩ tồn tại số nguyên p sao cho → Kp Kn1 , Kn2 , Kn3 Cĩ nghĩa rằng nếu mỗi cạnh của Kp tơ bởi xanh, đỏ, hoặc vàng thì cĩ Kn1 tơ màu xanh hoặc cĩ Kn2 tơ màu vàng hoặc Kn3 tơ màu đỏ. Ví dụ r(3, 3, 3) = 17. Mở rộng tự nhiên cho m màu → ··· Kp Kn1 , Kn2 , , Knm . . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 44 / 44