Bài giảng Nguyên lý chuồng bồ câu

Nguyên lý chuồng bồ câu

Nguyên lý chuồng bồ câu1

HUST

Trần Vĩnh Đức

1Tham 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

Ngày 17 tháng 2 năm 2014

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

. . . . . .

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ụ

Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014

3 / 44

.Trong 13 người có ít nhất 2 người sinh cùng tháng.

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 (cid:20) k < ℓ (cid:20) m sao cho

ak+1 + ak+2 + (cid:1) (cid:1) (cid:1) + aℓ

Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014

4 / 44

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. .

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 (cid:0) 1. Vậy thì có hai số k; ℓ và k < ℓ sao cho a1 + (cid:1) (cid:1) (cid:1) + ak và a1 + (cid:1) (cid:1) (cid:1) + aℓ có cùng phần dư là r khi chia cho m:

a1 + a2 + (cid:1) (cid:1) (cid:1) + ak = bm + r; a1 + a2 + (cid:1) (cid:1) (cid:1) + aℓ = cm + r

Nguyên lý chuồng bồ câu | Nguyên lý chuồng bồ câu

Trừ hai tổng này ta được ak+1 + (cid:1) (cid:1) (cid:1) + aℓ = (c (cid:0) b)m. Vậy ak+1 + ak+2 + (cid:1) (cid:1) (cid:1) + aℓ chia hết cho m.

..Chứng minh.

Ta xét m tổng

a1; a1 + a2; : : : ; a1 + a2 + (cid:1) (cid:1) (cid:1) + am:

Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014

5 / 44

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 (cid:0) 1. Vậy thì có hai số k; ℓ và k < ℓ sao cho a1 + (cid:1) (cid:1) (cid:1) + ak và a1 + (cid:1) (cid:1) (cid:1) + aℓ có cùng phần dư là r khi chia cho m:

a1 + a2 + (cid:1) (cid:1) (cid:1) + ak = bm + r; a1 + a2 + (cid:1) (cid:1) (cid:1) + aℓ = cm + r

Nguyên lý chuồng bồ câu | Nguyên lý chuồng bồ câu

Trừ hai tổng này ta được ak+1 + (cid:1) (cid:1) (cid:1) + aℓ = (c (cid:0) b)m. Vậy ak+1 + ak+2 + (cid:1) (cid:1) (cid:1) + aℓ chia hết cho m.

..Chứng minh.

Ta xét m tổng

a1; a1 + a2; : : : ; a1 + a2 + (cid:1) (cid:1) (cid:1) + 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

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 + (cid:1) (cid:1) (cid:1) + am:

a1 + a2 + (cid:1) (cid:1) (cid:1) + ak = bm + r; a1 + a2 + (cid:1) (cid:1) (cid:1) + aℓ = cm + r

Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014

5 / 44

Trừ hai tổng này ta được ak+1 + (cid:1) (cid:1) (cid:1) + aℓ = (c (cid:0) b)m. Vậy ak+1 + ak+2 + (cid:1) (cid:1) (cid:1) + aℓ chia hết cho m. .

Nguyên lý chuồng bồ câu | Nguyên lý chuồng bồ câu

..Ví dụ

Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014

6 / 44

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. .

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 (cid:20) ai (cid:20) 45. Và a1 + 14; a2 + 14; : : : ; a30 + 14 cũng là dãy tăng chặt và thỏa mãn

15 (cid:20) ai + 14 (cid:20) 59

Dãy sau gồm 60 số nguyên dương

a1; a2; : : : ; a30; a1 + 14; a2 + 14; : : : ; a30 + 14

Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014

7 / 44

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. .

Nguyên lý chuồng bồ câu | Nguyên lý chuồng bồ câu

..Ví dụ

Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014

8 / 44

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. .

Nguyên lý chuồng bồ câu | Nguyên lý chuồng bồ câu

..Ví dụ

Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014

9 / 44

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. .

Nguyên lý chuồng bồ câu | Nguyên lý chuồng bồ câu

..Chứng minh.

Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014

10 / 44

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 (cid:2) a, với k (cid:21) 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 (cid:2) a và 2s (cid:2) 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). .

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 (cid:20) a (cid:20) m và 0 (cid:20) b (cid:20) n (cid:0) 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

Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014

11 / 44

x = pm + a và x = qn + b: .

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 (cid:0) 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 (cid:20) i < j (cid:20) n (cid:0) 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

và im + a = qin + r jm + a = qjn + r:

Trừ hai vế ta được

Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014

12 / 44

