SIS SJS SK = { 1, 2, . . . , 2010 } VỚI MỌI 1 ≤ I < J < K ≤ N...

2. S

^S S

^S S

= { 1, 2, . . . , 2010 } với mọi 1 ≤ i < j < k ≤ n

Bài tập 3.13 (VMO 2004). Cho tập A gồm 16 số nguyên dương đầu tiên. Hãy tìm số nguyên dương

k nhỏ nhất có tính chất: trong mỗi tập con có k phần tử của A đều tồn tại hai số phân biệt a, b sao cho

a

+ b

là số nguyên tố.

Bài tập 3.14 (Stars of Mathematics 2014). Cho các số nguyên dương M, m, n thỏa mãn 1 ≤ m ≤

n, 1 ≤ M ≤ m(m + 1)

2 và A là một tập con của { 1, 2, . . . , n } sao cho | A | = m. Chứng minh rằng tồn tại

tập con B ⊆ A sao cho

0 ≤ ∑

b − M ≤ n − m.

Bài tập 3.15 (China 2007). Cho X là tập hợp gồm 56 phần tử. Tìm số nguyên dương n nhỏ nhất sao

cho với bất kỳ 15 tập con tùy ý của X , nếu hợp của 7 tập tùy ý trong 15 tập này chứa ít nhất n phần tử,

thì tồn tại 3 tập trong 15 tập này mà giao của chúng khác rỗng.

Chứng minh. 1. Giả sử X = { 1, 2, . . . , 56 } . Nếu n ≤ 40, đặt

A

= { i, i + 7, i + 14, i + 21, i + 28, i + 35, i + 42, i + 49 } , i = 1, 2, . . . ,7.

Viết tường minh như sau

A

= { 1, 8, 15, 22, 29, 36, 43, 50 }

A

= { 2, 9, 16, 23, 30, 37, 44, 51 }

A

= { 3, 10, 17, 24, 31, 38, 45, 52 }

A

= { 4, 11, 18, 25, 32, 39, 46, 53 }

A

= { 5, 12, 19, 26, 33, 40, 47, 54 }

A

= { 6, 13, 20, 27, 34, 41, 48, 55 }

A

= { 7, 14, 21, 28, 35, 42, 49, 56 } .

Đặt

B

= { j, j + 8, j + 16, j + 24, j + 32, j + 40, j + 48 } , j = 1, 2, . . . , 8.

B

= { 1, 9, 17, 25, 33, 41, 49 }

B

= { 2, 10, 18, 26, 34, 42, 50 }

B

= { 3, 11, 19, 27, 35, 43, 51 }

B

= { 4, 12, 20, 28, 36, 44, 52 }

B

= { 5, 13, 21, 29, 37, 45, 53 }

B

= { 6, 14, 22, 30, 38, 46, 54 }

B

= { 7, 15, 23, 31, 39, 47, 55 }

B

= { 8, 16, 24, 32, 40, 48, 56 } .