Lời giải và bình luận đề thi các tỉnh, các trường Đại học năm học 2009-2010 - Trần Nam Dũng

 có màu xanh. Khi đó, 4, 5, 6 có màu đỏ và dãy (4, 5, 6) lại thỏa mãn cả
ba điều kiện kể trên.
Như vậy, điều mà ta đã giả sử ở trên là sai. Hay nói một cách khác, bài toán đúng
với n= 3. Phép chứng minh được hoàn tất.
Bài 6.11. Cho tập hợp A gồm n ≥ 5 phần tử. Xét k tập con bất kì gồm ba phần tử
của A. Hãy tìm số k nhỏ nhất sao cho với mọi cách chọn k tập con trên luôn tồn tại
hai tập con có chung nhau đúng một phần tử.
(Đại học Khoa học tự nhiên)
Lời giải. Một cách tự nhiên, không ít bạn đã nghĩ như sau: Chọn các tập Ai−2 =
(1, 2, i) với 3 ≤ i ≤ n. Ta chọn được n− 2 tập như thế, và khi chọn thêm một tập
nữa thì luôn có hai tập giao nhau tại đúng một phần tử. Nên dự đoán số tập là n−1
và tìm cách đi chứng minh nó. Bây giờ, cần kiểm chứng lại xem điều đó có đúng
hay không . . .
Ta kí hiệu các tập con của A là A1, A2, . . . , AKn và đánh số các phần tử của tập A từ
1 đến n (trong đó, Kn là giá trị tốt nhất để tồn tại Kn tập hợp, mà hai tập hợp bất kì
giao nhau tại 0 hoặc 2 phần tử). Ta sẽ chứng minh Kn = Kn−4+4.
Theo bước suy luận ở trên, rõ ràng ta có Kn ≥ n− 1. Theo đó, do |Ai| = 3 nên tồn
tại một phần tử thuộc vào ít nhất ba tập hợp. Không mất tính tổng quát, giả sử phần
tử đó là 1, và nó thuộc vào ba tập hợp A1, A2, A3.
Theo giả thiết, |A1∩A2| = 2, nên tồn tại một phần tử khác (kí hiệu là 2) thuộc vào
cả hai tập hợp này, tức là A1 = {1, 2, 3} và A2 = {1, 2, 4}. Xét tập hợp A3, ta có hai
trường hợp nhỏ.
+ Trường hợp 1. 2 ∈ A3. Khi đó, A3 = {1, 2, 5}, và do đó, nếu một tập Ai nào đó có
phần tử chung với ít nhất một trong ba tập A1, A2, A3, nó sẽ phải có dạng (1, 2, i).
Như thế, số tập tối đa có thể chọn làmax{n−1, Kn−6+3}≤max{n−1, Kn−4+3}.
+ Trường hợp 2. 2 6∈ A3. Khi đó, A3 = (1, 3, 4), và kiểm tra trực tiếp cho thấy nếu
Ai có phần tử chung với ít nhất một trong ba tập đó thì nó chỉ có dạng duy nhất là
82 Trần Nam Dũng (chủ biên)
(2, 3, 4). Như thế, Kn−4 tập còn lại sẽ là tập con của {5, 6, . . . , n}, và như thế thì
số tập con tối đa trong tình huống này là Kn−4+4.
Kết hợp cả hai trường hợp này ta được Kn = Kn−4+ 4. Vậy ta chỉ cần xét bài toán
tại trường hợp cơ sở là n= 5, 6, 7, 8, thậm chí có thể xét ngay tại trường hợp n= 1,
2, 3, 4. Kiểm tra trực tiếp cho thấy K1 = K2 = 0, K3 = 1, K4 = 4. Do đó, giá trị lớn
nhất của Kn sẽ là
Kn =