(j (cid:0) i)m = (qj (cid:0) qi)n: Vậy n là ước của (j (cid:0) i)m. Vì m và n nguyên tố cùng nhau nên n phải là ước của j (cid:0) i, nhưng vì i < j < n (cid:0) 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.

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 (cid:0) 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

Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014

13 / 44

là số thỏa mãn yêu cầu.

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

. . . . . .

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 + (cid:1) (cid:1) (cid:1) + qn (cid:0) n + 1

Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014

15 / 44

đố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. .

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 = (cid:1) (cid:1) (cid:1) = qn = 2

Tức là nếu có

2 + 2 + (cid:1) (cid:1) (cid:1) + 2 (cid:0) n + 1 = 2n (cid:0) n + 1

= n + 1

Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014

16 / 44

đối tượng đặt trong n chiếc lồng, thì có lồng chứa ít nhất hai đối tượng.

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 (cid:0) 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

Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014

17 / 44

q1 = q2 = (cid:1) (cid:1) (cid:1) = qn = r

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 (cid:0) 1, tức là

> r (cid:0) 1: m1 + m2 + (cid:1) (cid:1) (cid:1) + mn n

Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014

18 / 44

Vậy có ít nhất một số mi lớn hơn hoặc bằng r. .

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à

< r + 1: m1 + m2 + (cid:1) (cid:1) (cid:1) + mn n

Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014

19 / 44

Vậy có ít nhất một số mi nhỏ hơn hoặc bằng r. .

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ụ

Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014

20 / 44

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? .

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.

Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014

21 / 44

Đặ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. .

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

Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014

22 / 44

đề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ố. .

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

. . . . . .

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à toán học người Anh. Nói chung, lý thuyết Ramsey giải quyết những bài toá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

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”

Nguyên lý chuồng bồ câu | Định lý Ramsey

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”

..Khẳng định

Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014

25 / 44

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. .

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”

Nguyên lý chuồng bồ câu | Định lý Ramsey

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”

..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

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

Nguyên lý chuồng bồ câu | Định lý Ramsey

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”

..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

Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014

25 / 44

K6= “6 đối tượng và 15 cặp không thứ tự của các đối tượng này”

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

Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014

25 / 44

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

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

Vậy K6 ! K3; K3

có nghĩa là

Nguyên lý chuồng bồ câu | Định lý Ramsey

“Dù có tô xanh đỏ các cạnh của K6 ta luôn tìm được một K3 có toàn cạnh đỏ hoặc một K3 toàn cạnh xanh”

Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014

27 / 44

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 đỏ.

Nguyên lý chuồng bồ câu | Định lý Ramsey

“Dù có tô xanh đỏ các cạnh của K6 ta luôn tìm được một K3 có toàn cạnh đỏ hoặc một K3 toàn cạnh xanh”

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

Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014

27 / 44

có nghĩa là

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

“Dù có tô xanh đỏ các cạnh của K6 ta luôn tìm được một K3 có toàn cạnh đỏ hoặc một K3 toàn cạnh xanh”

Bây giờ, nếu tồn tại một cạnh nối giữa a (cid:0) b

hoặc a (cid:0) c hoặc b (cid:0) 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.

Nguyên lý chuồng bồ câu | Định lý Ramsey

... .. .. .. .. c .

Chứng minh K6 ! K3; K3

Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014

28 / 44

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.

Nguyên lý chuồng bồ câu | Định lý Ramsey

Chứng minh K6 ! K3; K3

Bây giờ, nếu tồn tại một cạnh nối giữa a (cid:0) b hoặc a (cid:0) c hoặc b (cid:0) 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.

Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014

28 / 44

.. ... .. .. .. c .

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

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 (cid:21) p ta luôn có

Nguyên lý chuồng bồ câu | Định lý Ramsey

Kp ! Km; Kn ) Kq ! Km; Kn:

Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014

30 / 44

..Định lý (Ramsey, dạng đơn giản) Với hai số nguyên m (cid:21) 2 và n (cid:21) 2, luôn tồn tại một số nguyên dương p sao cho Kp ! Km; Kn .

Rõ ràng, với mọi q (cid:21) p ta luôn có

Nguyên lý chuồng bồ câu | Định lý Ramsey

Kp ! Km; Kn ) Kq ! Km; Kn:

..Định lý (Ramsey, dạng đơn giản) Với hai số nguyên m (cid:21) 2 và n (cid:21) 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

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 (cid:21) 2 và n (cid:21) 2, luôn tồn tại một số nguyên dương p sao cho Kp ! Km; Kn .

Rõ ràng, với mọi q (cid:21) p ta luôn có

Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014

