BÀI TOÁN ĐƯỢC GIẢI QUYẾT HOÀN TOÀN.VÍ DỤ 2.3.4. CHO AILÀ CÁC TẬP HỢ...
2 .
Bài toán được giải quyết hoàn toàn.
Ví dụ 2.3.4. Cho A
ilà các tập hợp hữu hạn, với i = 1, 2, . . . , n. Chứng minh rằng nếu
| A
i∩ A
j|
1≤i<∑
j≤n| A
i| . | A
j| < 1,
thì tồn tại a
i∈ A
i(i = 1, 2, . . . , n) để a
i6 = a
j, ∀ 1 ≤ i < j ≤ n.
Chứng minh. Đặt S = { 1, 2, . . . , n } và T = A
1∪ A
2∪ . . . ∪ A
n. Xét ánh xạ f : S → T sao cho: với mỗi
i ∈ S thì f (i) ∈ A
i(i = 1, 2, . . . , n). Gọi M là tập hợp tất cả các ánh xạ như vậy. Khi đó
| M | = | A
1| . | A
2| . . . | A
n| .
Ta chứng minh có ít nhất một đơn ánh trong M. Nếu f ∈ M mà không là đơn ánh, khi đó tồn tại
i, j ∈ S, i 6 = j sao cho f (i) = f ( j). Với ánh xạ f như vậy, thì f (i) = f ( j) nhận nhiều nhất là | A
i∩ A
j|
giá trị khác nhau, và f (k) (k 6 = i, j) nhận nhiều nhất là | A
k| giá trị khác nhau. Do đó với i, j ∈ S(i 6 = j),
số ánh xạ f mà f (i) = f ( j) nhiều nhất là
∏
n| A
i∩ A
j| ·
| A
k| = | A
i∩ A
j|
| A
i| . | A
j| . | M | .
k=1,k6=i,jTừ đó suy ra số ánh xạ trong M mà không phải là đơn ánh nhiều nhất là
| A
i| . | A
j| .M < | M | .
Từ đó suy ra tồn tại ít nhất một đơn ánh f
0∈ M. Đặt
f
0(i) = a
i(i = 1, 2, . . . , n).
Khi đó a
i∈ A
i(i = 1, 2, . . . , n) và do f
0đơn ánh nên i, j ∈ S(i 6 = j) thì
a
i= f
0(i) 6 = f
0( j) = a
j.
Ví dụ 2.3.5 (Iran 1999). Cho n là số nguyên dương và tập hợp X = { 1, 2, . . . , n } . Các tập A
1, A
2, . . . , A
klà các tập con của X sao cho với mọi 1 ≤ i
1, i
2, i
3, i
4≤ n ta có
| A
i1
∪ A
i2
∪ A
i3
∪ A
i4