4 − 7KHI ĐÓ M ≤ 8. VỚI M = 8 TA CÓ MỘT CÁCH XÂY DỰNG CÁC NHÓM LÀ, VỚ...
2.4 − 7
Khi đó m ≤ 8. Với m = 8 ta có một cách xây dựng các nhóm là, với a, b, c, d, e, f , h là 7 học sinh
A
1: a b c
A
2: a d e
A
3: a f g
A
4: b d f
A
5: b e g
A
6: c d f
A
7: c e f
A
8: a b c d e f g
Ví dụ 2.1.2 (China TST 1994). Cho A
1, A
2, . . . , A
klà các tập con của X = { 1, 2, . . . , 10 } sao cho
( | A
i| = 5, ∀ i = 1, 2, . . . , k
| A
i∩ A
j| ≤ 2, ∀ 1 ≤ i < j ≤ k.
Tìm giá trị lớn nhất có thể có của k.
Chứng minh. Ta coi mỗi tập con A
tlà một xâu nhị phân dạng x
1. . . x
10, trong đó x
i= 1 nếu i ∈ A
tvà
x
i= 0 nếu i 6∈ A
t. Do
| A
i∩ A
j| ≤ 2, ∀ 1 ≤ i < j ≤ k
nên suy ra d(x, y) ≥ 6.
v
b
1
b
1
b
1
b
0
b
1
b
0
b
0
b
0
b
0
b
1
w
b
1
b
1
b
0
b
0
b
0
b
1
b
1
b
0
b
1
b