Về một số bài toán phân hoạch tập hợp thỏa mãn một tính chất cho trước

Bài viết nghiên cứu bài toán phân hoạch tập hợp các số nguyên dương Z+ thỏa mãn một tính chất cho trước nào đó. Cụ thể là bài toán Schur với tính chất tồn tại bộ số là nghiệm phương trình cho trước và bài toán Van de Waerden với tính chất tồn tại cấp số cộng độ dài k.
Nội dung trích xuất từ tài liệu:
Về một số bài toán phân hoạch tập hợp thỏa mãn một tính chất cho trước VỀ MỘT SỐ BÀI TOÁN PHÂN HOẠCH TẬP HỢP THỎA MÃN MỘT TÍNH CHẤT CHO TRƯỚC ĐỖ VIẾT LÂN - NGUYỄN ĐẮC HIẾU Khoa Toán học1 GIỚI THIỆUChúng tôi nghiên cứu bài toán phân hoạch tập hợp các số nguyên dương Z+ thỏa mãnmột tính chất cho trước nào đó. Cụ thể là bài toán Schur với tính chất tồn tại bộ số lànghiệm phương trình cho trước và bài toán Van de Waerden với tính chất tồn tại cấp sốcộng độ dài k.Nghiên cứu các số Schur, số Van de Waerden để nhằm mục đích tìm hiểu các bài toántrên tập hợp hữu hạn các số nguyên dương. Từ đó giới thiệu các trò chơi với số Van deWaerden, đưa ra các chiến thuật chơi và đồng thời nghiên cứu một số các bài toán sơ cấpliên quan đến định lý Schur, định lý Van de Waerden.2 BÀI TOÁN PHÂN HOẠCH TẬP HỢPSau chặng đường dài toán học đi theo con đường giải tích với tính chất nổi bật là sự liêntục thì ngày nay, toán học thế giới trở lại nhiều hơn với lĩnh vực rời rạc, một lĩnh vực cónhiều ứng dụng trong cuộc sống. Bài toán phân hoạch tập hợp được nhiều nhà toán họcđưa ra từ những năm đầu thế kỷ XX cuốn hút các nhà toán học tham gia cho đến tậnngày nay.Năm 1927, nhà toán học Van de Waerden đã đưa ra chứng minh trong trường hợp tổngquát của giả thiết Schur: Cho hai số r và k, tồn tại số nguyên nhỏ nhất n - số Van deWaerden W (r; k) - mọi phân hoạch tập hợp {1, 2, . . . , n} thành r tập con thì có ít nhấtmột tập chứa cấp số cộng độ dài k. Lúc bấy giờ chỉ có 5 số Van de Waerden được biết đến(đến bây giờ là 6 số). Những số này thu được bằng sự hỗ trợ rất nhiều từ máy tính.Thời gian dài sau đó các nhà toán học chỉ nghiên cứu về các chặn của số Van de Waerden,nghiên cứu các vấn đề liên quan (những hệ quả và áp dụng) của định lý và cách chứngminh của nó. Nhưng mãi đến năm 1986 sau chứng minh của Shelah, số Van de Waerdenmới có chặn trên đệ quy. Sau đó Gowers cải thiện chặn trên của số Van de Waerden saunhững chứng minh của định Szemerédi về cấp số cộng. Về các chặn dưới có nhiều kết quảKỷ yếu Hội nghị Khoa học Sinh viên năm học 2013-2014Trường Đại học Sư phạm Huế, tháng 12/2013: tr. 5-186 ĐỖ VIẾT LÂN - NGUYỄN ĐẮC HIẾUđóng góp của Erdos và Rado, hay của Berlekamp. Việc tìm số Van de Waerden cũng nhưtìm các chặn tốt cho nó vẫn còn là khó khăn không nhỏ.Tuy vậy việc sử dụng các kết quả của định lý trong các trò chơi hay các bài toán sơ cấpđược sử dụng khá nhiều, đặc biệt là trong các kỳ thi quốc gia, quốc tế về rời rạc. Định lýVan de Waerden phát biểu như thế nào? Các chặn là gì? Trò chơi liên quan đến định lývới luật chơi ra sao? Việc sử dụng định lý trong các bài toán sơ cấp như thế nào? Các vấnđề trên sẽ được trình bày trong bài báo này.3 ĐỊNH LÝ VAN DE WAERDEN. CÁC SỐ VAN DE WAERDEN3.1 Một số khái niệm và định lý về đồ thị3.1.1 Đồ thị (i) Cho V là một tập hợp bất kì. E là một tập con của [V ]2 , với [V ]2 là tập tất cả những tập con gồm hai phần tử của V . Khi đó cặp G = (V, E) được gọi là một đồ thị trên V. Mọi phần tử của V được gọi là đỉnh của đồ thị G. Mọi phần tử của E là một cặp phần tử của V , được gọi là cạnh của đồ thị G. (ii) Đồ thị G0 = (V 0 , E 0 ) là đồ thị con của G = (V, E) nếu V 0 ⊆ V và E 0 ⊆ E. Đồ thị G0 = (V 0 , E 0 ) là đồ thị con cảm sinh của G = (V, E) nếu G0 là đồ thị con của G và với mọi a, b ∈ V 0 mà ab ∈ E thì ab ∈ E 0 . Ký hiệu G0 = G[V 0 ] Đồ thị G0 = (V 0 , E 0 ) là đồ thị con bao trùm của G = (V, E) nếu G0 là đồ thị con của G và V 0 = V . (iii) Tập đỉnh của đồ thị G được ký hiệu là V (G), tập các cạnh của G được ký hiệu là E(G). (iv) Một r - tô màu cạnh của đồ thị G là một hàm χ : E(G) → C, trong đó |C| = r. Thông thường, ta sử dụng tập C = {0, 1, . . . , r − 1} hay C = {1, 2, . . . , r}. Ta có thể xem một r - tô màu cạnh χ của đồ thị G như một cách phân chia tập E(G) vào r tập con E1 , E2 , . . . , Er mà Ei = {x ∈ E(G)|χ(x) = i}.Để biết thêm về lý thuyết đồ thị có thể tìm hiểu ở tài liệu [1, 3]3.1.2 Định lý RamseyNgười ta có thể đặt ra nhiều vấn đề về phân hoạch tập hợp từ định lý Ramsey dược phátbiểu dưới đây:VỀ MỘT SỐ BÀI TOÁN PHÂN HOẠCH TẬP HỢP... 7Định lý 3.1. (Định lý Ramsey hai màu)Cho k, l ≥ 2. Khi đó tồn tại số R = R(k, l) sao cho mọi tô màu các cạnh của đồ thị đầyđủ KR với hai màu xanh và đỏ thì luôn có đồ thị con đầy đủ Kk màu đỏ hoặc đồ thị conđầy đủ Kl màu xanh.Tổng quát hơn, định lý Ramsey cũng đúng cho trường hợp nhiều màu nhiều màuĐịnh lý 3.2. (Định lý Ramsey)Cho r ≥ 2 và các số k1 , k2 , . . . , kr ≥ 2. Khi đó tồn tại số R = R(k1 , k2 , . . . , kr ) sao cho mọir - tô màu các cạnh của đồ thị đầy đủ KR với r màu thì luôn có đồ thị con đầy đủ Kkicùng màu.Sau thời gian dài nổ lực các nhà toán học cũng chỉ thu được một số kết quả hiếm hoi vềcác giá trị của số Ramsey (xem [1] p.21) (i) R(k, l) = R(l, k) với mọi số nguyên k, l ≥ 2. (ii) R(2, n) = n với mọi số nguyên n ≥ 2. (iii) R(3, 3) = 6, R(3, 4) = 9, R(3, 5) = 14, R(3, 6) = 18, R(4, 4) = 36, R(4, 5) = 25, R(3, 7) = 23, R(3, 8) = 28, R(3, 9) = 36. (iv) R(3, 3, 3) = 173.1.3 Định lý SchurTừ định lý Ramsey ta có thể chứng minh được định lý Schur trong trường hợp tổng quát.Định lý 3.3. (Định lý Schur)Nếu r, k là các số nguyên dương thì tồn tại số nguyên dương S = S(k, r) sao cho vớibất kỳ r - tô màu χ : [1, S] → C thì tồn tại một tập con cùng màu của [1, S] có dạng{x1 , x2 , . . . , xk , x1 + x2 + . . . + xk }Thực tế ta chỉ cần lấy S = R(k + 1, k + 1, . . . , k + 1) − 1, trong đó R(k + 1, k + 1, . . . , k + 1)là số Ramsey r - màu, để chứng minh định lý trên là đúng. Trong trường hợp k = 2 ta c ...