30 / 44

Kp ! Km; Kn ) Kq ! Km; Kn:

Dễ thấy r(m; n) = r(n; m):

..Ví dụ

Ta có r(3; 3) = 6

Nguyên lý chuồng bồ câu | Định lý Ramsey

vì K6 ! K3; K3 và K5 ̸! K3; K3: .

Số Ramsey

Số nguyên p nhỏ nhất sao cho Kp ! Km; Kn gọi là số Ramsey

Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014

31 / 44

r(m; n):

..Ví dụ

Ta có r(3; 3) = 6

Nguyên lý chuồng bồ câu | Định lý Ramsey

vì K6 ! K3; K3 và K5 ̸! K3; K3: .

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

Dễ thấy r(m; n) = r(n; m):

Nguyên lý chuồng bồ câu | Định lý Ramsey

K6 ! K3; K3 và K5 ̸! K3; K3:

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

Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014

31 / 44

vì .

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

Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014

31 / 44

K6 ! K3; K3 và K5 ̸! K3; K3: vì .

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

1 r(2, n) = r(n,2) = ?

Tính các số Ramsey sau

Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014

32 / 44

3 r(3,5) = r(5,3) = ?

Nguyên lý chuồng bồ câu | Định lý Ramsey

..Bài tập

1 r(2, n) = r(n,2) = ?

2 r(3,4) = r(4,3) = ?

Tính các số Ramsey sau

Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014

32 / 44

Nguyên lý chuồng bồ câu | Định lý Ramsey

..Bài tập

1 r(2, n) = r(n,2) = ?

2 r(3,4) = r(4,3) = ?

3 r(3,5) = r(5,3) = ?

Tính các số Ramsey sau

Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014

32 / 44

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

. . . . . .

Nguyên lý chuồng bồ câu | Chứng minh định lý Ramsey

Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014

34 / 44

..Định lý (Ramsey, dạng đơn giản) Với hai số nguyên m (cid:21) 2 và n (cid:21) 2, luôn tồn tại một số nguyên dương p sao cho Kp ! Km; Kn .

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

Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014

35 / 44

Ta chỉ ra sự tồn tại của r(m; n) bằng quy nạp theo cả m và n.

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

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

Đặt p = r(m (cid:0) 1; n) + r(m; n (cid:0) 1)

Nguyên lý chuồng bồ câu | Chứng minh định lý Ramsey

Ta sẽ chỉ ra rằng Kp ! Km; Kn.

Bước quy nạp

Giả sử rằng m (cid:21) 3 và n (cid:21) 3 và tồn tại cả

r(m; n (cid:0) 1) và r(m (cid:0) 1; n)

Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014

36 / 44

Nguyên lý chuồng bồ câu | Chứng minh định lý Ramsey

Ta sẽ chỉ ra rằng Kp ! Km; Kn.

Bước quy nạp

Giả sử rằng m (cid:21) 3 và n (cid:21) 3 và tồn tại cả

r(m; n (cid:0) 1) và r(m (cid:0) 1; n)

Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014

36 / 44

Đặt p = r(m (cid:0) 1; n) + r(m; n (cid:0) 1)

Nguyên lý chuồng bồ câu | Chứng minh định lý Ramsey

Bước quy nạp

Giả sử rằng m (cid:21) 3 và n (cid:21) 3 và tồn tại cả

r(m; n (cid:0) 1) và r(m (cid:0) 1; n)

Đặt p = r(m (cid:0) 1; n) + r(m; n (cid:0) 1)

Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014

36 / 44

Ta sẽ chỉ ra rằng Kp ! Km; Kn.

Vậy

jRxj + jBxj = p (cid:0) 1

= r(m (cid:0) 1; n) + r(m; n (cid:0) 1) (cid:0) 1

chỉ ra rằng

(1) jRxj (cid:21) r(m (cid:0) 1; n), hoặc

(2) jBxj (cid:21) r(m; n (cid:0) 1).

Nguyên lý chuồng bồ câu | Chứng minh định lý Ramsey

Chứng minh Kp ! Km; Kn

Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014

37 / 44

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.

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

jRxj + jBxj = p (cid:0) 1

= r(m (cid:0) 1; n) + r(m; n (cid:0) 1) (cid:0) 1

Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014

37 / 44

chỉ ra rằng (1) jRxj (cid:21) r(m (cid:0) 1; n), hoặc (2) jBxj (cid:21) r(m; n (cid:0) 1).

hoặc m (cid:0) 1 điểm của Kq (cũng thuộc Kp) có toàn cạnh màu đỏ. Ta có

