- Trang Chủ
- Toán họ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
Xem mẫ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
ĐỖ 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
nguon tai.lieu . vn
