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

t
vậy, giả sử tồn tại số k = pq có màu đen. Khi đó,
(q+1)p= qp+ p có màu đen;
(q+2)p= (q+1)p+ p có màu đen;
· · ·
Như vậy, tất cả các số lớn hơn k và là bội của p đều có màu đen. Mặt khác, theo
bước 1 thì tất cả các số màu trắng đều là bội của p. Như vậy, số lượng số màu trắng
phải là hữu hạn, trái giả thiết số lượng số màu trắng là vô hạn. Vậy điều giả sử là sai
và bước 2 được giải quyết.
Từ hai bước trên ta có kết luận rằng, một số có màu trắng khi và chỉ khi số đó là bội
của p. Từ đây, kết luận của bài toán là hiển nhiên.
Bài 6.8. Cho tập hợp S= {1, 2, 3, . . . , n}. Tìm số cách chia tập S thành ba tập con
khác rỗng sao cho mỗi tập con không chứa hai số nguyên liên tiếp.
(Đại học Sư phạm)
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 79
Lời giải. Kí hiệu S(n) là số cách chia tập S thành ba tập con không chứa khác rỗng
mà bất kì tập con nào cũng không chứa hai phần tử liên tiếp nhau. Ta sẽ tìm cách
tính S(n+1) theo S(n).
Giả sử ta đã chia được ba tập con và tổng số phần tử của chúng là n. Bổ sung thêm
phần tử n+1. Ta có hai khả năng xảy ra.
+ Khả năng 1. n+1 không tạo thành một tập con mới (tức tập chứa n+1 có ít nhất
một phần tử khác). Khi đó, rõ ràng ta có hai cách bổ sung n+1 (vào một trong hai
tập không chứa n). Vậy số cách xây dựng tập con trong trường hợp này là 2S(n).
+ Khả năng 2. n+ 1 tạo thành một tập con mới. Khi đó, n số từ 1 đến n phải nằm
trong hai tập hợp còn lại. Có thể thấy ngay chỉ có một cách chia thỏa mãn (một tập
chứa các số chẵn và tập còn lại chứa các số lẻ). Do đó, số cách trong trường hợp này
là một cách.
Vậy ta thu được công thức truy hồi
S(n+1) = 2S(n)+1,
hay
S(n+1)+1= 2[S(n)+1]. (∗)
Mặt khác, kiểm tra trực tiếp ta có S(3) = 1. Kết hợp với (∗), ta dễ dàng tìm được
công thức tổng quát của S(n) là S(n) = 2n−2−1 với n≥ 3.
Như vậy, số cách chia tập hợp thỏa mãn đề bài là S(1) = S(2) = 0 và S(n) = 2n−2−1
với n≥ 3.
Bình luận. Bài này không khó trong việc lập công thức truy hồi, nhưng lại rất dễ
sai (vì quên rằng n+1 có thể tự lập thành một tập mới). Để tránh bị bỏ sót, nên tính
trực tiếp một số giá trị đầu tiên.
Bài 6.9. Cho n là số nguyên lớn hơn 1 và P1, P2, . . . , Pn là các tập con có hai phần
tử và đôi một phân biệt của tập hợp S = {1, 2, 3, . . . , n} thỏa mãn tính chất: nếu
i 6= j mà Pi∩Pj 6= /0 thì tồn tại k để Pk = {i, j}. Chứng minh rằng với mỗi số i ∈ S
xuất hiện đúng hai lần trong các tập Pj với j = 1, 2, . . . , n.
Lời giải. Với mỗi 1≤ i≤ n, kí hiệu xi là số lần xuất hiện của số i trong các tập hợp.
Theo giả thiết, ta có x1+ x2+ · · ·+ xn = 2n.
Cũng theo giả thiết, nếu |Pi∩Pj| 6= 0 thì tồn tại Pk = {i, j}. Và rõ ràng, ứng với mỗi
bộ (i, j) mà |Pi ∩Pj| 6= 0 (không kể thứ tự của i và j) thì các Pk là phân biệt. Cho
nên số các bộ (i, j) mà |Pi∩Pj| 6= 0 không vượt quá n.
80 Trần Nam Dũng (chủ biên)
Nhưng, số bộ số này lại bằng
n
∑
i=1
C2xi =
(x21+ · · ·+ x2n)− (x1+ · · ·+ xn)
2
≥ (x1+ · · ·+ xn)
2
2n
− x1+ · · ·+ xn
2
≥ 2n−n= n.
Như vậy dấu bằng trong bất đẳng thức trên phải xảy ra, tức x1 = · · ·= xn = 2 và đây
chính là điều phải chứng minh.
Bài 6.10. Cho số nguyên n không nhỏ hơn 3. Giả sử mỗi số nguyên dương không
lớn hơnC1n+C
2
n+C
3
n được tô một trong hai màu xanh hoặc đỏ. Chứng minh tồn tại
dãy các số cùng màu thỏa mãn
(1) x1 < x2 < · · ·< xn;
(2) x2− x1 ≤ x3− x2 ≤ ·· · ≤ xn− xn−1 ≤C2n .
Lời giải. Ta sẽ chứng minh bài toán bằng quy nạp. Giả sử mệnh đề của bài toán đã
đúng tới n, tức luôn tồn tại dãy 1≤ x1 < x2 < · · ·< xn ≤C1n+C2n+C3n có cùng màu
và thỏa mãn x2− x1 ≤ x3− x2 ≤ ·· · ≤ xn− xn−1 ≤ C2n . Không mất tính tổng quát,
giả sử n số này có màu đỏ. Xét mệnh đề với n+1.
+ Giả sử tồn tại số xn+1 cũng có màu đỏ vàC2n ≤ xn+1− xn ≤C2n+1. Khi đó,
xn+1 ≤C2n+1+ xn ≤C2n+1+C1n+C2n+C3n =C1n+1+C2n+1+C3n+1−1,
nên số xn+1 thỏa mãn toàn bộ các điều kiện để được bổ sung vào dãy, tức ta có dãy
x1, x2, . . . , xn+1 thỏa mãn đề bài.
+ Nếu tất cả các số xn+ i, với C2n ≤ i ≤ C2n+1 đều có màu xanh, thì chú ý rằng
C2n+1−C2n =
(n+1)n
2
− n(n−1)
2
= n, nên dãy xn+ i gồm n+1 số và ngay lập tức
thỏa mãn tất cả các điều kiện của bài toán.
Vậy mệnh đề đúng với n+1. Theo đó, ta chỉ cần chứng minh bài toán với n= 3, tức
cần chứng minh tồn tại ba số x1, x2, x3 sao cho
(1) x1, x2, x3 cùng màu.
(2) 1≤ x1 < x2 < x3 ≤ 7.
(3) x2− x1 ≤ x3− x2 ≤ 3.
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 81
Ta sử dụng phản chứng. Giả sử tồn tại cách tô sao cho không tìm được ba số như
vậy. Không mất tính tổng quát, giả sử 2 được màu đỏ. Nếu 2 được tô màu đỏ, dẫn
đến cả 3, 4, 5 đều có màu xanh (nếu không, thì số được tô màu đỏ sẽ hợp với 1, 2
tạo thành dãy thỏa mãn đề bài). Nhưng khi đó, (3, 4, 5) lại thỏa mãn cả ba điều kiện
trên, mâu thuẫn. Do vậy 2 có màu xanh.
Bây giờ giả sử 3 có màu đỏ. Lí luận tương tự như trên, ta được 5 và 6 có màu xanh,
4 và 7 có màu đỏ, dẫn đến dãy (1, 4, 7) thỏa mãn cả ba điều kiện trên, mâu thuẫn.
Do vậy 3 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+(20− 4K4) · 3+(2n− 20) · 2 ≤ 4n+ 20, hay mn ≤ 4n+ 20. Kết hợp với
n> 10 (bây giờ mới thấy được tại sao n> 10), ta phải có m≤ 5.
86 Trần Nam Dũng (chủ biên)
+ Bước 4. m≤ 4. Tiếp tục đánh giá tương tự bước 3, ta được
mn≤ 4K4+(10−4K4) ·3+(2n−10) ·2≤ 4n+10.
Từ đó suy ra m≤ 4.
Cuối cùng, ta sẽ dựng bốn tập hợp thỏa mãn đề bài. Xét các tập sau đây
A1 = {1, 2, . . . , n}, A2 = {n+1, n+2, . . . , 2n},
A3 = {1, 3, . . . , 2n−1}, A4 = {2, 4, . . . , 2n},
thì rõ ràng tất cả các điều kiện của bài toán được thỏa mãn. Vậy giá trị lớn nhất của
m là 4.
Bình luận. Các bước đánh giá m trong bài này thể hiện vẻ đẹp của toán rời rạc:
luôn biến ảo đến khó lường, và luôn phải nhạy cảm để phát hiện những mấu chốt
cuối cùng. Điều để lại ấn tượng nhiều nhất khi làm bài này là việc sử dụng các bất
đẳng thức yếu hơn để chứng minh các bất đẳng thức mạnh hơn - một điều không
hề thường gặp trong các bài toán của chúng ta, cũng là thử thách cho sự kiên trì và
nhạy bén trong tất cả các tình huống có thể xảy ra.
Bài này được ra trong đề thi APMC 2001 (Austrian-Polish Mathematical Competi-
tion).
Bài 6.16. Cho A = {1, 2, . . . , 2n}. Một tập con của A được gọi là tốt nếu nó có
đúng hai phần tử x, y và |x−y| ∈ {1, n}. Tìm số các tập hợp {A1, A2, . . . , An} thoả
mãn điều kiện Ai là tập con tốt với mọi i= 1, 2, . . . , n và A1∪A2∪·· ·∪An = A.
(Phổ thông Năng khiếu)
Lời giải. Từ giả thiết, ta sẽ viết lại bài toán như sau (các bạn tự kiểm tra tính tương
đương của bài toán này so với bài ban đầu): “Cho một hình chữ nhật kích thước 2×n
được chia thành các ô vuông đơn vị. Đánh số các ô từ trái qua phải là 1, 2, . . . , n
(hàng 1) và n+ 1, n+ 2, . . . , 2n (hàng 2). Lát chúng bằng các quân domino 1× 2
sao cho chúng phủ kín hình chữ nhật và không có hai quân nào đè lên nhau. Ngoài
ra, với n lẻ, ta được bổ sung thêm một quân domino “đặc biệt” có thể phủ kín hai ô
n và n+1. Đếm số cách lát thỏa mãn đề bài”.
Với bài toán này, xét Sn là số cách lát thỏa mãn đề bài với hình chữ nhật kích thước
2×n. Ta sẽ tìm cách xây dựng công thức truy hồi cho Sn.
Giả sử ta đã lát được hình chữ nhật 2× (n+ 1) bằng các quân domino. Xét quân
domino phủ lên ô vuông n. Có ba khả năng xảy ra.
+ Khả năng 1. Quân domino đó phủ lên hai ô (n, 2n). Rõ ràng phần còn lại là một
hình chữ nhật kích thước 2×n, và số cách lát trong tình huống này là Sn.
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 87
+ Khả năng 2. Quân domino đó phủ lên hai ô (n, n+1). Như vậy, buộc phải có một
quân domino phủ lên hai ô (2n−1, 2n) và khi đó, phần còn lại là một hình chữ nhật
kích thước 2× (n−1). Tức số cách lát trong tình huống này là Sn−1.
+ Khả năng 3. Quân domino đó phủ lên hai ô (n, n+1) (với n lẻ). Khi đó, phần còn
lại chỉ có thể lát được bằng các quân domino nằm ngang (nếu có một quân domino
nào nằm dọc thì nó sẽ chia hình chữ nhật thành hai phần, mỗi phần có một số lẻ ô
chưa được lát (do quân domino “đặc biệt” gây ra)). Tức trong trường hợp này chỉ có
một cách lát duy nhất.
Như vậy ta xây dựng được công thức truy hồi như sau
S2k = S2k−1+S2k−2−1 (lưu ý rằng khi n chẵn thì không có quân domino “đặc
biệt” nên phải bớt đi một cách của S2k−1).
S2k+1 = S2k+S2k−1 (lập luận tương tự với quân domino “đặc biệt”).
Và bằng quy nạp ta sẽ thu được S2k = F2k, S2k+1 = F2k+1+ 1, trong đó Fk là số
Fibonacci thứ k của dãy Fibonacci được xác định bởi công thức
F0 = F1 = 1, Fn+2 = Fn+1+Fn.
Cuối cùng ta được công thức tổng quát
Sn =
1√
5
[(
1+
√
5
2
)n
−
(
1−√5
2
)n]
+
1− (−1)n
2
.
Bình luận. Đây chỉ là biến thể của một bài toán quen thuộc: “Có bao nhiêu cách lát
đường đi 2×n bằng các quân domino?”. Tuy nhiên cách phát biểu làm cho bài toán
khó hình dung hơn. Đây cũng là một đặc điểm rất điển hình của bài toán tổ hợp:
cùng một bài toán có thể có nhiều cách phát biểu khác nhau, và quan trọng là ta phải
tìm được cách phát biểu thuận lợi cho lời giải.
88 Trần Nam Dũng (chủ biên)
Chương 7
Dãy số
“Toán học là cánh cửa và là chìa khóa để đi vào các ngành khoa học khác.”
Roger Bacon
7.1 Đề bài
7.1. Cho dãy (un) xác định bởi u1 =
1
2
và un+1 =
3
2
u2n−
1
2
u3n. Chứng minh rằng dãy
(un) có giới hạn. Tìm giới hạn đó.
7.2. Chứngminh rằng với mỗi số nguyên dương n cho trước thì phương trình x2n+1=
x+1 có đúng một nghiệm thực. Gọi nghiệm đó là xn. Tính lim
n→∞xn.
7.3. Cho dãy số (an) xác định bởi a1 = a2 = 12
√
2 và
an+1 =−an
√
a2n−1+1+an−1
√
a2n+1
với mọi n≥ 2. Chứng minh rằng
√
2+2
√
a2n+1 là số nguyên dương với mọi n≥ 1.
7.4. Giả sử dãy số nguyên dương {an} thỏa mãn a4 = 4 và
1
a1a2a3
+
1
a2a3a4
+ · · ·+ 1
anan+1an+2
=
(n+3)an
4an+1an+2
với mọi n nguyên, n≥ 2. Chứng minh rằng an = n với mọi n nguyên dương.
7.5. Cho dãy số {xn} xác định bởi x1 = 3 và xn+1 = x
2
n+3
3xn
với mọi n ≥ 1. Chứng
minh rằng dãy {xn} có giới hạn và tìm giới hạn đó.
89
90 Trần Nam Dũng (chủ biên)
7.6. Cho dãy số nguyên {an} thỏa mãn các điều kiện
(1) |an+2−an| ≤ 2 với mọi n thuộc N∗;
(2) Tồn