2 .
Ví dụ 2.2.5. Cho 2005 tập hợp, mỗi tập hợp có có 44 phần tử. Biết rằng hai tập hợp bất kỳ đều có đúng
một phần tử chung. Chứng minh rằng tồn tại một phần tử thuộc tất cả 2005 tập hợp đã cho.
Ta cần khẳng định tồn tại một phần tử thuộc tất cả 2005 tập hợp đã cho. Do đó ta sẽ làm việc với
một phần tử x thuộc nhiều tập hợp nhất (vì chỉ có phần tử này mới có cơi hội nhiều nhất thỏa đề bài).
Để làm được điều này, ta phải biết được x thuộc bao nhiêu tập hợp. Nếu x thuộc ít hơn 2005 tập hợp,
bằng lập luận dẫn đến vô lý.
Giải. Ta có 2005 tập hợp, mỗi tập có 44 phần tử nên có tối đa là 2005 × 44 phần tử. Với x là một phần
tử bất kỳ trong chúng, đặt
n
x = { số tập hợp trong 2005 tập hợp mà chứa phần tử x } ∈ N .
Vì { n
x}
x⊂ N là hữu hạn nên tồn tại phần tử lớn nhất trong chúng, mà ta giả sử luôn là x. Tức x là
phần tử thuộc nhiều tập hợp nhất, gọi các tập hợp này là A
1, A
2, . . . , A
k. Nếu k = 2005 thì bài toán
được chứng minh. Giả sử k < 2005, tức tồn tại một tập hợp B, trong số 2005 tập hợp, không chứa x.
Theo giả thiết bài toán
x
1= B ∩ A
1 6 = x,
x
2= B ∩ A
2 6 = x,
dễ thấy x
16 = x
2vì nếu không thì x
1= x
2∈ A
1∩ A
2, trong khi đó theo điều kiện bài toán thì A
1∩ A
2= x,
duy nhất. Tương tự ta có B sẽ chứa các phần tử x
1, x
2, . . . , x
k. Tuy nhiên B chỉ chứa đúng 44 phần tử nên
k ≤ 44. Vì mỗi phần tử của B không thuộc quá 44 tập hợp (vì phần tử x thuộc nhiều tập hợp nhất là k
tập hợp mà k ≤ 44) nên B có giao khác rỗng với nhiều nhất là
44
2= 1936 < 2004
tập hợp, mâu thuẫn với giả thiết B có giao khác rỗng với 2004 tập hợp còn lại.
Vậy điều giả sử là sai, tức k = 2005. Bài toán được giải xong.
Ví dụ 2.2.6. Cho 2014 thùng trái cây, mỗi giỏ trái cây có cả ba loại trái cây Táo, Xoài, Cam. Chứng
minh rằng có thể chọn ra được 1008 thùng trái cây, sao cho tổng số Xoài, tổng số Táo, tổng số Cam
trong 1008 thùng trái cây này đều lớn hơn một nửa tổng số Xoài, tổng số Táo, tổng số Cam của 2014
thùng trái cây ban đầu.
Chứng minh. Đánh số A
1, A
2, ··· , A
2014là 2014 thùng trái cây đó. Gọi (a
i, b
i, c
i)lần lượt là số táo, xoài,
cam trong thùng A
i. Chọn ra 2 thùng A
i, A
j có số táo và số xoài lớn nhất. Nếu i = j thì ta chọn thùng
A
i và một thùng bất kỳ. Gọi A và B lần lượt là số táo và số xoài lớn nhất trong 2012 thùng còn lại. Ta
sẽ chứng minh trong 2012 thùng còn lại, có thể chia vào 2 nhóm I, II (mỗi nhóm có 1006 thùng) sao
cho
a
i− ∑
a
i ∑
≤ A
i∈Ii∈IIb
i− ∑
b
i ≤ B
Giả sử a
1≥ a
2≥ . . . ≥ a
2012, ta xét các cặp X
i= (a
2i−1, a
2i), (i = 1, 2, . . . , 1006). Với mỗi cặp
( a
2i−1 ∈ X
ia
2i∈ X
ita sẽ cho cặp đó vào 2 nhóm nhau. Khi đó với mọi cách chia thì
∑
i∈Ia
i≤ a
1+ a
3+ ··· + a
2011− a
2− a
4− ··· − a
2012= a
1+ (a
3− a
2) + ··· + (a
2011− a
2010) − a
2012≤ a
1;
a
i≥ a
2+ a
4+ ··· + a
2012− a
1− a
3− ··· − a
2011= − a
1+ (a
2− a
3) + ··· + (a
2010− a
2011) + a
2012≥ − a
1.
Nên với mọi cách chia thì
∑
≤ A.
Gọi T là một cách chia như thế. Nếu
≤ B
thì chọn cách này. Nếu
> B
không mất tính tổng quát, giả sử
b
i> ∑
b
i⇒ ∑
b
i> B.
Khi đó tồn tại j ∈ I, k ∈ II sao cho b
j> b
k. Khi đó ta chỉ việc đổi chỗ (a
j, b
j) từ nhóm I sang nhóm II
và (a
k, b
k) từ nhóm II sang nhóm I (cách đổi chỗ này không ảnh hưởng đến điều kiện (1)). Khi đó ∑
sẽ giảm đi ít nhất 1, còn ∑
b
isẽ tăng lên ít nhất 1. Do đó
sẽ giảm đi ít nhất là 2. Nếu sau khi đổi chỗ mà thỏa điều kiện (2) thì dừng, nếu chưa thỏa thì tiếp tục
làm như trên sẽ đến lúc thỏa vì hiệu trên giảm ngặt trên tập số nguyên dương. Vậy ta luôn chia được
thành 2 nhóm sao cho
≤ A
≤ B.
Trong hai nhóm I và II, thì tổng số cam trong mỗi nhóm đã được xác định, nên ta sẽ chọn được nhóm
nào số số cam nhiều hơn. Giả sử nhóm I. Khi đó thêm 2 thùng đã lấy ra cho vào nhóm I, thì số cam lấy
ra lớn hơn 1 nửa và
− A ≤ ∑
a
i≤ A ⇒ ∑
a
i≤ ∑
a
i+ A,
tức số Táo thỏa mãn điều kiện. Tương tự kiểm tra cho số Xoài.
Ví dụ 2.2.7. Cho X là một tập hợp hữu hạn, | X | = n và A
1, A
2, . . . , A
m là các tập con của X thỏa mãn
| A
i| ≥ 2, ∀ i = 1, 2, . . . , n và | A
i∩ A
j| 6 = 1, ∀ 1 ≤ i < j ≤ m.
Chứng minh rằng có thể tô các phần tử của X bằng hai màu, mỗi phần tử tô một màu, sao cho mọi tập
A
iđều chứa các phần tử được tô cả hai màu.
Chứng minh. 1. Giả sử X = { x
1, x
2, . . . , x
n} . Giả sử kết luận bài toán sai. Trong tất cả các cách
tô màu mỗi phần tử của tập X , chọn cách tô được một tập con cực đại của X, giả sử Y =
{ x
1, x
2, . . . ,x
k} (k < n) thỏa mãn bài toán theo nghĩa: nếu thêm phần tử x
k+1 vào Y thì không thể
tô màu cho x
k+1được để thỏa mãn bài toán.
Bạn đang xem 2 . - Chuyên đề Toán chuyên
