BÀI TẬP VẬN DỤNGBÀI TẬP 1 (OLYMPIC KHTN LẦN 1). XÉT TẬP M = { 1,...

3. - Chuyên đề Toán chuyên
Toán Chuyên đề Toán chuyên

3. BÀI TẬP VẬN DỤNG

Bài tập 3.1 (Olympic KHTN lần 1). Xét tập M = { 1, 2, 3, . . . , 10 } và A

1

, A

2

, . . . ,A

n

là dãy các tập con

khác rỗng, phân biệt của M sao cho

| A

i

∩ A

j

| ≤ 3, ∀ 1 ≤ i < j ≤ n.

Tìm giá trị lớn nhất của n.

Đáp số: n = 385.

Bài tập 3.2 (Đài Loan 1998). Cho n ≥ k ≥ 3 và X = { 1, 2, . . . , n } . Gọi F

k

là một họ các k_tập của X

sao cho với mọi A, B ∈ F

k

thì

| A ∩ B | ≤ k − 2.

Chứng minh rằng tồn tại một tập con M

k

của X , | M

k

| ≥ [log

2

n] + 1 sao cho M

k

không nhận bất cứ phần

tử nào của F

k

là tập con của nó.

Chứng minh. 1. Nếu k ≥ log

2

n thì kết quả hiển nhiên đúng. Xét trường hợp k < log

2

n. Đặt m =

[log

2

n] + 1.