n với n≡ 0 (mod 4)
n−1 với n≡ 1 (mod 4)
n−2 với n≡ 2, 3 (mod 4)
.
Và việc chỉ ra các tập hợp thỏa mãn đề bài xin được dành cho các bạn (chú ý đến
các bước chứng minh phía trên để dựng).
Tóm lại, ta có kết luận giá trị nhỏ nhất của m để trong m tập con bất kì của A luôn
có hai tập giao nhau tại đúng một phần tử là
m=

n+1 với n≡ 0 (mod 4)
n với n≡ 1 (mod 4)
n−1 với n≡ 2, 3 (mod 4)
.
Bài toán được giải quyết hoàn toàn.
Bài 6.12. Cho tập S= {1, 2, 3, . . . , 2009}. A là tập con có n phần tử của S. Tìm n
nhỏ nhất sao với mọi cách chọn tập A thì trong A luôn có hai phần tử a, b mà
a
b
= 3.
(Bắc Ninh)
Lời giải. Với mỗi số nguyên dương x, ta kí hiệu v(x) là số nguyên không âm lớn nhất
thỏa mãn 3v(x) | x (nói cách khác, nếu đặt v(x) = k thì x chia hết cho 3k và không
chia hết cho 3k+1). Bây giờ, ta chia tập S thành các tập con Si thỏa mãn
Si = {x ∈ S | v(x) = i}.
Ta chứng minh rằng số phần tử được chọn là nhiều nhất nếu ta chọn các tập S0,
S2, S4, . . . Thật vậy, với mỗi số nguyên dương k không chia hết cho 3, xét tập Tk =
{k, 3k, 32k, . . .}. Rõ ràng các tập Tk phủ kín S.
Xét một giá trị k bất kì. Khi đó, trong tập A được chọn sẽ không tồn tại hai phần tử
liên tiếp cùng nằm trong Tk. Như thế, nếu đặt s là số nguyên không âm lớn nhất sao
cho 3s · k < 2009 thì ta chỉ có thể chọn được nhiều nhất
⌊
s+1
2
⌋
phần tử thuộc Tk,
và giá trị đó đạt được nếu ta chọn các số k, 32k, 34k, . . .
Lời giải và bình luận đề thi các tỉnh, các trường Đại học năm học 2009-2010 83
Do mệnh đề trên đúng với số k nguyên dương bất kì, nên gộp lại, số phần tử được
chọn sao cho không có phần tử nào nhiều gấp ba lần phần tử kia nằm trong các tập
S0, S2, . . . Tính toán trực tiếp, ta có
|S0|= 1340, |S1|= 446, |S2|= 149, |S3|= 50 |S4|= 16,
|S5|= 6, |S6|= 2, |Si|= 0 ∀i≥ 7.
Và do đó, nếu ta chọn 1507 phần tử nằm trong các tập S0, S2, S4, S6 thì bất kì hai
phần tử a, b phân biệt nào thuộc S cũng đều thỏa mãn a 6= 3b. Vậy tập hợp A cần có
ít nhất 1508 phần tử, hay giá trị nhỏ nhất của n là 1508.
Bài 6.13. Cho tập A = {1, 2, 3, . . . , 2009}. Chứng minh rằng, có thể tô màu mỗi
phần tử của tập A bằng một trong hai màu đen trắng sao cho mọi cấp số cộng công
sai khác 0 gồm 18 phần tử của A đều được tô bởi đủ cả hai màu.
(Hải Phòng)
Lời giải. Rất có thể một số bạn sẽ cố gắng tìm một cách tô (xây dựng cấu hình cụ
thể) cho bài toán, và sẽ rất nhanh chóng cảm thấy khó khăn với giá trị rất lớn của
các con số. Một số khác sẽ đi tìm một phương án tiếp cận nhẹ nhàng hơn . . .
Do mỗi màu chỉ được tô bới một trong hai màu đen hoặc trắng, nên số cách tô màu
2009 số này là 22009. Ta đếm số cách tô sao cho có một cấp số cộng gồm 18 số cùng
màu. Rõ ràng, ta sẽ tô 18 số này cùng màu, và tô màu tùy ý cho 1991 số còn lại.
Như vậy, số cách tô dẫn đến xuất hiện một cấp số cộng có 18 số cùng màu sẽ nhỏ
hơn 2a ·21991 = a ·21992, do chắc chắn sẽ có những cách trùng nhau trong các cách
tô này (ở đây, kí hiệu a là số lượng cấp số cộng gồm 18 số).
Bài toán sẽ được giải quyết nếu ta chứng minh được số cách tô xuất hiện cấp số cộng
cùng màu nhỏ hơn tổng số cách tô. Khi đó sẽ có một cách tô mà không có 18 số
cùng màu nào lập thành một cấp số cộng). Tức ta cần chứng minh a ·21992 < 22009,
hay là a< 217.
Bây giờ ta đếm số lượng cấp số cộng. Xét một cấp số cộng x, x+ d, x+ 2d, . . . ,
x+17d, trong đó x, d > 0 và x+17d ≤ 2009. Tức là d ≤ 2009− x
17
. Do x là một số
bất kì trong [1, 2009], nên bất đẳng thức của d cho ta
a≤
2009
∑
k=1
2009− k
17
=
2009 ·2010
17 ·2 < 2
17.
Điều kiện a< 217 được thỏa mãn và phép chứng minh kết thúc.
Bình luận. Phiên bản đầu tiên của bài toán này xuất hiện trong IMO Shortlist 1987
do Romania đề nghị, sau đó được chọn là bài 6 (bài khó nhất) của German TST
84 Trần Nam Dũng (chủ biên)
1988. Bài toán gốc được phát biểu như sau: Chứng minh rằng có thể tô màu các số
nguyên dương từ 1 đến 1987 bởi bốn màu sao cho mỗi số được tô bởi đúng một màu
và không tồn tại bất kì cấp số cộng nào chứa 10 số cùng màu.
Các bạn có thể tham khảo lời giải của bài này trong cuốn IMO Compendium (trang
496 - 497) hoặc Polya’s Footsteps (trang 146 - 147) (tuy nhiên cũng khá giống với
lời giải ở trên).
Bài 6.14. Tập hợp A⊂R được gọi là có tính chất T nếu A có không ít hơn bốn phần
tử và ab+ cd thuộc A với mọi a, b, c, d phân biệt thuộc A.
(a) Hãy chỉ ra tập hợp A gồm bốn phần tử, có tính chất T.
(b) Có hay không tập hợp A⊂ (0, +∞) gồm bốn phần tử và có tính chất T.
(Đại học Sư phạm)
Lời giải. Ta sẽ giải quyết câu (b) trước (điều đó sẽ giúp giải quyết câu (a) một cách
nhanh gọn). Giả sử tồn tại bốn số thực a, b, c, d thỏa mãn đề bài. Xét các đẳng thức
(ad+bc)− (ac+bd) = a(d− c)+b(c−d) = (b−a)(c−d)< 0,
(ab+ cd)− (ad+bc) = a(b−d)+ c(d−b) = (a− c)(b−d)> 0.
Do vậy
ad+bc< ac+bd < ab+ cd.
Mặt khác, tất cả ba số kể trên đều thuộc vào tập T, nên chỉ có các trường hợp sau
xảy ra.
+ Trường hợp 1. ad+bc= b. Khi đó ta có ac+bd = c và ab+ cd = d. Như vậy
b−d = (ad+bc)− (ab+ cd) = (c−a)(b−d),
suy ra c−a= 1. Và như thế ta tìm được
0= (ab+ cd)−d = ab+d(c−1) = a(b+d),
nhưng rõ ràng điều này vô lí vì 0< a< b< c< d. Vậy trường hợp này bị loại.
+ Trường hợp 2. ad+bc= a.
- Nếu ab+ cd = c, thì ac+bd = b và ta giải quyết tương tự trường hợp trên.
- Xét trường hợp ab+ cd = d, lúc này ta có thể cho ac+ bd = b (trường hợp kia
được giải quyết hoàn toàn tương tự). Khi đó
a−b= (ad+bc)− (ac+bd) = (b−a)(c−d).
Lời giải và bình luận đề thi các tỉnh, các trường Đại học năm học 2009-2010 85
Từ đây ta tìm được d− c= 1, dẫn tới
0= (ac+bd)−b= ac+b(d−1) = c(a+b),
và ta lại thu được điều vô lí.
Tóm lại, không tồn tại bốn số 0< a< b< c< d thỏa mãn đề bài.
Bây giờ trở lại câu (a). Từ cách xác định kể trên, ta sẽ thử cho a= 0. Khi đó c= 1,
bd = 1. Và ta có thể cho(a, b, c, d) =
(
0,
1
2
, 1, 2
)
là thu được bộ số thỏa mãn đề
bài.
Bài 6.15. Cho số nguyên dương n > 10. Tìm m ∈ N∗ lớn nhất thỏa mãn điều kiện:
Tồn tại m tập con A j của tập A= {1, 2, 3, . . . , 2n}, mỗi tập con gồm n phần tử sao
cho |Ai∩A j ∩Ak| ≤ 1 với mọi 1≤ i< j < k ≤ n.
(Đại học Khoa học tự nhiên)
Lời giải. Quá trình chứng minh được thực hiện theo bốn bước như sau.
+ Bước 1. m ≤ 8. Để có điều này, ta sẽ chứng minh mỗi phần tử thuộc vào không
quá bốn tập hợp. Ngược lại, giả sử tồn tại một phần tử (kí hiệu là 1) thuộc vào năm
tập hợp khác nhau (kí hiệu là A1, A2, . . . , A5). Xét các tập Bi = Ai\{1}. Khi đó, theo
giả thiết ta được |Bi∩B j ∩Bk|= 0 với mọi 1≤ i< j < k ≤ 5, tức mỗi phần tử từ 2
đến 2n chỉ thuộc vào nhiều nhất hai tập B. Do vậy số phần tử tối đa của năm tập này
là 2(2n−1). (1)
Mặt khác, |Bi|= n−1, nên năm tập này có tổng số phần tử là 5(n−1). (2)
Từ (1) và (2), ta suy ra 5(n− 1) ≤ 2(2n− 1), hay n ≤ 3 (vô lí). Vậy điều giả sử là
sai, hay mỗi phần tử chỉ thuộc vào tối đa bốn tập hợp. Như vậy, m tập hợp có tối đa
8n phần tử, tức m≤ 8.
+ Bước 2. m≤ 6. Gọi K4 là số các phần tử thuộc vào đúng bốn tập hợp. Kết hợp với
giả thiết cùng với kiểm tra trực tiếp, ta được k≤ 6, tức tổng số phần tử của m tập hợp
sẽ không vượt quá 6 ·4+(2n−6) ·3= 6n+6. Như thế, mn≤ 6n+6, hay m≤ 6.
+ Bước 3. m≤ 5. Định nghĩa K3 tương tự như K4. Theo giả thiết, ta có nhận xét: giá
trị lớn nhất của K3 chính là số cách chọn ba số khác nhau trong sáu số từ 1 đến 6
(và do đó, K3 ≤C36 = 20). Do m≤ 6 nên K4 ≤ 3 (K4 kí hiệu ở bước 2). Ngoài ra, để
ý rằng, nếu có một phần tử i thuộc vào bốn tập hợp (chẳng hạn là A1, A2, A3, A4),
thì sẽ không có phần tử j nào khác thuộc vào (Ai, A j, Ak) (1≤ i< j < k ≤ 4), tức
K3 phải giảm đi bốn phần tử. Như vậy, tổng số phần tử lớn nhất của các tập hợp sẽ
là 4.K4+(2