55 ⇒ M − 12 ∑2 ≤ M − 1X∈XX∈XNẾU M = 3, KHI ĐÓ DẤU BẰNG PHẢI XẢY RA...
2 .55 ⇒ m − 1
2 ∑
2 ≤ m − 1
x∈XNếu m = 3, khi đó dấu bằng phải xảy ra trong tất cả các bất đẳng thức trên, nên n
x= m = 3, ∀ x ∈ X.
Nhưng ∑
x∈Xn
x= 55 không chia hết cho 3, nên n
xkhông thể bằng 3 với mọi giá trị của x ∈ X . Từ đây
suy ra m ≥ 4.
Tiếp theo ta chứng minh m = 4 thỏa mãn. Xét
a b b d
e f g h
1 2 3 4
5 6 7 8
Khi đó 11 tập M
iđược lấy như sau:
• 4 tập dòng
M
1= { a, b, c, d, D } , M
2= { e, f , g, D } , M
3= { 1, 2, 3, 4, D } , M
4= { 5, 6, 7, 8, D } .
• 4 tập cột
M
5= { a, e, 1, 5,C } , M
6= { b, f , 2, 6, C } , M
7= { c, g, 3, 7, C } , M
8= { d, h, 4, 8, C } .
• 3 tập đường chéo
M
9= { a, f , 3, 8, D } , M
10= { b, g, 4, 5, D } , M
11= { c, h, 1, 6, D } .
(Mỗi tập trên đều lấy trên mỗi dòng, mỗi cột đúng một phần tử)
Ví dụ 2.4.3 (USAMO 2011). Cho A
1, A
2, . . . , A
11là các hợp sao cho
( | A
i| = 45, ∀ 1 ≤ i ≤ 11
| A
i∩ A
j| = 9, ∀ 1 ≤ i < j ≤ 11.
Chứng minh rằng | A
1∪ A
2∪ . . . ∪ A
11| ≥ 165 và cho một ví dụ với trường hợp dấu bằng xảy ra.
Chứng minh. Đặt X = A
1∪ A
2∪ . . . ∪ A
11, với mỗi x ∈ X , đặt
n
x= |{ j ∈ { 1, 2, . . . , 11 }| x ∈ A
j}| .
Khi đó
x∑
∈Xn
x= | A
1| + | A
2| + ··· + | A
11| = 11 × 45 = 495.
cách chọn hai tập giao khác rỗng A
i, A
jtrong số 11 tập A
1, A
2, . . . , A
11.
• Có
112giao khác rỗng của các tập A
i, A
j.
• Mặt khác, mỗi phần tử x xuất hiện trong
n2x