Phép phân hoach tập hợp và quan hệ t−ơng đ−ơng
Trong bài viết này, chúng ta sẽ xem xét khái niệm phân hoạch tập hợp với giả thiết rằng X là một tập hợp khác rỗng Mục tiêu chính là giới thiệu mối liên hệ giữa các phép phân hoạch của tập X và các quan hệ tương đương trên tập này.
Phép phân hoạch tập X, hay còn gọi là sự chia lớp trên X, được định nghĩa là cách chia X thành một tập hợp các tập con không rỗng {Xi}i∈I Các tập con này phải thỏa mãn điều kiện rằng chúng không giao nhau, tức là Xi ∩ Xj = ∅ với mọi i, j ∈ I (với i khác j), và tổng hợp tất cả các tập con này lại phải bằng tập X, tức là X = S i∈I.
Nếu {Xi}i∈I là một phân hoạch của tập X, thì mỗi tập con Xi được gọi là một khối trong phân hoạch Nếu I có k phần tử, phân hoạch này được xem là gồm k khối.
1.1.2 Ví dụ (i) Nếu X = {a} thì X có đúng một phân hoạch, đó là phân hoạch thành một khối X.
(ii) Nếu X = {a, b} thì X có hai phân hoạch, phân hoạch thứ nhất thành một khối X; phân hoạch thứ hai gồm hai khối {a},{b}.
(iii) Nếu X = {a, b, c} thì có 5 phép phân hoạch tập X, đó là
{{a},{b},{c}}; {{a, b},{c}}; {{a, c},{b}}; {{b, c},{a}}; {{a, b, c}}, trong đó có một phân hoạch thành 1 khối, ba phân hoạch thành 2 khối, và một phân hoạch thành 3 khối.
(iv) Nếu X = {a, b, c, d} thì có 15 phép phân hoạch tập X, đó là
Tập hợp gồm 4 phần tử có 1 phân hoạch thành 1 khối là {abcd}
Tập hợp gồm 4 phần tử có 1 phân hoạch thành 4 khối là {a, b, c, d}
Tập hợp gồm 4 phần tử có 7 phân hoạch thành 2 khối là
Tập hợp gồm 4 phần tử có 6 phân hoạch thành 3 khối là
Phân hoạch của một tập hợp không bị ảnh hưởng bởi thứ tự của các phần tử Ví dụ, với tập X = {a, b, c}, các phân hoạch {{a},{b},{c}} và {{b},{a},{c}} được coi là giống nhau, tương tự như các phân hoạch {{a, c},{b}} và {{b},{a, c}} cũng là giống nhau.
Thực tế, có nhiều bài toán đ−ợc quy về bài toán phân hoạch tập hợp nh− các bài toán về xác xuất thống kê, về tổ hợp đồ thị,
Trong lý thuyết xác suất, cho không gian mẫu Ω của một phép thử, hệ biến cố gồm n biến cố A1, A2, A3, , An được gọi là một phân hoạch của không gian mẫu Ω nếu các biến cố này không giao nhau, tức là Ai ∩ Aj = ∅ với mọi i, j = 1, 2, 3, , n.
Hệ biến cố A1, A2, A3, , An tạo thành một hệ đầy đủ và đôi một xung khắc với nhau, có nghĩa là tổng hợp của chúng bằng không gian mẫu Ω Đối với một biến cố B bất kỳ trong phép thử, ta có thể áp dụng công thức đầy đủ và công thức Bayes để tính toán xác suất.
(i) P(B) = P(A1)P(B/A1) +P(A2)P(B/A2) + .+ P(An)P(B/An) (ii) P(Ai/B) = P(Ai)P(B/Ai)
Tiếp theo, chúng ta trình bày mối quan hệ giữa các phép phân hoạch tập
X với các quan hệ t−ơng đ−ơng trên X Nhắc lại rằng một tập con khác rỗng của tích Descartes X ìX đ−ợc gọi là một quan hệ (hai ngôi) trên X.
Ta th−ờng kí hiệu các quan hệ bằng các chữ R, S, T,Ω, hoặc các kí hiệu
Cho Ω là một quan hệ hai ngôi trên tập X Nếu (a, b) thuộc Ω, ta biểu thị là aΩb và nói rằng a quan hệ với b theo quan hệ Ω Dưới đây là một số tính chất quan trọng mà quan hệ Ω có thể có.
(ii) Đối xứng: Nếu aΩb thì bΩa với mọi a, b ∈ X.
(iii) Phản đối xứng: Nếu aΩb và bΩa thì a = b với mọi a, b ∈ X.
(iv) Bắc cầu: Nếu aΩb và bΩc thì aΩc với mọi a, b, c∈ X Chẳng hạn, với
Quan hệ chia hết Ω trên tập hợp X được định nghĩa là Ω ={(a, b) ∈ X × X | a là ước của b} và có các tính chất phản xạ, phản đối xứng và bắc cầu Điều này có nghĩa là aΩb nếu và chỉ nếu a là ước của b với mọi a, b thuộc X Quan hệ này cũng có thể được biểu diễn bằng cách liệt kê các cặp (a, b) tương ứng.
1.1.5 Định nghĩa Một quan hệ trên X đ−ợc gọi là quan hệ t−ơng đ−ơng nếu nó phản xạ, đối xứng và bắc cầu.
Theo truyền thống, quan hệ tương đương được ký hiệu bởi ∼ Giả sử ∼ là quan hệ tương đương trên tập X Đối với mỗi phần tử a thuộc X, lớp tương đương của a, ký hiệu là cl(a) (hoặc [a]), là tập hợp các phần tử của X có quan hệ với a, tức là cl(a) = {b ∈ X | b ∼ a}.
Tập các lớp t−ơng đ−ơng đ−ợc gọi là tập th−ơng của X theo quan hệ t−ơng đ−ơng ∼ và đ−ợc kí hiệu bởi X/ ∼ Nh− vậy
Hai phần tử a và b trong tập X được coi là tương đương, ký hiệu là a ∼ b, khi và chỉ khi tập đóng của a và b là giống nhau, tức là cl(a) = cl(b) Nếu a ∼ b, thì mọi phần tử x thuộc cl(a) cũng sẽ thuộc cl(b) do tính bắc cầu của quan hệ ∼ Ngược lại, nếu cl(a) = cl(b), thì theo tính phản xạ, a sẽ nằm trong cl(a) và do đó cũng nằm trong cl(b), dẫn đến a ∼ b.
1.1.6 Ví dụ Cho m ≥ 1 là một số tự nhiên Ta định nghĩa quan hệ
Trong toán học, quan hệ đồng dư (mod m) trên tập số nguyên Z được định nghĩa như sau: hai số a và b thuộc Z được coi là đồng dư theo môđun m (a ≡ b (mod m)) khi hiệu a − b là bội của m Quan hệ này là quan hệ tương đương, với tính chất phản xạ, đối xứng và bắc cầu Mỗi số nguyên a có một lớp tương đương, ký hiệu là a, gọi là lớp thặng dư theo môđun m, với tập thương Z m chứa các lớp thặng dư này Đối với mỗi a ∈ Z, có thể viết a = mq + r với 0 ≤ r < m, dẫn đến a ≡ r (mod m) Nếu r và s là hai số tự nhiên khác nhau trong khoảng từ 0 đến m−1, thì r − s không thể là bội của m, do đó r khác s Tập thương Z m bao gồm chính xác m phần tử: 0, 1, , m−1.
1.1.7 Mệnh đề Cho ∼ là quan hệ tương đương trên X Khi đó.
(iii) Nếu cl(a) 6= cl(b) thì cl(a)∩cl(b) = ∅ với mọi a, b ∈ X.
Chứng minh (i), (ii) Với mỗi a ∈ X, do tính phản xạ nên ta luôn có a ∼a Vì thế a ∈ cl(a) Do đó cl(a) 6= ∅ và X = S a∈X cl(a).
Giả sử cl(a) ∩ cl(b) 6= ∅, chọn c ∈ cl(a) ∩ cl(b) với a ∼ c và c ∼ b Nếu x ∈ cl(a), thì x ∼ a, từ đó theo tính chất bắc cầu, ta có x ∼ b, suy ra x ∈ cl(b) Điều này dẫn đến cl(a) ⊆ cl(b) Ngược lại, ta cũng có cl(a) ⊇ cl(b), do đó cl(a) = cl(b) Định lý sau đây là kết quả chính của tiết này, thể hiện mối quan hệ giữa các phép phân hoạch và các quan hệ tương đương.
Nếu ∼ là một quan hệ tương đương trên tập X, thì tập các lớp tương đương X/∼ = {cl(a) | a ∈ X} sẽ tạo thành một phân hoạch của X Ngược lại, nếu {Xi} i∈I là một phép phân hoạch của tập X, thì tồn tại duy nhất một quan hệ tương đương trên X sao cho mỗi Xi là một lớp tương đương.
Chứng minh Giả sử ∼ là một quan hệ t−ơng đ−ơng trên X Theo Mệnh đề 1.1.7, tập X/ ∼ các lớp tương đương của X theo quan hệ tương đương
Trong bài viết này, chúng ta xem xét một phép phân hoạch trên tập X và định nghĩa quan hệ tương đương Ω trên X Theo đó, hai phần tử a và b thuộc Ω nếu tồn tại một chỉ số i thuộc I sao cho cả a và b đều nằm trong lớp Xi Điều này cho thấy Ω là một quan hệ tương đương, với mỗi lớp Xi là một lớp tương đương Nếu S cũng là một quan hệ tương đương trên X với tính chất tương tự, ta chứng minh rằng Ω là tập con của S Cụ thể, nếu (a, b) thuộc Ω, thì từ định nghĩa, a và b đều thuộc cùng một lớp Xi, dẫn đến a và b đều tương đương với một phần tử c trong lớp này theo quan hệ S Ngược lại, nếu (a, b) thuộc S, thì a và b cũng nằm trong cùng một lớp Xi, do đó (a, b) thuộc Ω Từ đó, ta kết luận rằng Ω và S là tương đương nhau.
1.1.9 Hệ quả Giả sử X là tập hữu hạn Khi đó số phân hoạch tập X chính là số quan hệ t−ơng đ−ơng trên X.
Chứng minh Theo Định lí 1.1.8, ánh xạ cho ứng mỗi quan hệ t−ơng đ−ơng
Ω trên X với phép phân hoạch gồm các lớp t−ơng đ−ơng của X theo Ω, là một song ánh.
Số Bell và số Stirling loại hai
1.2.1 Định nghĩa Số phép phân hoạch tập hợp n phần tử đ−ợc gọi là số Bell thứ n và đ−ợc kí hiệu là Bn.
Theo Định lý 1.1.8, số Bell thứ n đại diện cho số lượng quan hệ tương đương trên tập n phần tử, với quy ước rằng số Bell thứ 0 là 1 (B0 = 1) Các số Bell đầu tiên được xác định là B1 = 1, B2 = 2, B3 = 5 và B4 = 15 Dãy số Bell bắt đầu với những giá trị này.
Để tính số Bell, đại diện cho số phân hoạch của tập hợp X gồm n phần tử, chúng ta cần xác định số phân hoạch tập X thành k khối, với k từ 1 đến n Các số này được gọi là số Stirling loại hai, và các giá trị cụ thể là B8 = 4140, B9 = 21147, B10 = 115975.
1.2.2 Định nghĩa Cho X là tập có n phần tử Số phân hoạch tập X thành k khối đ−ợc gọi là số Stirling loại hai và đ−ợc kí hiệu là S(n, k).
Bằng phương pháp liệt kê, ta có thể xác định số phân hoạch của tập hợp gồm 4 phần tử thành 3 khối là S(4,3) Tương tự, số phân hoạch của tập hợp gồm 5 phần tử thành 4 khối là S(5,4) = 10 Đặc biệt, số phân hoạch của tập hợp rỗng thành 0 khối là 1, trong khi số phân hoạch của tập hợp khác rỗng thành 1 khối luôn bằng 1.
1 Sau này ta xây dựng đ−ợc số phân hoạch thành k khối của tập hợp gồm n phần tử bất kì, chẳng hạn S(10,4) = 34105, S(10,5) = 42525.
Các số Stirling loại hai là một phần quan trọng trong các bài toán tổ hợp và Toán thống kê, có thể được tính toán bằng phần mềm Maple Được đặt theo tên nhà toán học James Stirling (1692-1770), khái niệm này đã được giới thiệu và nghiên cứu từ thế kỷ 18 Nếu {X1, , Xk} là một phân hoạch của tập X thành k khối, với điều kiện 1 ≤ k ≤ n (n > 0 là số phần tử của X), thì có thể áp dụng công thức tính số Bell thông qua số Stirling loại hai.
1.2.5 Ví dụ Để tính B 5 , theo Bổ đề 1.2.4 ta cần tính S(5, k) với k 1,2,3,4,5 Ta cã S(5,1) = 1, S(5,2) = 15, S(5,3) = 25, S(5,4) = 10, S(5,5) = 1 Do đó
Số Stirling loại hai đóng vai trò quan trọng trong việc tính toán số Bell, theo Bổ đề 1.2.4 Vì vậy, trong phần tiếp theo, chúng ta sẽ nghiên cứu một số tính chất liên quan đến số Stirling loại hai.
Kết quả dưới đây cung cấp một số công thức tính số Stirling loại hai Với k thuộc tập hợp {0, 1, , n}, ta định nghĩa C n k = n! / (k!(n−k)!), trong đó C n k được gọi là hệ số nhị thức thứ k ứng với n, hay số tổ hợp chập k của n phần tử.
1.2.6 Định lý Cho n, k là các số tự nhiên với k 6 n Khi đó
Chứng minh Giả sử có bộ số (i1, i2, , ik) sao cho P k j=1 ij = n víi ik ≥ 1.
Chúng ta sẽ xác định số cách phân hoạch tập X thành k tập con không rỗng với số phần tử của các tập là ij (j ∈ {1,2,…,k}) Đầu tiên, số cách chọn i1 từ n phần tử của tập X là C(n, i1) Tiếp theo, với mỗi cách chọn i1 phần tử, có C(n−i1, i2) cách chọn i2 phần tử Tương tự, với mỗi cách chọn i1 và i2, số cách chọn i3 phần tử là C(n−i1−i2, i3) Tổng quát, với mỗi cách chọn i1, i2, , ik−1, số cách chọn ik phần tử là C(n−i1−i2− −ik−1, ik) Lưu ý rằng các tập con trong phân hoạch không phân biệt thứ tự, vì vậy bộ số (i1, i2, , ik) cũng không phân biệt thứ tự Do đó, số cách phân hoạch tập hợp được tính toán dựa trên các yếu tố này.
X thành k tập con không rỗng sao cho số phần tử của các tập là ij với j ∈ {1,2, , k} bằng 1 k!C n i 1 C n−i i 2 1 C n−i i k 1 −i 2 − −i k hay 1 k! n! i1!i2! .ik! hay n! k!
1 i1!i2! .ik! Số cách phân hoạch tập hợp X thành k tập con không rỗng là S(n, k) = P i 1 + +i k =n n! k!( 1 i1! ik!) hay S(n, k) = n! k!
1.2.7 Ví dụ Giả sử ta cần tìm S(5,3) Sử dụng Định lí 1.2.6(i) ta có
Giả sử ta cần tìm S(6,4) Sử dụng Định lí 1.2.6(i) ta có
Chúng ta cũng có thể sử dụng Định lí 1.2.6 (ii) để tính S(6,4) Bằng cách sử dụng Định lí 1.2.6 (iii) ta đ−ợc
Công thức tính số Stirling loại 2 trực tiếp từ Định lý 1.2.6(i) gặp nhiều khó khăn khi n tăng lên Mệnh đề dưới đây sẽ giúp giải quyết một phần những khó khăn này.
1.2.8 Mệnh đề Cho n, k là các số tự nhiên với 26 k 6n Khi đó
Chứng minh Xét tập hợp bất kì có n+ 1 phần tử, chẳng hạn
Theo định nghĩa, S(n + 1, k) là số phân hoạch của tập hợp A thành k khối Tập B có thể được chia thành hai tập con: B1 gồm các phân hoạch của A thành k khối có một khối là {xn+1}, và B2 gồm các phân hoạch không có khối nào là {xn+1} Mỗi phân hoạch thuộc B1 chia tập {x1, x2, x3, , xn} thành k−1 khối, với S(n, k−1) cách phân chia Do đó, số lượng phân hoạch trong B1 là S(n, k−1) Nếu {xn+1} không phải là một khối, thì xn+1 sẽ nằm trong một khối với ít nhất một phần tử khác, dẫn đến kS(n, k) cách phân hoạch trong B2 Theo quy tắc cộng, tổng số phân hoạch của tập A thành k khối là S(n + 1, k) = S(n, k−1) + kS(n, k).
Khi đã biết S(5,3) = 25 và S(5,4) = 10, ta có thể tính S(6,4) bằng công thức S(6,4) = 4S(5,4) + S(5,3), dẫn đến kết quả 65 Công thức truy hồi này có ưu điểm lớn so với việc tính số Stirling loại 2 trực tiếp như trong Định lý 1.2.6(i) với số n lớn.
Cuối tiết này, chúng tôi giới thiệu công thức tổng quát để tính số Stirling loại hai cho một tập hợp n phần tử được phân hoạch thành k khối, với k có thể là 2, 3, 4, 5, n−1, hoặc n−2.
1.2.10 Mệnh đề Ta có các đẳng thức sau
Chứng minh Ta sẽ chứng minh các đẳng thức trên bằng phương pháp qui nạp đồng thời kết hợp với công thức truy hồi
(i) Khi n = 2, ta có S(n,2)=S(2,2) = 1 và 2 n−1 −1 = 2−1 = 1, do đó đẳng thức đúng với n = 2 Giả sử đẳng thức đúng với n = k ≥ 2, tức là S(k,2) = 2 k−1 −1 Ta cần chứng minh đẳng thức đúng với n = k + 1.
Mỗi cách phân hoạch tập hợp X gồm n phần tử thành 2 tập con A và B có thể được hiểu là A và B là hai tập con bù của nhau, tức là A = X \ B Có tổng cộng 2^n cặp (A, B) có thứ tự, bao gồm cả hai cặp đặc biệt (A, ∅) và (∅, B) Nếu không tính hai cặp này, sẽ có 2^n - 2 cặp bù nhau có thứ tự Do đó, trong phân hoạch, số cặp không có thứ tự là 2^n - 2.
2 = 2 n−1 −1. (ii) Khi n= 3, ta có S(n,3) = S(3,3) = 1 và
Do đó đẳng thức đúng với n = 3 Giả sử đẳng thức đúng với n = k ≥ 3, tức là S(k,3) = 3 k −3.2 k + 3
6 Ta cần chứng minh đẳng thức đúng với n= k + 1 ThËt vËy, ta cã
(iii) Khi n = 4, ta có S(n,4) = S(4,4) = 1 và
Do đó đẳng thức đúng với n = 4 Giả sử đẳng thức đúng với n = k ≥ 4, tức là S(k,4) = 4 k −4.3 k + 6.2 k −4
24 Ta cần chứng minh đẳng thức đúng víi n = k+ 1 ThËt vËy, ta cã S(k + 1,4) = 4S(k,4) +S(k,3) Theo kÕt quả (ii) ở trên ta có S(k,3) = 3 k −3.2 k + 3
(iv) Khi n= 5, ta có: S(n,5) = S(5,5) = 1 và
Vì thế đẳng thức đúng với n = 5 Giả sử đẳng thức đúng với n = k ≥ 5, tức là
Ta cần chứng minh đẳng thức đúng với n = k + 1 Thật vậy, ta có S(k +
1,5) = 5S(k,5) +S(k,4) Theo kết quả (iii) ở trên ta có
(v) Khi n = 2, ta có S(2,1) = C 2 2 = 1, do đó đẳng thức đúng với n = 2. Giả sử đẳng thức đúng với n = k, tức là S(k, k −1) = C k 2 , k ≥ 2, k ∈ N.
Ta cần chứng minh đẳng thức đúng với n = k+ 1 Thật vậy, ta có
Khi n = 4, ta có S(4,2) = 7, và theo công thức C(4,3) + 3C(4,4) = 7, điều này chứng minh rằng đẳng thức đúng với n = 4 Giả sử đẳng thức đúng với n = k, tức là S(k, k − 2) = C(k, 3) + 3C(k, 4) với k ≥ 4 và k ∈ N Bây giờ, chúng ta cần chứng minh rằng đẳng thức cũng đúng với n = k + 1.
1.2.11 Ví dụ Theo công thức trong mệnh đề trên ta có
Các công thức trong mệnh đề trên mang lại hiệu ứng khá mạnh, giúp chúng ta có thể tra cứu số phân hoạch của tập hợp gồm n phần tử thành k khối một cách dễ dàng, đặc biệt là với những giá trị của k đặc biệt.
Một số công thức tính hàm phân hoạch tập hợp
Hàm phân hoạch tập hợp, được định nghĩa bởi công thức f(n) = Bn với n ∈ N, là một hàm biến nguyên có giá trị nguyên Mục tiêu của bài viết này là chứng minh chi tiết một số công thức tính hàm phân hoạch tập hợp, cụ thể là số Bell Bn, và giới thiệu tam giác Pascal trong việc tính toán hàm phân hoạch này.
1.3.1 Mệnh đề Ta có công thức truy hồi sau đây.
Chứng minh Ta xây dựng phiếm hàm tuyến tính L : R[x] → R xác định bởi (x)k = A k x = x(x −1) .(x − k + 1) → L((x)k) = 1 với mọi k = 0,1,2 Ta chứng minh đ−ợc x n = P n k=0
Suy ra L((x)n+1) = L((x)n) =L(x(x−1)n) Do đó L(p(x)) = L((x)n) L(xP(x − 1)) với mọi P(x) Bây giờ ta cho P(x) = (x + 1) n , ta đ−ợc L((x+ 1) n ) = L(x n+1 ), hay
Tam giác Bell được sử dụng để tính số phân hoạch của tập hợp n phần tử, với n nhận các giá trị từ 1 đến 10 Kết quả này là sự tổng hợp của các định lý và mệnh đề đã được trình bày trước đó Để hiểu rõ hơn, chúng ta sẽ mô tả cách xây dựng tam giác Bell thông qua một số chú ý quan trọng.
Số Bell có thể được tính toán dễ dàng thông qua việc xây dựng tam giác Bell, còn gọi là dãy Aitken hoặc tam giác Pierce Để tạo ra tam giác Bell, bắt đầu với số 1 ở dòng đầu tiên Dòng tiếp theo được hình thành bằng cách lấy phần tử bên phải của dòng trên làm phần tử đầu tiên bên trái Các phần tử tiếp theo trong dòng mới được tính bằng cách cộng phần tử bên trái với phần tử cùng cột ở dòng trước Quá trình này tiếp tục cho đến khi số lượng phần tử trong dòng mới nhiều hơn một phần tử so với dòng trên.
Số nằm phía phải mỗi dòng là số Bell cho mỗi dòng.
Tam giác Bell có quy luật thiết lập tương tự như tam giác Pascal trong các số tổ hợp Hàng đầu tiên bắt đầu bằng số 1, đây là số Bell đầu tiên Đối với mọi i ≥ 1, hàng thứ i + 1 được điền theo quy tắc: chữ số cuối cùng của hàng thứ i được đặt lên đầu hàng thứ i + 1 Đối với mọi j > 1, số thứ j của hàng i + 1 là tổng của số thứ j - 1 của hàng i + 1 và số thứ j - 1 của hàng i Số cuối cùng của hàng i + 1 chính là số Bell của hàng đó.
Tr−ớc hết ta có bảng tính các số S(n, k), tức là các số Stirling loại 2.
Bảng số Bell Bn thể hiện số phân hoạch của tập hợp n phần tử, với dòng đầu tiên tương ứng với n = 1 và dòng thứ hai với n = 2 Mỗi dòng tiếp theo chứa số Bell ứng với giá trị n của dòng đó Ví dụ, số Bell ở dòng thứ 9 là B9 = 21147 Các số Bell cho từng n được liệt kê như sau: n = 1 (1), n = 2 (1, 2), n = 3 (2, 3, 5), n = 4 (5, 7, 10, 15), n = 5 (15, 20, 27, 37, 52), n = 6 (52, 67, 87, 114, 151, 203), n = 7 (203, 255, 322, 409, 523, 674, 877), n = 8 (877, 1080, 1335, 1657, 2066, 2589, 3263, 4140), và n = 9 (4140, 5017, 6097, 7432, 9089, 11155, 13744, 17007, 21147).
Chúng ta có thể mở rộng tam giác Bell với các số tự nhiên n lớn hơn, điều này mang lại lợi ích lớn trong việc tính toán số phân hoạch của các tập hợp có nhiều phân tử.
(ii) Một số nguyên tố Bell là một số Bell đồng thời là một số nguyên tố. Các số nguyên tố Bell đầu tiên là
Các số nguyên tố Bell ở trên t−ơng ứng là các số Bell thứ 2,3,7,13,42,55.
Số nguyên tố Bell tiếp theo là B2841, có giá trị xấp xỉ 93074106538 Đến năm 2005, B2841 là số nguyên tố Bell lớn nhất được biết đến Năm 2002, Phil Carmody đã tuyên bố rằng B2841 là số nguyên tố, và gần hai năm sau, Ignacio Larrosa Canestro đã chứng minh điều này.
Một số ứng dụng trong toán sơ cấp
Trong chương này, chúng ta sẽ khám phá các ứng dụng của lý thuyết phân hoạch trong nhiều lĩnh vực toán học, bao gồm đại số tổ hợp và xác suất thống kê Đặc biệt, chúng ta sẽ nhấn mạnh vai trò của phép phân hoạch tập hợp trong hình học sơ cấp.
Phân hoạch chẵn, lẻ và ứng dụng trong toán sơ cấp
Tập hợp X là một tập có n phần tử, và một phân hoạch của tập hợp này được gọi là phân hoạch có điều kiện khi có một điều kiện cụ thể áp dụng cho các tập con trong phân hoạch Bài viết sẽ tập trung vào hai loại phân hoạch đặc biệt: phân hoạch chẵn và phân hoạch lẻ.
Phân hoạch tập hợp X được phân loại thành hai loại chính: phân hoạch chẵn và phân hoạch lẻ Phân hoạch chẵn là khi mỗi tập con trong phân hoạch có số phần tử là số chẵn, trong khi phân hoạch lẻ là khi mỗi tập con có số phần tử là số lẻ.
2.1.2 Kí hiệu Với tập X có n phần tử ta kí hiệu:
(i) E(n, k) là số phân hoạch tập X thành k tập con sao cho mỗi tập con có chẵn phần tử.
(ii) O(n, k) là số phân hoạch tập X thành k tập con sao cho mỗi tập con có một số lẻ phần tử.
Số phân hoạch tập X thành các tập con với số lượng phần tử chẵn được ký hiệu là En, trong khi số phân hoạch thành các tập con với số lượng phần tử lẻ được ký hiệu là On.
2.1.3 Chó ý Ta cã En Pn k=0
2.1.4 Mệnh đề Với m, n là các số nguyên dương, ta có các đẳng thức sau: (i) E(2m,2) = 2 2m−2 −1;
Gọi A là tập các phân hoạch của một tập X gồm 2m phần tử thành các tập con có số chẵn phần tử Để tạo ra một phân hoạch trong A, trước tiên chọn 2j phần tử từ 2m phần tử cho tập con thứ nhất, có C(2m, 2j) cách chọn Sau đó, chọn 2m−2j phần tử còn lại cho tập con thứ hai, có đúng 1 cách chọn Vì j có thể nhận các giá trị từ 1 đến m−1 và số cách chọn ứng với mỗi j được tính 2 lần, ta có công thức tổng quát cho số phân hoạch này.
Khai triển nhị thức (1 +x) 2m sau đó cho x = 1, x = −1 ta nhận đ−ợc
0 2m = (1−1) 2m = C 2m 0 −C 2m 1 +C 2m 2 −C 2m 3 +C 2m 4 + −C 2m 2m−1 +C 2m 2m Cộng từng vế các đẳng thức trên ta nhận đ−ợc
Khi phân hoạch một tập hợp gồm 2m thành m tập con không rỗng, mỗi tập con chứa số lượng phần tử chẵn, thì số phần tử trong mỗi tập con là 2 Đầu tiên, ta có C(2m, 2) cách chọn 2 phần tử cho tập con thứ nhất Sau đó, ta tiếp tục chọn 2 phần tử cho tập con thứ hai từ 2m−2 phần tử còn lại.
Có hai cách để chọn các phần tử trong tập con, và khi chỉ còn lại hai phần tử, ta có hai cách để chọn chúng Theo quy tắc nhân và nguyên tắc phân hoạch, không cần quan tâm đến thứ tự của các tập hợp con trong phân hoạch.
Công thức phân hoạch tập hợp gồm 2n phần tử thành 2 tập con không rỗng có thể được thực hiện qua hai bước: đầu tiên, chọn 2j−1 phần tử từ 2n phần tử cho tập hợp thứ nhất, có tổng số cách chọn là C(2n, 2j−1) Tiếp theo, chọn 2n + 1 − 2j phần tử còn lại cho tập hợp thứ hai, với chỉ một cách thực hiện Vì j có thể nhận các giá trị từ 1 đến n và số cách chọn ứng với mỗi j được tính hai lần, ta có được công thức phân hoạch tổng quát.
2(C 2n 1 +C 2m 3 + .+C 2n 2n−1 Khai triển nhị thức (1 +x) 2n sau đó cho x = 1, x = −1 ta nhận đ−ợc
Cộng từng vế các đẳng thức trên ta nhận đ−ợc O(2n,2) = 2 2n−2
Khi phân hoạch tập hợp gồm n phần tử thành n−2 tập con không rỗng với mỗi tập con chứa số phần tử lẻ, sẽ có ít nhất một tập con có 3 phần tử và n−3 tập còn lại mỗi tập có một phần tử Số cách chọn 3 phần tử để tạo thành tập con này là C(n, 3) Đồng thời, chỉ có một cách phân hoạch n−3 phần tử còn lại thành n−3 tập không rỗng, mỗi tập chứa một phần tử Theo quy tắc nhân, tổng số cách phân hoạch được tính bằng tích của các số cách chọn và phân hoạch.
Từ Mệnh đề 2.1.4, ta có bảng sau để tính các số E(n, k) và O(n, k) với nh÷ng n nhá.
Trong một cuộc thi đấu cầu lông với 20 vận động viên, ban tổ chức cần chia họ thành 10 cặp thi đấu Số cách chia này tương đương với số phân hoạch tập hợp 20 phần tử thành 10 tập con, mỗi tập con gồm đúng 2 vận động viên.
2 phần tử Số cách là E(20,10) = 654729685.
2.1.6 Ví dụ Tại vòng chung kết Worldcup thế giới diễn ra tại Brazil năm
Năm 2014, Ban tổ chức đã chọn 16 đội bóng để tham gia vào vòng đấu loại trực tiếp, nơi các đội sẽ được bốc thăm thành 8 cặp đấu Mỗi cặp đấu sẽ thi đấu để chọn ra đội thắng vào tứ kết Số cách phân chia 16 đội thành 8 cặp là E(16,8) = 2027025 Tương tự, số cách chia 8 đội thắng thành 4 cặp cho vòng tứ kết là E(8,4) = 105, và số cách chia 4 đội thắng cho vòng bán kết là E(4,2) = 3.
Bây giờ ta sử dụng các công thức trên để giải một số bài toán sơ cấp.
Bài toán phân phối n quả cầu phân biệt vào m hộp giống nhau yêu cầu tìm số cách phân phối sao cho mỗi hộp có số quả cầu chẵn và số cách phân phối sao cho mỗi hộp có số quả cầu lẻ Việc xác định số lượng cách phân phối này là một bài toán thú vị trong combinatorics.
Số cách phân phối các quả cầu phân biệt vào các hộp giống nhau sao cho mỗi hộp chứa một số chẵn (hoặc lẻ) phần tử tương đương với số cách phân hoạch tập hợp n phần tử thành m tập con, trong đó mỗi tập con có số lượng quả cầu là chẵn (hoặc lẻ).
Số cách phân phối để mỗi hộp chứa một số chẵn quả cầu là E(n, m), trong khi số cách phân phối để mỗi hộp chứa một số lẻ quả cầu là O(n, m).
Có hai bài toán liên quan đến việc phân phối 5 đồ vật khác nhau vào 3 hộp giống nhau Bài toán đầu tiên yêu cầu tìm số cách phân phối sao cho mỗi hộp chứa một số lượng đồ vật chẵn, trong khi bài toán thứ hai yêu cầu tìm số cách phân phối với điều kiện mỗi hộp chứa một số lượng đồ vật lẻ.
Số cách phân phối 5 đồ vật khác nhau vào 3 hộp giống nhau sao cho mỗi hộp có một số chẵn đồ vật là E(5,3) = 0, do các đồ vật khác nhau và các hộp giống nhau Ngược lại, số cách phân phối 5 đồ vật khác nhau vào 3 hộp giống nhau với điều kiện mỗi hộp có một số lẻ đồ vật là O(5,3) = 10.
Một số ứng dụng giải toán tổ hợp và hình học sơ cấp
Số phân hoạch tập X gồm n phần tử thành k khối, được ký hiệu là S(n, k), được gọi là số Stirling loại 2 S(n, k) biểu thị số cách phân phối n quả cầu phân biệt vào k hộp giống nhau mà không có hộp nào rỗng Ví dụ, số cách phân phối 10 quả cầu phân biệt vào 5 hộp giống nhau mà không có hộp nào rỗng là S(10, 5) = 52525.
2.2.1 Bài toán Có bao nhiêu cách phân phối 2015 quả cầu phân biệt vào
Giả sử có 100 hộp giống nhau, việc phân phối 2015 quả cầu phân biệt vào các hộp này tương đương với việc phân hoạch tập hợp 2015 phần tử thành 100 khối, ký hiệu là S(2015, 100) Mỗi cách phân phối này có thể được hoán vị 100 hộp, tạo ra 100! cách phân phối 2015 quả cầu vào 100 hộp phân biệt Do đó, số cách phân phối tổng cộng được tính toán dựa trên các yếu tố này.
2015 quả cầu phân biệt vào 100 hộp phân biệt là 100! x S(2015,100).
Bài toán này đề cập đến việc phân phối n quả cầu phân biệt vào k hộp phân biệt Cần xác định số cách phân phối sao cho mỗi hộp chứa một số chẵn quả cầu, cũng như số cách phân phối khi mỗi hộp chứa một số lẻ quả cầu.
Để phân phối n quả cầu vào k hộp giống nhau sao cho mỗi hộp chứa số quả cầu chẵn, ta có số cách là E(n, k), và cho số quả cầu lẻ là O(n, k) Mỗi cách phân phối vào k hộp giống nhau có thể tạo ra k! phân phối khác nhau bằng cách hoán vị các hộp Do đó, tổng số cách phân phối n quả cầu phân biệt vào k hộp phân biệt với điều kiện mỗi hộp chứa số quả cầu chẵn là k! x E(n, k), trong khi với số quả cầu lẻ là k! x O(n, k).
2.2.3 Bài toán Tính số nghiệm nguyên không âm của ph−ơng trình x1 +x2 +x3 + .+xk = n.
Lời giải Xét dãy có độ dài là n+k −1 bao gồm n phần tử x và k−1 số
Trong bài viết này, chúng ta xem xét phương trình tổng hợp x1 + x2 + x3 + + xk = n, với điều kiện xi > 0 cho mọi i thuộc {1, 2, 3, , k} Điều đáng chú ý là có một sự song ánh giữa tập hợp các nghiệm nguyên dương của phương trình này và các dãy x1, x2, , xk thỏa mãn điều kiện trên Hơn nữa, số lượng các dãy có dạng như vậy tương ứng với số cách chọn k-1 vị trí cho số.
Trong bài toán này, 0 là tập con gồmk−1 phần tử của tập hợp gồm n−1 phần tử Số các dãy thỏa mãn điều kiện này được tính bằng C n−1 k−1 Do đó, số nghiệm nguyên dương của phương trình cũng là C n−1 k−1 Nếu xét phương trình x1 + x2 + x3 + + xk = n với điều kiện xi ≥ 0 cho mọi i thuộc {1, 2, 3, , k}, ta có thể rút ra những nhận xét quan trọng về số lượng nghiệm.
(x1 + 1) + (x2 + 1) + .+ (xk + 1) = n+k vớixi+1 > 0vài ∈ {1,2,3, k} Đảo lại, nếuy1+y2+y3+ .+yk = n+k và yi > 0 với mọi i ∈ {1,2,3, k} thì
(y1 −1) + (y2 −1) + .+ (yk −1) = n với yi ≥ 0 và i ∈ {1,2,3, k} Do đó số nghiệm nguyên không âm của ph−ơng trình là C n+k−1 k−1 = C n+k−1 n
2.2.4 Bài toán Chọn ngẫu nhiên một số tự nhiên có 3 chữ số Tính xác suất để chọn đ−ợc một số có tổng các chữ số chia hết cho 10.
Lời giải Gọi số cần lập có dạng abc thỏa mãn a 6= 0 và a, b, c ∈ {0,1,2,3,4,5,6,7,8,9}.
Số có 3 chữ số tùy ý là 9 x 10 2 = 900 số Nhận xét rằng số nghiệm không âm của ph−ơng trình a+b+c = n là C n+2 2 Theo giả thiết, ta có 2 tr−ờng hợp sau đây.
Trường hợp 1: Đối với phương trình a + b + c = 10, số nghiệm nguyên không âm của a, b, c là C(12, 2) Số nghiệm thỏa mãn điều kiện a = 0, với 0 ≤ b, c ≤ 9 và b, c ∈ N là C(11, 1) Ngoài ra, trường hợp a = 10, b = c = 0 có 1 nghiệm Tổng hợp lại, trường hợp này có
C 12 2 −C 11 1 −1 = C 11 2 −1 số thỏa mãn yêu cầu bài toán.
Tr−ờng hợp 2: a+ b+c = 20 Đặt a = 9−x, b = 9−y, c = 9−z Khi đó, ta có x, y, z ∈ {0,1,2,3,4,5,6,7,8,9} và x+y +z = 7, x 6= 9 Số nghiệm x, y, z thỏa mãn là C 9 2 và các số thỏa mãn tr−ờng hợp này là C 9 2
Tóm lại số các số thỏa mãn yêu cầu bài toán là C 11 2 +C 9 2 −1 = 90 Vì vậy, xác suất cần tìm là P = 90
2.2.5 Bài toán Chọn ngẫu nhiên một số tự nhiên có 3 chữ số Tính xác suất để chọn đ−ợc một số có tổng các chữ số chia hết cho 9.
Lời giải Gọi số cần lập có dạng abc thỏa mãn a 6= 0 và a, b, c ∈ {0,1,2,3,4,5,6,7,8,9}.
Số có 3 chữ số tùy ý là 9 x 10 2 = 900 số Nhận xét rằng số nghiệm không âm của ph−ơng trình a+ b+c = n là C n+2 2 Theo giả thiết ta có 3 tr−ờng hợp sau đây.
Trường hợp 1: a+b+c= 9, khi đó số nghiệm nguyên không âm với a, b, c tùy ý là C 11 2 Số nghiệm a, b, c thỏa mãn a = 0, 06 b, c 6 9 và b, c ∈ N là
C 10 1 Kết hợp lại, tr−ờng hợp này có C 11 2 −C 10 1 = C 10 2 số thỏa mãn yêu cầu bài toán.
Tr−ờng hợp 2: a+ b+c = 18 Đặt a = 9−x, b = 9−y, c = 9−z Khi đó, ta có x, y, z ∈ {0,1,2,3,4,5,6,7,8,9} và x+y +z = 9, x khác 9 Vì thế số nghiệm x, y, z thỏa mãn là C 11 2 −1, do đó số các số thỏa mãn trường hợp này là C 11 2 ư1.
Trường hợp 3: a+b+c = 27, khi đó a = 9, b = 9, c = 9 nên có 1 số thỏa mãn tr−ờng hợp này.
Tóm lại số các số thỏa mãn yêu cầu bài toán là C 10 2 +C 11 2 −1 + 1 = 100. Xác suất cần tìm là P = 90
Trong một hộp chứa 50 viên bi được đánh số từ 1 đến 50, chúng ta sẽ chọn ngẫu nhiên 3 viên bi Mục tiêu là tính xác suất để tổng của ba số trên 3 viên bi được chọn là một số chia hết cho 3.
Để giải bài toán, ta chọn ngẫu nhiên 3 viên bi từ 50 viên, với số cách chọn là C(50, 3) = 19600 Gọi A là biến cố mà tổng ba số trên ba viên bi được chọn chia hết cho 3 Tập hợp 50 viên bi có thể phân chia thành 3 tập hợp: X1 (16 viên bi chia hết cho 3), X2 (17 viên bi chia cho 3 dư 1), và X3 (17 viên bi chia cho 3 dư 2) Để tìm số cách chọn 3 viên bi sao cho tổng của chúng chia hết cho 3, ta xem xét hai trường hợp Trường hợp 1: nếu 3 viên bi được chọn cùng loại, tức là thuộc X1, X2 hoặc X3, thì số cách chọn là C(16, 3) + C(17, 3) + C(17, 3) = 1920.
Trong trường hợp 2, có 3 viên bi được chọn, mỗi viên thuộc một loại khác nhau Cụ thể, viên đầu tiên thuộc tập hợp X1, viên thứ hai thuộc tập hợp X2, và viên thứ ba thuộc tập hợp X3.
X3 Khi đó số cách chọn trong trường hợp này là C 16 1 +C 17 1 +C 17 1 = 4624. Theo qui tắc cộng có n(A) = 1920 + 4624 = 6544 Xác suất cần tìm là
Trong hình học, ngoài các bài toán truyền thống phát triển thành định lý, còn có những bài toán ghép hình và chia hình với nội dung khác Phương pháp khảo sát toán học này dựa vào các đặc tính riêng biệt, được gọi là sự suy luận logic hình thức, tương tự như nguyên lý Dirichlet Các bài toán ghép hình và chia hình có thể coi là những bài toán sơ đẳng của hình học tổ hợp Chúng ta sẽ xem xét một số tính chất đơn giản của hình học tổ hợp, đặc biệt là bài toán phân hoạch đa giác lồi, phẳng thành các tam giác bằng một hệ thống điểm cho trước trong đa giác đó.
2.2.7 Ví dụ Cho tứ giác ABCD và 1 điểm M tùy ý nằm trong tứ giác đó. Xét 4 tr−ờng hợp sau đây.
(i) Điểm M không nằm trên 2 đ−ờng chéo AC và BD;
Điểm M có thể nằm trên đường chéo AC và bên ngoài đường chéo BD, hoặc nằm trên đường chéo BD và bên ngoài đường chéo AC Ngoài ra, điểm M cũng có thể nằm trên cả hai đường chéo AC và BD.
Khi đó, cả 4 trường hợp này đều có 4 tam giác nằm trong phân hoạch nói trên.
Phân hoach số và ứng dụng trong toán sơ cấp
Chứng minh rằng không thể chia tập hợp {1, 2, 3, , 1997} thành các tập con rời nhau sao cho số lớn nhất trong mỗi tập con bằng tổng các số còn lại Điều này có nghĩa là không tồn tại cách phân chia nào mà trong đó số lớn nhất của mỗi tập con lại bằng tổng các phần tử khác trong cùng tập con đó.
Chứng minh rằng phân hoạch nh− không tồn tại bằng cách giả sử ngược lại Nếu tồn tại phân hoạch, tổng tất cả các số trong mỗi tập con sẽ bằng hai lần số lớn nhất, dẫn đến tổng của tập hợp {1,2,3, ,1997} là một số chẵn Tuy nhiên, dãy số 1, 2, 3, , 1997 tạo thành một cấp số cộng với 1997 số hạng, số hạng đầu tiên là u1 = 1 và công sai d = 1.
2 = 1997999, đây là một số lẻ, mâu thuẫn Từ đây ta suy ra phân hoạch nh− thế không tồn tại.
Chứng minh rằng khi phân hoạch tập hợp X = {1, 2, 3, , 100} thành 7 tập con, sẽ luôn có ít nhất một tập con chứa bốn phần tử phân biệt a, b, c, d thỏa mãn điều kiện a + b = c + d, hoặc chứa ba số phân biệt e, f, g sao cho e + f = 2g.
Chứng minh rằng tồn tại ít nhất một tập con T của X với ít nhất 15 phần tử, vì 14.7 = 98 < 100 Xét tất cả các hiệu a−b với a, b thuộc T và a > b, ta có C(15, 2) = 105 hiệu khác nhau, mà các hiệu này nhận giá trị thuộc tập hợp {1, 2, 3, , 99} Do đó, có ít nhất 2 cặp phân biệt (x, y) và (u, v) thỏa mãn x − y = u − v > 0 Nếu x, y, u, v là 4 số phân biệt, ta có x + v = u + y, từ đó suy ra điều cần chứng minh Nếu x = v, thì y + u = 2x; hoặc nếu y = u, ta có x + v = 2y.
2.3.3 Bài toán Giả sử tổng của 2 số nguyên a, b không chia hết cho 3.
Chứng minh rằng không thể chia tập số nguyên Z thành 3 lớp đôi một rời nhau sao cho mỗi t∈ Z thì 3 số sau t, t+ a, t+ b thuộc 3 lớp phân biệt.
Giả sử có một phân hoạch Z = T1 ∪ T2 ∪ T3 đáp ứng yêu cầu của bài toán Ký hiệu xΩy nếu x và y thuộc cùng một lớp phân hoạch Bộ ba số nguyên (a, b, c) được gọi là bộ tốt khi a, b, c thuộc ba lớp phân hoạch khác nhau.
Từ giả thiết (x, x+a, x+b) là bộ tốt vì x, x+a, x+b thuộc 3 lớp phân hoạch T−ơng tự cho t = x+a, t = x+ b ta có các bộ tốt
(x+ a, x+ 2a, x +a+b), x+b, x+ 2b, x+a+b) Khi đó xΩ(x+a+b), chox = 0thì0Ω(a+b)và chox = a+bsuy ra(a+b)Ω2(a+b) Tiếp tục, ta có 0Ωp(a+b) với mọi p ∈ Z (∗).
Mặt khác, (x+ a, x + 2a, x + a + b) là bộ tốt và (x + a + b)Ωx nên (x, x + a, x + 2a) là bột tốt, cho x = 0 suy ra (0, a,2a) là bộ tốt và cho x = a suy ra (a,2a,3a) là bộ tốt, từ đó 0Ω3a.
Mặt khác, bộ (3a, 4a, 5a) và (4a, 5a, 6a) là bộ tốt, do đó 3aΩ6a và 0Ωqa chỉ xảy ra khi q chia hết cho 3 Kết hợp điều này với giả thiết trước đó, ta có tổng số a + b phải chia hết cho 3, dẫn đến mâu thuẫn với giả thiết đã đưa ra.
2.3.4 Bài toán Tìm số m nhỏ nhất sao cho phân hoạch bất kì tập hợp
{1,2,3, , m} thành 2 lớp T1, T2 thì luôn tồn tại 1 lớp có chứa 3 số phân biệt x < y < z sao cho x+z = 2y
Để chứng minh, ta xem xét các trường hợp với m từ 4 đến 8 Với m = 4, ta có {1,2,3,4} = {2} ∪ {1,3,4}, nhưng không thỏa mãn yêu cầu Tương tự, với m = 5, {1,2,3,4,5} = {2,3} ∪ {1,4,5} cũng không thỏa mãn Khi m = 6, {1,2,3,4,5,6} = {2,5,6} ∪ {1,3,4} vẫn không đáp ứng yêu cầu Tiếp theo, với m = 7, {1,2,3,4,5,6,7} = {1,2,4,5} ∪ {3,6,7} không thỏa mãn Cuối cùng, với m = 8, {1,2,3,4,5,6,7,8} = {1,4,5,8} ∪ {2,3,6,7} cũng không thỏa mãn yêu cầu của bài toán.
Giả sử rằng với m = 9, tồn tại một phân hoạch {1,2,3,4,5,6,7,8,9} thành hai lớp T1 và T2 Nếu cả hai lớp T1 và T2 đều không đáp ứng yêu cầu của bài toán, điều này dẫn đến m = 9 không thỏa mãn các tiêu chí đề ra.
2 lớp T 1 , T 2 nh− nhau nên ta chỉ xét 2 tr−ờng hợp sau đây:
Tr−ờng hợp 1: (1,9) ⊆ T1 suy ra 1 + 9
T 2 Từ đó 3,7 không đồng thời thuộc T 2 (nếu ng−ợc lại 3+7=2.5) suy ra phải ít nhất có 1 số thuộc T1 Giả sử 3 ∈ T1 suy ra
2 = 4∈ T 1 ,(5,6) ⊆T 2 , suy ra 7 ∈ T1 và (1,4,7) ∈ T1 (mâu thuẫn).
2 = 6∈ T1,(6,7) ⊆T1, suy ra 5 ∈ T2,(5,4) ∈ T2,3 ∈ T1 và (3,6,9) ∈ T1 (mâu thuẫn).
Tr−ờng hợp 2: 1 ∈ T 1 ,9 ∈ T 2 , giả sử 5 ∈ T 1 suy ra (1,5) ⊆ T 1 và 3 ∈ T2,9 ∈ T2 và (1,3,5),(1,5,9) lập thành một cấp số cộng nên
2 = 8 ∈ T1 Ta có (3,4) ∈ T2 suy ra 2 ∈ T1 và (2,5,8) ∈ T1 (mâu thuÉn).
Giả sử 5 ∈ T2 ta suy ra ( 9,5) ∈ T2 và (3,6) ∈ T1 mà 1,3 ∈ T1 suy ra
2 = 2 ∈ T2,(6,7) ∈ T1, suy ra 8 ∈ T2 và (2,5,8) ∈ T2 (mâu thuẫn) nên số m nhỏ nhất cần tìm là 9.
Bài toán phân hoạch tập hợp X thành các lớp T1, T2, T3, , Tn được gọi là cân bằng theo số phần tử nếu mỗi lớp có số lượng phần tử bằng nhau Ngoài ra, phân hoạch cũng được coi là cân bằng tổng nếu tổng số phần tử của mỗi lớp là như nhau Vấn đề đặt ra là liệu có tồn tại một phân hoạch cho tập hợp {1, 2, 3, , nk} thành k lớp mà vừa đảm bảo cân bằng số phần tử vừa cân bằng tổng hay không Nếu có, chúng ta sẽ gọi đây là giả thiết.
Chứng minh Ta sẽ chứng minh giả thiết H(n, k) đúng khi n là số chẵn. Thật vậy giả sử H(2, k), n = 2 đúng vì ta có phân hoạch
{1,2,3, ,2k} = {1,2k} ∪ {2,2k−1} ∪ {3,2k −2} ∪ .∪ {k, k+ 1} là phân hoạch cân bằng vì cân bằng theo số phần tử và cân bằng theo tổng.
{1,2,3 ,2mk} = {1,2mk} ∪ {2,2mk −1} ∪ .∪ {mk, mk + 1}.
Ta kí hiệu các lớp sau đây:
Tập hợp Tk được định nghĩa là {m(k−1) + 1, 2mk − m(k−1)} ∪ ∪ {mk, mk + 1}, với T1, T2, T3, , Tk chứa tất cả các phần tử từ 1 đến 2mk Mỗi tập Ti đều có 2m phần tử và tổng các số trong mỗi Ti đều bằng m(2mk + 1) Giả thiết H(2m, k) được cho là đúng.
Đối với mọi số nguyên lẻ n > 3, giả thiết H(3, k) đúng dẫn đến H(n, k) cũng đúng Giả sử chúng ta có các phân hoạch cân bằng T1, T2, , Tn theo tổng và theo số phần tử Khi n là số lẻ lớn hơn 3, n - 3 sẽ là số chẵn Điều này cho phép chúng ta xây dựng một phân hoạch cân bằng cho tập hợp {1, 2, 3, , (n - 3)k} thành k lớp X1, X2, , Xk Tiếp theo, chúng ta thêm vào các lớp Xi để tạo thành phân hoạch {1, 2, 3, , nk} từ {(n - 3)k + 1, (n - 3)k + 2, , nk} Tập hợp này bao gồm 3k số, do đó theo giả thiết qui nạp, nó có thể được phân hoạch thành k lớp, mỗi lớp có 3 phần tử với tổng các phần tử trong mỗi lớp bằng nhau, ký hiệu là {(n - 3)k + 1, (n - 3)k + 2, , nk} = Y1 ∪ Y2 ∪ ∪ Yk.
Khi đó tập hợp sau có thể phân hoạch thành k lớp sau đây
Chứng minh rằng khi phân hoạch tập hợp {1, 2, 3, , 3n} thành 3 lớp với mỗi lớp có n phần tử, chúng ta có khả năng chọn một số từ mỗi lớp sao cho một trong ba số được chọn bằng tổng của hai số còn lại.
Chứng minh : Ta xét 1 phân hoạch A, B, C Ta có số phần tử của mỗi lớp
A, B, C là những tập hợp bằng nhau và đều có kích thước n Để mô tả phân hoạch nh− một cách tổng quát, ta có thể xác định rằng 1 thuộc A và {1, 2, 3, , k - 1} là tập con của A, trong khi k thuộc B Các phần tử còn lại của A, B, C sẽ được phân bổ theo các phân hoạch khác nhau Chúng ta gọi (a, b, c) thuộc (A, B, C) là bộ tốt nếu một số trong ba số này bằng tổng của hai số còn lại.
Giả thiết phản chứng cho thấy không tồn tại bộ tốt, và ta chứng minh rằng với mọi c ∈ C, c−1 ∈ A Mục tiêu là chỉ ra rằng số phần tử của C nhỏ hơn số phần tử của A, từ đó dẫn đến mâu thuẫn vì số phần tử của C và A đều bằng n Giả sử c−1 không thuộc A, ta chọn giá trị c nhỏ nhất sao cho c−1 không thuộc A Nếu c−1 ∈ B, thì (1, c−1, c) là bộ tốt thỏa mãn giả thiết, từ đó suy ra c−1 không thuộc B Vì c−1 không thuộc A và B, nên c−1 ∈ C Nếu c−k ∈ A, thì (c−k, k, c) là bộ tốt, dẫn đến mâu thuẫn, do đó c−k không thuộc A Nếu c−k ∈ B, thì (k−1, c−k, c−1) cũng là bộ tốt, từ đó c−k không thuộc B, suy ra c−k ∈ C Hơn nữa, với c nhỏ nhất sao cho c−1 không thuộc A, ta có c−k−1 thuộc A và (c−k−1, k, c−1) tạo thành bộ tốt.
Dựa vào khẳng định đã nêu, ta xác định rằng số phần tử của tập C luôn nhỏ hơn hoặc bằng số phần tử của tập A Theo quy tắc tương ứng, nếu 2 không thuộc C nhưng 2−1 = 1 lại thuộc A, điều này dẫn đến mâu thuẫn khi số phần tử của C được cho là nhỏ hơn số phần tử của A Do đó, chúng ta có thể suy ra điều cần chứng minh.
2.3.7 Bài toán Trong tập hợp n số nguyên d−ơng phân biệt Xét tất cả các tổng của các phần tử trong mỗi tập con không rỗng của nó Chứng minh
2 n −1 số này có thể chia thành n lớp sao cho trong mỗi lớp này tỷ số giữa số lớn nhất và số nhỏ nhất luôn nhỏ hơn hoặc bằng 2.