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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:14

Thêm vào BST

Báo xấu

21
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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ọc 1 GIỚI THIỆU Chú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ã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. 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án trê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 de Waerden, đư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ấp liên quan đến định lý Schur, định lý Van de Waerden. 2 BÀI TOÁN PHÂN HOẠCH TẬP HỢP Sau 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ên tụ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ận ngày nay. Năm 1927, nhà toán học Van de Waerden đã đưa ra chứng minh trong trường hợp tổng quá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 de Waerden 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ất mộ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ứng minh của nó. Nhưng mãi đến năm 1986 sau chứng minh của Shelah, số Van de Waerden mới có chặn trên đệ quy. Sau đó Gowers cải thiện chặn trên của số Van de Waerden sau nhữ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-2014 Trường Đại học Sư phạm Huế, tháng 12/2013: tr. 5-18
6 ĐỖ 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 WAERDEN 3.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ý Ramsey Ngườ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át biể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ọi r - tô màu các cạnh của đồ thị đầy đủ KR với r màu thì luôn có đồ thị con đầy đủ Kki cù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) = 17 3.1.3 Định lý Schur Từ đị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ới bấ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ó định lý sau đây Định lý 3.4. (Định lý Schur) Với r ≥ 1, luôn tồn tại số nguyên dương nhỏ nhất s = s(r) sao cho với mọi r - tô màu của [1, s] thì tồn tại nghiệm đơn sắc của phương trình x + y = z Nhận xét 3.5.
8 ĐỖ VIẾT LÂN - NGUYỄN ĐẮC HIẾU (i) Trong định lý Schur các số x, y, z không nhất thiết phải khác nhau. (ii) Số nguyên dương thỏa mãn định lý Schur được gọi là số Schur và được ký hiệu là s(r). (iii) Một bộ số {x, y, z} thỏa mãn phương trình x + y = z trong định lý Schur được gọi là bộ số Schur. Hiện nay, người ta chỉ tìm ra các số Schur khi r = 1, 2, 3, 4. Cụ thể là s(1) = 2, s(2) = 5, s(3) = 14 và s(4) = 45. Khi r = 1 ta dễ dàng thấy được s(1) = 2 với bộ số Schur là {1, 1, 2}. Với những số r lớn hơn việc tìm ra s(r) khá khó khăn nên người ta tập trung vào tìm các chặn trên, chặn dưới cho số Schur. Ngay từ cách chọn S = R(k + 1, k + 1, . . . , k + 1) − 1 trong chứng minh định lý, ta có thể suy ra kết quả sau: Hệ quả 3.6. Với mọi r ≥ 1 ta luôn có s(r) ≤ Rr (3) − 1 Hệ quả 3.6 cho ta một chặn trên của s(r). Tuy nhiên chặn trên này chưa thực sự rõ ràng bởi nó còn phụ thuộc nhiều vào số Ramsey Rr (3), trong đó Rr (3) là ký hiệu cho số Ramsey r màu R(3, 3, . . . , 3). Như vậy yêu cầu đặt ra là phải tìm được chặn trên của số Ramsey Rr (3). Bổ đề 3.7. Với mọi r ≥ 1 ta có Rr (3) ≤ 3r!. Từ hệ quả 3.6 và bổ đề 3.7 ta có thể suy ra ngay định lý sau đây Định lý 3.8. Với mọi r ≥ 1 thì ta có s(r) ≤ 3.r! Trên đây là chặn trên của số Schur, định lý sau liên quan đến chặn dưới của số Schur. 3r +1 Định lý 3.9. Với mọi r ≥ 1 ta có s(r) ≥ 2 Ở định lý Schur, bộ số {x, y, z} thỏa mãn phương trình x + y = z trong đó x, y không nhất thiết phân biệt. Khi thay đổi phương trình x + y = 2z và x, y phân biệt thì ta có một kết quả của định lý Van de Waerden mà chúng ta cùng tìm hiểu ở phần tiếp theo. 3.2 Định lý Van de Waerden 3.2.1 Định lý Van de Waerden Nếu xem x, z, y nêu ở cuối phần trên là một cấp số cộng độ dài 3 thì ta có thể phát biểu lại như sau: "Với r ≥ 1, luôn tồn tại số nguyên dương nhỏ nhất s = s(r) sao cho với mọi r - tô màu của [1, s] thì tồn tại một cấp số cộng cùng màu có độ dài 3". Khi thay bộ ba x, y, z bởi cấp số cộng độ dài k thì ta có phát biểu của định lý Van de Waerden như sau
VỀ MỘT SỐ BÀI TOÁN PHÂN HOẠCH TẬP HỢP... 9 Định lý 3.10. (Định lý Van de Waerden) Cho k, r ≥ 2 là những số nguyên. Khi đó tồn tại số nguyên dương nhỏ nhất w = w(r; k) sao cho với mỗi số nguyên n ≥ w và với mọi r - tô màu của [1, n] đều tồn tại cấp số cộng cùng màu có độ dài k. Ngoài định lý đã được phát biểu ở trên, định lý Van de Waerden có nhiều dạng tương đương sau Định lý 3.11. Các khẳng định sau là tương đương (i) Với k ≥ 2, với 2 - tô màu bất kỳ của Z+ luôn tồn tại cấp số cộng cùng màu độ dài k. (ii) Với k ≥ 2 thì tồn tại số w(2; k). (iii) Với k, r ≥ 2 thì số w(r; k) tồn tại. (iv) Cho r ≥ 2. Với mọi r - tô màu của Z+ và tập S = {s1 , s2 , . . . , sn } ⊂ Z+ thì tồn tại các số nguyên a, d ≥ 1 sao cho a + dS = {a + s1 d, a + s2 d, . . . , a + sn d} là đợn sắc. (v) Với k, r ≥ 2, mọi r - tô màu bất kỳ của Z+ luôn tồn tại cấp số cộng cùng màu độ dài k. (vi) Với k ≥ 2, tập bất kỳ chứa vô hạn các số nguyên dương S = {si }i≥0 sao cho tồn tại số c = max{|si+1 − si | : i ≥ 0} thì luôn chứa cấp số cộng độ dài k. 3.2.2 Số Van de Waerden Cho đến ngày nay, có rất ít số Van de Waerden được biết. Số Van de Waerden w(r; k) với k = 2 là trường hợp tầm thường của số Van de Waerden. Mệnh đề 3.12. Với mọi r ≥ 2 thì luôn có w(r; 2) = r + 1. Chứng minh định lý trên có thể suy ra ngay từ nguyên lý Dirichlet: tô màu r + 1 số với r màu thì luôn tồn tại 2 số nào đó cùng màu. Với trường hợp không tầm thường (k ≥ 3), người ta chỉ tính được một số giá trị của số Van de Waerden: w(2; 3) = 9; w(3; 3) = 27; w(4; 3) = 76; w(2; 4) = 35; w(2; 5) = 178 Cho đến năm 2008, Kouril công bố kết quả cho W (2; 6) là 1132 trong bài báo " The Van de Waerden number W (2; 6) is 1132" (xem [2]) Tuy nhiên những số Van de Waerden được tìm ra nhờ sự hỗ trợ rất lớn từ máy tính. Kể cả khi ta có sự hỗ trợ từ các máy tính thì việc tìm ra các số Van de Waerden cũng không hề dễ dàng. Chẳng hạn với số w(3, 5), thấy rằng w(5; 3) > 76 nếu cho máy tính thử các 5 - tô màu của [1,77] thì phải mất đến hàng nghìn năm! Sự khó khăn quá lớn đó đã khiến
10 ĐỖ VIẾT LÂN - NGUYỄN ĐẮC HIẾU một số nhà toán học chuyển hướng sang nghiên cứu các số Van de Waerden ở dạng khác, chẳng hạn thay vì giả thiết có cấp số cộng độ dài 4 thì chuyển sang giả thiết có cấp số cộng độ dài 3 hoặc 4. Khi nghiên cứu các số ở dạng này, các nhà toán học thu được nhiều kết quả hơn. Bảng 1 dưới đây là một trong số các kết quả đó. r k1 k2 k3 w 2 4 3 - 18 2 5 3 - 22 2 5 4 - 55 3 3 3 2 14 3 4 3 2 21 3 4 3 3 51 3 5 3 2 32 Bảng 1: Một số số Van de Waerden hỗn hợp Các nhà toán học tiếp tục với số Van de Waerden cổ điển thì chuyển sang nghiên cứu chặn trên, chặn dưới của số Van de Waerden để tiến tới tìm giá trị chính xác của chúng. Định lý 3.13. (Berlekamp 1968) Cho p là một số nguyến tố thì w(2; p + 1) ≥ p.2p √ k−1 Định lý 3.14. Cho k ≥ 2 thì w(2; k) ≥ k.2 2 (1 − o(1)) Hai định lý trên phát biểu cho trường hợp đặc biệt của số Van de Waerden với 2 - tô màu. Với số Van de Waerden nhiều màu ta có hai định lý sau Định lý 3.15. Cho p ≥ 5 và q là số nguyên tố. Khi đó w(q; p + 1) ≥ p(q p − 1) + 1. rk Định lý 3.16. Với mọi k ≥ 2 thì w(r; k) ≥ ekr (1 + o(1)) Cho đến ngày nay, cùng với máy tính và nhiều phương pháp tìm chặn dưới mới, chúng ta có chặn dưới tốt nhất cho các số Van de Waerden (xem thêm tài liệu [5]) Về các chặn trên, năm 1988 Shelah chứng minh các chặn trên cho w(r; k) trong trường hợp k = 3, k = 4 (xem thêm [4]) Định lý 3.17. Với r ≥ 2 ta có
VỀ MỘT SỐ BÀI TOÁN PHÂN HOẠCH TẬP HỢP... 11 r\k 3 4 5 6 7 8 9 2 9 35 175 1132 > 3703 > 11495 > 41265 3 27 > 292 > 2173 > 11191 > 48811 > 238400 4 76 > 1048 > 17705 > 91331 > 420217 5 > 170 > 2254 > 98740 > 540025 6 > 223 > 9778 > 98748 > 816981 Bảng 2: Các chặn dưới số Van de Waerden c1 c1 er w(r; 3) ≤ er và w(r; 4) ≤ ee với c1 , c2 là một hằng số nào đó. Định lý sau đây được phát biểu bởi Gowers cho trường hợp r = 2 Định lý 3.18. Với k ≥ 2, k+9 22 22 w(2; k) ≤ 2 . Và trong trường hợp tổng quát Định lý 3.19. Với k, r ≥ 2 ta có 2k+9 r2 w(r; k) ≤ 22 4 ỨNG DỤNG ĐỊNH LÝ VAN DE WAERDEN 4.1 Trò chơi Van de Waerden Trò chơi Van de Waerden phát biểu như sau: Cho trước hai số n và k, tập hợp [1,n] và 2 người chơi (hoặc nhiều hơn). Trong mỗi lượt chơi mỗi người chọn cho mình đúng một số (mỗi số chỉ có một người được chọn) và cố gắng tạo ra cấp số cộng độ dài k đồng thời ngăn chặn đối phương tạo ra cấp số cộng. Người chiến thắng là người tạo ra cấp số cộng trước. Từ các định lý đã nêu ở mục 2 ta có kết quả trong trường hợp hai người chơi: (i) Nếu thay tập [1,n] bằng tập Z+ thì người thứ nhất luôn luôn thắng vì nếu có chiến thuật thắng cho người thứ hai thì người thứ nhất chọn một số rồi xem mình là người thứ hai và áp dụng chiến thuật đó (điều này làm được vì Z+ là vô hạn). (ii) Nếu n = w(2; k) thì người thứ nhất sẽ thắng nếu có chiến thuật đúng đắn.
12 ĐỖ VIẾT LÂN - NGUYỄN ĐẮC HIẾU (iii) Nếu n < w(2; k) và chiến thuật của người thứ hai là đúng thì kết quả sẽ là hòa. Tuy nhiên việc tìm ra chiến lược chơi cho các trò chơi này vẫn là bài toán mở. Sau đây ta xét 2 trường hợp đơn giản với 2 người chơi 4.1.1 Cần tạo cấp số cộng độ dài 3 Theo định lý Van de Waerden (số w(2; 3) = 9) thì với n bằng 9 hoặc lớn hơn sẽ đảm bảo rằng trò chơi sẽ kết thúc và có người thắng. Nhưng thực tế chỉ cần với n = 7 thì người thứ nhất sẽ chết thắng với chiến thuật thích hợp. Nếu muốn chiến thắng người thứ nhất (người I) phải chọn 3 hoặc 5 trong lượt đi đầu tiên. Giả sử người I chọn 3 trong lượt đi đầu (ta có thể giả sử như vậy bởi trong tập [1,7], vị trí của 3 và 5 là như nhau). Trong lượt đi của người thứ hai (người II), có 2 tình huống xảy ra: người đó chọn 5 hoặc không chọn 5 Nếu người II không chọn 5 trong lượt thứ nhất thì người I sẽ chọn 5 ở lượt thứ hai. Và ở lượt thứ ba có thể chọn 1 hoặc 4 hoặc 7 để chiến thắng vì lúc này người II đã đi được 2 lượt nên không thể chọn được cả 3 số 1, 4 và 7. Hình 1: Sau hai lượt chơi. Người I có thể chọn 1 để thắng. Nếu người II chọn 5 trong lượt đi thứ nhất thì ở lượt thứ hai người I chọn 2 và lượt thứ ba sẽ chọn 1 hoặc 4 để chiến thắng (vì lúc này người II chỉ chọn được 2 số nên không thể chọn cả 4 và 1). Hình 2: Người II chỉ chọn được 1 hoặc 4. Người I chọn số còn lại để thắng Người I luôn thắng nếu chọn một trong hai số 3 hoặc 5. Đó là một chiến thuật thắng của trò chơi. Câu hỏi trong trường hợp này là liệu có còn chiến thuật nào để thắng? Bây giờ ta kiểm tra các trường hợp còn lại để chứng tỏ rằng đó là chiến thuật duy nhất để người I thắng. Xét một chiến thuật chơi, chú ý đến sự đối xứng, ta có thể giả sử ở lượt thứ nhất người I chọn các số từ 1 đến 4.
VỀ MỘT SỐ BÀI TOÁN PHÂN HOẠCH TẬP HỢP... 13 Trường hợp 1: Nếu người I chọn 1. Sau đó người II chọn 3. Ở lượt tiếp theo, nếu người I chọn 2 hoặc 6 hoặc 7 thì sẽ thua sau 2 lượt chơi (xem hình vẽ) Hình 3: Trong lượt tiếp người II có 2 lựa chọn ở vị trí * để thắng Nếu ở lượt thứ hai người I chọn 4 thì các nước đi tiếp theo chỉ có một khả năng (như hình vẽ) và dẫn đến kết quả hòa. Hình 4: Các nước đi phải theo thứ tự Nếu ở lượt thứ hai người I chọn 5 thì người II sẽ chọn 4 (vì người II muốn tạo ra cấp số cộng) và buộc người I phải chọn 2. Hình 5: Kết quả sẽ là hòa Trường hợp 2: Nếu người I chọn 2 ở lượt đầu. Sau đó người II chọn 3. Ở lượt tiếp theo, nếu người I chọn 1 hoặc 6 hoặc 7 thì sẽ thua sau 2 lượt chơi (xem hình vẽ) Nếu ở lượt thứ hai người I chọn 4 thì các nước đi tiếp theo chỉ có một khả năng (như hình vẽ) và dẫn đến kết quả hòa. Nếu ở lượt thứ hai người I chọn 5 thì người II sẽ chọn 6. Lúc này không ai có thể tạo ra cấp số cộng độ dài 3. Trường hợp 3: Nếu người I chọn 4 ở lượt đầu. Sau đó người II chọn 5. Ở lượt tiếp theo, nếu người I chọn 2 hoặc 6 thì sẽ thua sau 2 lượt chơi (xem hình vẽ)
14 ĐỖ VIẾT LÂN - NGUYỄN ĐẮC HIẾU Hình 6: Trong lượt tiếp người II có 2 lựa chọn ở vị trí * để thắng Hình 7: Không ai có thể tạo ra cấp số cộng Hình 8: Kết quả sẽ là hòa Hình 9: Trong lượt tiếp người II có 2 lựa chọn ở vị trí * để thắng Nếu ở lượt thứ hai người I chọn 1 hoặc 7 thì các nước đi tiếp theo chỉ có một khả năng (như hình vẽ) và dẫn đến kết quả hòa. Hình 10: Không ai có thể tạo ra cấp số cộng Nếu ở lượt thứ hai người I chọn 3 thì người II phải chọn 2. Để tạo ra cấp số cộng thì người I phải chọn 1 hoặc 7, khi đó người II chọn số còn lại. Hình 11: Kết quả sẽ là hòa
VỀ MỘT SỐ BÀI TOÁN PHÂN HOẠCH TẬP HỢP... 15 Cũng từ những phân tích trên ta có thể rút ra chiến thuật của người II: chọn 3 hoặc 5 để đưa đến kết quả hòa. Và với lập luận tương tự có thể chỉ ra rằng với n = 6 thì với chiến thuật đúng thì kết quả sẽ là hòa. 4.1.2 Cần tạo cấp số cộng độ dài 4 Tương tự mục trên, với số người chơi là 2 và cấp số cộng cần tạo có độ dài 4 thì số w(2; 4) = 35 cho ta số n để đảm bảo trò chơi kết thúc và chắc chắn có người thắng. Thực tế sau khi thử với các số n khác nhau chúng tôi đã đưa ra được chiến thuật thắng cho người chơi thứ nhất (người I) chỉ với n = 17 (nhỏ hơn số w(2; 4) nhiều!). Dưới đây chúng tôi chỉ đưa ra chiến thuật thằng cho người I và không đề cập đến câu hỏi liệu với số n nhỏ hơn có thể tìm được chiến thuật thắng hay không? Chiến thuật để người I thắng là sau lượt của mình sẽ tạo ra 2 khả năng thắng. Khi đó người II không thể ngăn cản được. Cách chơi như sau: Ở lượt đầu, người I chọn số 9 vì nó "ở chính giữa". Trong lượt thứ nhất, người II có thể đánh bất kỳ số nào, ta có thể giả sử người II chọn số lớn hơn 9 (vì nếu ngược lại ta chỉ lập luận tương tự) Nếu ở lượt 1, người II chọn một trong các số 10, 12, 14, 16 thì người I sẽ thắng sau khi chọn số 13. Bởi ở lượt 2 có 2 khả năng xảy ra cho người II: Trường hợp 1: Nếu người II chọn không chọn 11 hoặc 15 thì người I sẽ chọn 11 ở lượt 3 và tạo ra 2 khả năng thắng ở lượt 4 (lúc này người II mới chọn 3 số nên không thể có cấp số cộng trước người I). Trường hợp 2: Nếu người II chọn 11 hoặc 15 thì ở lượt 3 người I chọn 5 và tạo ra 2 khả năng thắng. Trò chơi kết thúc ở lượt 4 khi người I chọn ra bộ số {1, 5, 9, 13} hoặc {5, 9, 13, 17}. Hình 12: Trong lượt tiếp người I có 2 lựa chọn ở vị trí * để thắng Nếu người II chọn 11 trong lượt 1. Trong lượt 2 người I chọn 7 khi đó lượt 2 của người II có các khả năng sau: Trường hợp 1: Nếu người II không chọn 6, 8, 10 thì người I sẽ thắng ở lượt 4 khi chọn 8 ở lượt 3 và tạo cho mình 2 "con đường thắng". Trường hợp 2: Nếu người II chọn một trong các số 6, 8, 10 thì ở lượt 3 người I chọn 5 buộc
16 ĐỖ VIẾT LÂN - NGUYỄN ĐẮC HIẾU người II phải chặn tại 3. Khi đó người I sẽ kết thúc trò chơi khi tạo cho mình 2 khả năng thắng bằng cách chọn 13 (lưu ý là lúc này người II chưa thể tạo ra cấp số cộng). Hình 13: Trong lượt tiếp người I có 2 lựa chọn ở vị trí * để thắng Nếu người II chọn 13 hoặc 15 hoặc 17 trong lượt 1. Ở lượt 2 người I chọn 7 khi đó lượt 2 của người II có các khả năng sau: Trường hợp 1: Nếu người II không chọn 5 thì người I sẽ chọn 5 ở lượt 3 tạo 2 khả năng thắng ở lượt 4. Trường hợp 2: Nếu người II chọn 5 thì người I sẽ thắng ở lượt 4 khi chọn 8 ở lượt 3. Hình 14: Trong lượt tiếp người I có 2 lựa chọn ở vị trí * để thắng 4.2 Các bài toán sơ cấp Trong mục này chúng tôi giới thiệu một số bài toán sơ cấp mà chứng minh được suy ra từ định lý Van de Waerden Bài toán 1. (RMO 78) Xét tập X = {1, 2, 3, 4, 5, 6, 7, 8, 9}. Chứng minh rằng với mỗi cách phân hoạch tập X thành hai tập thì luôn tồn tại một tập chứa 3 phần tử lập thành một cấp số cộng. HD w(2; 3) = 9. Bài toán 2. Cho dãy vô hạn số nguyên dương (an )n∈N thỏa mãn: 0 < an+1 − an ≤ r. Chứng minh rằng dãy chứa cấp số cộng độ dài k bất kỳ. HD Sử dụng các mệnh đề tương đương nêu trong định lý 3.11 Bài toán 3. Cho hình 9 cạnh đều. Tô màu các đỉnh của đa giác bởi hai màu xanh và đỏ. Chứng minh rằng tồn tại tam giác cân có các đỉnh cùng màu.
VỀ MỘT SỐ BÀI TOÁN PHÂN HOẠCH TẬP HỢP... 17 HD Suy ra ngay từ định lý w(2; 3) = 9. Bài toán 4. (Bulgaria 1998) Tìm số n nhỏ nhất thỏa mãn: với n điểm bất kỳ trên đường tròn A1 , A2 , . . . , An thỏa mãn A1 A2 = A2 A3 = . . . = An−1 An thì với 2 tô màu bất kì tồn tại Ai , Aj , A2j−1 có cùng màu HD Ai , Aj , A2j−1 có cùng màu nghĩa là tam giác cân Ai Aj A2j−1 . Làm tương tự bài toán 3, ta có kết quả n = 9 Qua bài toán 4 trong giả thiết hình 9 - cạnh đều ở bài toán 3, ta thấy rằng giả thiết "đều" là không cần thiết. Bỏ đi giả thiết đó ta có bài toán sau Bài toán 5. Với 9 điểm bất kỳ trên đường tròn A1 , A2 , . . . , A9 thỏa mãn A1 A2 = A2 A3 = . . . = A8 A9 . Tô màu 9 điểm đó bởi hai màu xanh và đỏ. Chứng minh rằng tồn tại tam giác cân có các đỉnh cùng màu. Quay trở lại bài toán 3, nếu vẫn giữ giả thiết đa giác đều thì giả thiết nào cần phải thay đổi để giả thiết không bị "thừa"? Ta xét bài toán sau đây: Bài toán 6. Cho hình 7 - cạnh đều. Tô màu các đỉnh của đa giác bởi hai màu xanh và đỏ. Chứng minh rằng tồn tại tam giác cân có các đỉnh cùng màu. Bài toán 7. Có 5 học sinh của lớp 3B cùng ngồi vào một bàn dài. Các chỗ ngồi đã được đánh số từ 1 đến 5. Chứng minh rằng có 3 học sinh cùng là nam hoặc nữ sao cho 1 học sinh có số chỗ bằng tổng số chỗ của hai học sinh còn lại hoặc có 2 học sinh cùng là nam hoặc nữ sao cho số chỗ học sinh này gấp đôi học sinh kia. HD Sử dụng cách chứng minh s(2) = 5. Từ định lý Schur và chặn dưới của số Schur ta có thể phát biểu một số bài toán tương tự bài toán 8. Chẳng hạn với s(3) = 14 ta có bài toán Bài toán 8. Các lớp năm 2 của khoa toán (gồm 3 lớp 2A, 2B và 2C) cùng tham gia vào một đội trong giải bóng chuyền của trường. Đội bóng chuyền gồm 14 người mang số áo từ 1 đến 14. Chứng minh rằng có 3 sinh viên của cùng một lớp trong đó có một sinh viên mang số áo bằng tổng số áo của 2 sinh viên còn lại hoặc có 2 sinh viên cùng lớp mà áo người này có số gấp đôi người kia. Từ số Van de Waerden ở dạng khác ta có thể phát biểu bài toán tương tự bài toán 6. Chẳng hạn với w(2; 3, 4) = 18 ta có bài toán Bài toán 9. Với 18 điểm bất kỳ trên đường tròn A1 , A2 , . . . , A18 thỏa mãn A1 A2 = A2 A3 = . . . = A1 7A1 8. Chứng minh rằng khi tô màu 18 điểm đó bởi hai màu xanh và đỏ thì tồn tại tam giác cân có các đỉnh cùng màu hoặc tồn tại hình thang cân có các đỉnh cùng màu.
18 ĐỖ VIẾT LÂN - NGUYỄN ĐẮC HIẾU TÀI LIỆU THAM KHẢO [1] Lanman Bruce; Aaron Robertson (2004), Ramsey Theory on the Integers, American Mathematical Society. [2] Kouril M.; Paul J. L. (2008), The Van de Waerden number W (2; 6) is 1132, Experi- mential Mathematics. [3] Reinhard Diestel (2010), Graduate Texts in Mathematics - Graph Theory, Springer. [4] Shelah S. (1988), Primitive Recursive Bounds for Van de Waerden numbers, Journal of the American Mathematical Society. [5] Herwig P. R., Heule M. J. H., van Lambalgen P. M., van Maaren H. (2007), A New Method to Construct Lower Bounds for Van de Waerden numbers, The Electronic Journal of Combinatorics. [6] Các đề thi lấy từ trang http://www.artofproblemsolving.com/Forum/resources.php [7] Các thông tin lấy từ trang http://mathworld.wolfram.com/ ĐỖ VIẾT LÂN NGUYỄN ĐẮC HIẾU SV lớp Toán 3A, Khoa Toán học, Trường Đại học Sư phạm - Đại học Huế ĐT: 0984.243.254, Email: vietlan2005@gmail.com