Km(cid:0)1 đỏ, và tất cả m (cid:0) 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 toà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 jRxj (cid:21) r(m (cid:0) 1; n), ta đặt

q = jRxj

Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014

38 / 44

vậy q (cid:21) r(m (cid:0) 1; n). Xét Kq trên các điểm của Rx, ta thấy rằng

hoặc n điểm của Kq toà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 jRxj (cid:21) r(m (cid:0) 1; n), ta đặt

q = jRxj

vậy q (cid:21) r(m (cid:0) 1; n). Xét Kq trên các điểm của Rx, ta thấy rằng

hoặc m (cid:0) 1 điểm của Kq (cũng thuộc Kp) có toàn cạnh màu đỏ. Ta có Km(cid:0)1 đỏ, và tất cả m (cid:0) 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

Nguyên lý chuồng bồ câu | Chứng minh định lý Ramsey

Nếu jRxj (cid:21) r(m (cid:0) 1; n), ta đặt

q = jRxj

vậy q (cid:21) r(m (cid:0) 1; n). Xét Kq trên các điểm của Rx, ta thấy rằng

hoặc m (cid:0) 1 điểm của Kq (cũng thuộc Kp) có toàn cạnh màu đỏ. Ta có Km(cid:0)1 đỏ, và tất cả m (cid:0) 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 toà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

Nguyên lý chuồng bồ câu | Chứng minh định lý Ramsey

Nếu jRxj (cid:21) r(m (cid:0) 1; n), ta đặt

q = jRxj

vậy q (cid:21) r(m (cid:0) 1; n). Xét Kq trên các điểm của Rx, ta thấy rằng

hoặc m (cid:0) 1 điểm của Kq (cũng thuộc Kp) có toàn cạnh màu đỏ. Ta có Km(cid:0)1 đỏ, và tất cả m (cid:0) 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 toà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

Nguyên lý chuồng bồ câu | Chứng minh định lý Ramsey

Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014

39 / 44

Lập luận tương tự với jBxj (cid:21) r(m; n (cid:0) 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 (cid:21) 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

. . . . . .

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) (cid:20) r(m (cid:0) 1; n) + r(m; n (cid:0) 1) với m; n (cid:21) 3: (2)

( ) Xét

f(m; n) = : m + n (cid:0) 2 m (cid:0) 1

Dùng đẳng thức Pascal ta được ( ) ( ) ( )

= + m + n (cid:0) 2 m (cid:0) 1 m + n (cid:0) 3 m (cid:0) 1 m + n (cid:0) 3 m (cid:0) 2

Vậy ta được công thức tương tự như (2):

Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014

41 / 44

f(m; n) = f(m (cid:0) 1; n) + f(m; n (cid:0) 1):

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ó

Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014

42 / 44

r(m; n) (cid:20) = m + n (cid:0) 2 m (cid:0) 1 m + n (cid:0) 2 n (cid:0) 1

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;

r(3; 4) = r(4; 3) = 9; 40 (cid:20) r(3; 10) = r(10; 3) (cid:20) 43; r(4; 4) = 18;

r(3; 5) = r(5; 3) = 14;

r(3; 6) = r(6; 3) = 18;

r(3; 7) = r(7; 3) = 23;

r(3; 8) = r(8; 3) = 28;

Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014

43 / 44

r(3; 9) = r(9; 3) = 36; r(4; 5) = r(5; 4) = 25; 35 (cid:20) r(4; 6) (cid:20) 49; 43 (cid:20) r(5; 5) (cid:20) 49; 58 (cid:20) r(5; 6) = r(6; 5) (cid:20) 87; 102 (cid:20) r(6; 6) (cid:20) 165: . .

Ví dụ r(3; 3; 3) = 17:

Mở rộng tự nhiên cho m màu

Nguyên lý chuồng bồ câu | Ví dụ và tổng quát hóa

Kp ! Kn1; Kn2; (cid:1) (cid:1) (cid:1) ; Knm:

Tổng quát hoá

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

Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014

44 / 44

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 đỏ.

Mở rộng tự nhiên cho m màu

Nguyên lý chuồng bồ câu | Ví dụ và tổng quát hóa

Kp ! Kn1; Kn2; (cid:1) (cid:1) (cid:1) ; Knm:

Tổng quát hoá

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

Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014

44 / 44

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:

Nguyên lý chuồng bồ câu | Ví dụ và tổng quát hóa

Tổng quát hoá

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

Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014

44 / 44

Kp ! Kn1; Kn2; (cid:1) (cid:1) (cid:1) ; Knm: