Giáo trình Toán logic và rời rạc

C h u y ê n đ ề : T o á n L o g i c & R ờ i r ạ c | 1 
Lê Trần Nhạc Long ( Chủ Biên) – Trần Nguyễn Quốc Cƣờng 
Chuyªn ®Ò 
To¸n logic 
vµ rêi r¹c 
Đà Nẵng 1/2011 
⪷⎈⪸ 
C h u y ê n đ ề : T o á n L o g i c & R ờ i r ạ c | 2 
Lêi nãi ®Çu 
 Thượng đế có tất cả những lời giải ngắn nhất 
và hay nhất của mọi bài toán 
(P.Erdos) 
 Hiện nay các bài toán về lí thuyết tổ hợp càng ngày càng có vẻ xa lạ với học sinh 
chúng ta và cũng có khi xa lạ với nhiều bạn học sinh chuyên toán, các bạn còn e ngại vì 
khi nhìn vào các bài toán có vẻ “ dao to búa lớn” vì sao? Không hiểu hết đề hay khó quá. 
Điều đó càng khiến cho những con ngƣời tò mò ham học hỏi muốn lao vào. Những bài 
toán tổ hợp đều làm cho con ngƣời rèn một tƣ duy cao, nó nhƣ những câu hỏi IQ thú vị. 
Có một số bài toán các bạn sẽ nghĩ điều đó hiển nhiên mà sao chứng minh lại khó quá? 
Đó chính là mấu chốt vấn đề của một bài toán tổ hợp. Để làm tốt các bài toán này cũng 
đòi hỏi các bạn một tƣ duy cao, những suy luận tinh tế , sắc bén. Để đƣợc nhƣ vậy cũng 
yêu cầu các bạn một sự luyện tập. Trong bài viết này , tôi xin đề cập đến một số vấn đề 
sơ cấp và phổ biến của toán tổ hợp để mong có thể phần nào truyền tải đến một số bạn 
yêu toán dễ dàng tiếp cận và cũng ít e ngại hơn với các bài toán tổ hợp nữa. Vì kiến thức 
còn hạn hẹp nên có một vài sự sai xót , mong các bạn thông cảm . 
 Qua đây tôi cũng xin giới thiệu với các bạn một số website cho các bạn yêu toán: 
w.w.w.diendantoanhoc.net;( Diễn đàn VMF) và một số diễn đàn khác nhƣ: 
w.w.w.mathscope.org ; w.w.w.mathlinks.ro ; w.w.w.math.vn..ở đó các bạn sẽ học hỏi 
đƣợc nhiều kinh nghiệm và tiếp xúc với bạn bè bốn phƣơng. 
 Cuối cùng tôi cũng xin trân trọng cảm ơn các anh Phạm Hy Hiếu ( Sinh viên đại học 
ngoại thƣơng Sài Gòn- Huy chƣơng bạc IMO 2009) , anh Võ Quốc Bá Cẩn (sinh viên 
Đaị học Y Dƣợc Cần Thơ) đã sửa chữa, đóng góp giúp tôi hoàn thành bài viết này.Cảm 
ơn các bạn đã đón đọc bài viết của tôi. Mọi ý kiến đóng góp xin gửi về đựa chỉ: 
winwave1995@yahoo.com.vn hoặc liên hệ trực tiếp qua nick yahoo: winwave1995 
 Lê Trần Nhạc Long
C h u y ê n đ ề : T o á n L o g i c & R ờ i r ạ c | 3 
MỤC LỤC 
Lời nói đầu..2 
 Problem 1:Các bài toán giải bằng đồ thị 
Lê Trần Nhạc Long....4 
 Problem 2:Các bài toán giải bằng tô màu 
Lê Trần Nhạc Long10 
 Problem 3: Nguyên lí bất biến, đơn biến. 
Lê Trần Nhạc Long18 
 Problem 4: Nguyên lí cực hạn 
Trần Nguyễn Quốc Cường..26 
 Problem 5: Nguyên lí Dirichlet và ứng dụng 
 Lê Trần Nhạc Long, Võ Quốc Bá Cẩn41 
 Problem 6:Các bài toán về trò chơi 
Trần Nguyễn Quốc Cường53 
Problem 7:Giới thiệu về định lí Ramsey-số Ramsey 
Lê Trần Nhạc Long.58 
Một số bài tập tổng hợp..60 
Tài liệu tam khảo.63 
C h u y ê n đ ề : T o á n L o g i c & R ờ i r ạ c | 4 
Problem 1: Lý thuyết đồ thị 
“Toán học và con người như hai đỉnh luôn nối với nhau 
bởi một đoạn thẳng” 
 Lê Trần Nhạc Long 
Trường THPT chuyên Lê Quý Đôn –tp Đà Nẵng 
Lý thuyết đồ thị nói chung , đặc biệt đồ thị tô màu đƣợc vận dụng để giải các bài toán 
không mẫu mực hiệu quả đặc biêt là Tổ Hợp Đại Số 
Ta sẽ thể hiện mối qua hệ giữa các giả thiết bài toán trong không gian và có những khẳng 
định tƣơng ứng về đồ thị tô màu để có vận dụng gải quyết hàng loạt bài toán đƣợc xét 
Và ta sẽ cùng đi đến những bài toán sau để hiểu rõ thêm về lí thuyết đồ thị 
Ví dụ 1: trong phòng có 6 người chứng minh rằng tồn lại 3 người đôi một quen nhau và 
đôi một không quen nhau. 
Giải: xét 6 điểm trên mặt phẳng. Chọn 1 điểm bất kì ta dùng đoạn nối liền giữa các điểm 
thể hiện sự quen nhau và và các điểm nối 
nét đứt với nhau chỉ sự không quen nhau 
Bây giờ ta xét 6 điểm O,A,B,C,D,E lấy 
O làm tâm , 
Trong 5 điểm còn lại , ta thấy 2 ngƣời 
bất kì hoặc là quen nhau , hoặc là không 
quen nhau , trên hình theo nguyên lí 
Dirichlet thì tồn tại ít nhất 3 đƣờng 
thẳng nét liền từ O đến 5 điểm 
A,B,C,D,E hoặc 3 đƣờng nối nét đứt . 
Bây giờ ta chỉ cần xét sự quen nhau . thật 
vậy nếu trong 3 điểm A,B,C mà nối lại 
với nhau thì ta đƣợc 1 tam giác có đỉnh 
là O => thỏa mãn bài toán, nếu không nối lại thì 3 điểm A,B,C sẽ chỉ nối nhau bằng nét 
đứt cũng là điều phải chứng minh. Vậy luôn tìm đƣợc 3 ngƣời đôi một quen nhau hoặc 
không quen nhau. 
Nhận xét: trong bài này để lời giải ngắn gọn ta có thể dùng thêm mệnh đề Đại số , đó là 
 A B A B  
Bây giờ câu hỏi đặt ra là ta có thể tổng quát bài toán này lên n ngƣời mà có k ngƣời đôi 
một quen nhau hoặc m ngƣời đôi một không quen nhau đƣợc không? Đáp án sẽ đƣợc trả 
lời ở phần sau 
C h u y ê n đ ề : T o á n L o g i c & R ờ i r ạ c | 5 
Ví dụ 2: có 17 nhà toán học viết thư cho nhau , viết về 3 đề tài khác nhau mỗi người phải 
viết thư cho các người còn lại biết, từng cặp nhà toán học viết thư trao đổi cùng một đề 
tài. Chứng minh rằng có ít nhất 3 nhà toán học viết thư cho nhau trao đổi về cùng 1 đề 
tài. 
Giải: tƣ tƣởng của chúng ta cũng nhƣ bài toán trên.chọn 17 điểm trên mặt phẳng và đặt 
tên là 1 2 6, ,...,OA OA OA Và cứ 2 điểm bất kì ta dùng màu đỏ nối hai điểm đó chỉ sự trao 
đổi đề tài thứ nhất , màu xanh là 
đề tài thứ 2 và vàng chỉ đề tài 
thứ 3 
Giả sử các cạnh đƣợc tô nhiều 
nhất là màu đỏ theo nguyên lí 
Dirichlet trong 16 cạnh thì có ít 
nhất 6 cạnh đƣợc tô màu đỏ giả 
sử đó là các cạnh 
1 2 6, ,...,OA OA OA trong sáu 
điểm này nếu có 2 điểm đƣợc 
nối với nhau màu đỏ thì tạo 
than 1 tam giác màu đỏ có đỉnh 
là O tức là đã có 3 ngƣời trao 
đổi cùng 1 đề tài. Bây giờ xét 6 
điểm này không có 2 điểm nào 
đƣợc nối với nhau màu đỏ thì 
phải nối với nhau màu xanh 
hoặc vàng . theo ví dụ 1 thì luôn 
tồn tại trong 6 điểm đó 3 điêm cùng đƣợc nối bởi màu xanh hoặc màu vàng.Vậy bài toán 
đƣợc chứng minh  
Ví dụ 3:(ví dụ này không mang tính đồ thị mà dựa vào tư tưởng của nó) 
Trong một nhóm gồm 2n+1 người , với mỗi n người thì tồn tại 1 người trong 2n+1 người 
này quen n người đó .Chứng minh rằng 
a) Có n+1 người đội một quen nhau 
b) Tồn tại 1 người quen hết tất cả các người 
Giải: 
a) Ta sẽ quy nạp: rõ rằng có 2 ngƣời quen nhau , giả sử có k ngƣời đôi một quen nhau (k 
≤ n ) thì tồn tại 1 ngƣời quen k ngƣời này theo giả thiết => có k+1 ngƣời đôi một quen 
nhau .Do đó tồn tại n+1 ngƣời đôi một quen nhau 
b) Xét n ngƣời còn lại trong câu a thì tồn tại 1 ngƣời trong n+1 ngƣời này quen n ngƣời 
đó suy ra ngƣời này quen tất cả các ngƣời còn lại 
C h u y ê n đ ề : T o á n L o g i c & R ờ i r ạ c | 6 
BÀI TẬP: 
Bài 1.1:(TST Hong Kong 1999) Các học sinh được phát bài kiểm tra , mỗi môn một bài , 
trong n (n≥ 3)môn học. Biết rằng với mỗi môn học bất kì có đúng 3 học sinh đạt điểm tối 
ưu ,còn với hai môn tùy ý thì có 1 học sinh đạt điểm tối ưu cho mỗi môn trong cả hai môn 
đó. Hãy xác định n bé nhất sao cho từ các điều kiện có thể suy ra có đúng 1 học sinh đạt 
điểm tối ưu cho mỗi môn trong n môn học (ĐS:8) 
Bài 1.2:Có 3 trường học, mỗi trường học có n học sinh. Một học sinh bất kì có tổng số 
người quen từ 
hai trường học kia là n+1. Chứng minh rằng có thể chọn được ở mỗi trường 1 học sinh 
sao cho 3 học sinh này đôi một quen nhau. 
Bài 1.3:trong một phòng có 5 người, giữa 3 người bất kì luôn tìm được 2 người quen 
nhau và 2 người không quen nhau. Chứng minh rằng nhóm người này có thể ngồi quanh 
một bàn tròn sao cho mỗi người đều quen hai người ngồi cạnh mình 
Bài 1.4: 
Trong một căn phòng có 9 người , biết rằng giữa 3 người bất kì có 2 người quen nhau . 
Chứng minh rằng, có thể tìm được 4 người mà 2 người bất kì trong số đó đều quen nhau 
Bài 1.5:(Trần Nam Dũng-Preparation VMO-2010) Cho 2010 tập hợp, mỗi tập hợp chứa 
45 phần tử. Biết rằng hợp của hai tập hợp bất kỳ chứa đúng 89 phần tử. Hỏi hợp của tất 
cả các tập hợp nói trên chứa bao nhiêu phần tử? 
LỜI GIẢI CÁC BÀI TẬP DÙNG ĐỒ THỊ 
 Bài 1.1:(TST Hong Kong 1999) Các học sinh được phát bài kiểm tra , mỗi môn một bài 
, trong n (n≥ 3)môn học. Biết rằng với mỗi môn học bất kì có đúng 3 học sinh đạt điểm 
tối ưu ,còn với hai môn tùy ý thì có 1 học sinh đạt điểm tối ưu cho mỗi môn trong cả hai 
môn đó. Hãy xác định n bé nhất sao cho từ các điều kiện có thể suy ra có đúng 1 học sinh 
đạt điểm tối ưu cho mỗi môn trong n môn học 
Giải: Ta sẽ biểu thị mỗi học sinh là một điển trên mặt phẳng sao cho không có 3 điểm 
nào thẳng hàng , và cứ hai học sinh đạt điểm tối ƣu cho trong một môn nào đó ta sẽ nối 
hai điểm tƣơng ứng lại với nhau. Nhƣ vậy trong mỗi môn ta sẽ có duy nhất một tam giác. 
Vì cứ hai môn bất kì luôn có 1 học sinh đạt điểm tối ƣu cho cả 3 môn đó nên giữa hai tam 
giác luôn có chung đỉnh 
Ta có nhận xét sau: nếu 4 tam giác có chung một đỉnh thì tất cả các tam giác đều có 
ching đỉnh đó. Thật vậy bởi vì nếu không thì tam giác thứ 5 có chung 4 đỉnh với 4 tam 
giác kia tạo thành 1 tứ giác => vô lí! 
Bây giờ xét 1 tam giác bất kì thì nó sẽ có chung đỉnh với mỗi một trong 7 tam giác còn 
lại. theo nguyên lí Dirichlet thì tồn tại một trong các đỉnh của tam giác đã chọn có chung 
C h u y ê n đ ề : T o á n L o g i c & R ờ i r ạ c | 7 
đỉnh với ít nhất 
2
1
3
n 
 tam giác khác. Theo nhận xét trên ta cần 
2 2
1 4 3 8
3 3
n n
n
. Vậy n nhỏ nhất là 8 
Bài 1.2:Có 3 trường học, mỗi trường học có n học sinh. Một học sinh bất kì có tổng số 
người quen từ hai trường học kia là n+1. Chứng minh rằng có thể chọn được ở mỗi 
trường 1 học sinh sao cho 3 học sinh này đôi một quen nhau 
Giải: Trong 3 trƣờng ta chọn ra 1 học sinh có số ngƣời quen k (k ≤ n) nhiều nhất với một 
trong hai trƣờng kia.Giả sử ngƣời đó là A quen k học sinh ở trƣờng thứ 2. Khi đó sẽ quen 
n-k+1 học sinh ở trƣờng thứ 3.Xét học sinh B ở trƣờng số 3 nằm trong số ngƣời quen của 
A, nếu B quen ngƣời học sinh C ở trƣờng thứ 2 nằm trong k ngƣời quen của A thì A,B,C 
là 3 ngƣời cần tìm. Còn nếu B quen C không nằm trong k ngƣời quen của A thì B sẽ quen 
không quá n-k học sinh của trƣờng thứ 2 => B sẽ quen không ít hơn (n+1)-(n-k)=k+1 học 
sinh của trƣờng 1. Mà theo cách chọn k thì k là số lớn nhất => mâu thuẫn. vậy bài toán 
đƣợc chứng minh 
Bài 1.3:trong một phòng có 5 người, giữa 3 người bất kì luôn tìm được 2 người quen 
nhau và 2 người không quen nhau. Chứng minh rằng nhóm người này có thể ngồi quanh 
một bàn tròn sao cho mỗi người đều quen hai người ngồi cạnh mình 
Giải: 
C h u y ê n đ ề : T o á n L o g i c & R ờ i r ạ c | 8 
xét mỗi ngƣời là 1 điểm trên Mặt phẳng . 5 ngƣời này sẽ là 5 điểm ko thẳng hàng và tạo 
thành một ngũ giác lồi ABCDE 
ta sẽ thể hiện các đƣờng đƣợc nối liền là chỉ sự quen nhau còn nét đứt là sự ko quen nhau 
của 2 ngƣời bất kì 
ta sẽ chứng minh hình trên là điều cần chứng minh . thật vậy nếu ta đã sắp 1 ngƣời quen 
với 2 ngƣời ngồi cạnh giả sử ngƣời này lại quen với ngƣời đối diện tiếp theo giải sử nhƣ 
A quen B và E mà nếu A cũng quen cả C thì Tam giác ACE thỏa mãn đề bài nhƣng ABC 
thì ko vì trong đó sẽ ko có 2 ngƣời nào ko quen nhau 
do đó cách sắp sếp nhƣ trên là duy nhất để thỏa nãm yêu cầu bài toán 
Bài 1.4: 
a) Trong một căn phòng có 9 người , biết rằng giữa 3 người bất kì có 2 người quen nhau 
. Chứng minh rằng, có thể tìm được 4 người mà 2 người bất kì trong số đó đều quen nhau 
Giải: Trên mặt phẳng ta lấy 9 điểm và nếu giữa 2 điểm đƣợc tô màu đỏ thể hiện sự quen 
nhau và màu xanh thể hiện sự không quen nhau có 2 trƣờng hợp xảy ra 
TH1: nếu tồn tại một điểm có chung đỉnh với hơn 4 cạnh màu xanh ,giả sử các cạnh đó là 
1 2 3 4, , ,OA OA OA OA vì trong 3 ngƣời bất kì có hai ngƣời quen nhau nên trong 4 
điểm 1 2 3 4, , ,OA OA OA OA , khổng thể nối với nhau cạnh xanh vì thế chings đều phải nối với 
nhau màu đỏ => 4 điểm này lập thành một tứ giác có 4 cạnh và các đƣờng chéo cùng là 
màu đỏ , đây chính là 4 ngƣời đôi một quen nhau 
TH2:nếu tồn tại một điểm có chung đỉnh với không quá 3 cạnh màu xanh , thì theo 
nguyên lí Dirichlet thì tồn tại ít nhất một đỉnh là đầu mút của hai cạnh màu xanh , ví dụ 
đó là H, suy ra nó phải là đầu mút của 6 cạnh , mà theo ví dụ một trong 6 đỉnh chứa 6 
cạnh ấy luôn tồn tại 3 đỉnh nối với nhau bằng màu đỏ vì không tồn tại 3 điểm nối với 
nhau mà xanh ( giả thiết) , nhƣ vậy 3 điểm này hợp với H thành một tứ giác có 4 cạnh và 
các đƣớng chéo nối với nhau thành bằng các cạnh màu đỏ => đây là 4 điểm cần tìm 
Bài 1.5:(Trần Nam Dũng-Preparation VMO-2010) Cho 2010 tập hợp, mỗi tập hợp chứa 
45 phần tử. Biết rằng hợp của hai tập hợp bất kỳ chứa đúng 89 phần tử. Hỏi hợp của tất 
cả các tập hợp nói trên chứa bao nhiêu phần tử? 
Giải: Do hợp của hai tập hợp bất kỳ chứa đúng 89 phần tử nên giao hai tập hợp bất kỳ 
chứa đúng 1 phần tử. 
Ta chọn ra một tập hợp A0 gồm 45 phần tử : 1 2 45, ,...,{ }X x x x 
Do 2009 tập hợp còn lại, mỗi tập hợp đều chứa 1 phần tử trong A0 nên theo nguyên lí 
Dirichlet ra suy ra có một phần tử trong X (giả sử là x1) nằm trong ít nhất 
2009
45
1 45
tập hợp. Đặt 45 tập hợp này là A1 , A2 ,  , A45 
C h u y ê n đ ề : T o á n L o g i c & R ờ i r ạ c | 9 
Suy ra x1 nằm trong ít nhất 46 tập hợp (bao gồm 45 tập hợp A1 , A2 ,  , A45 và tập hợp 
A0) 
Ta chứng minh tất cả các tập hợp còn lại đều chứ 1x bằng phản chứng : giả sử tồn tại 
một tập hợp B không chứa x1 (B nằm trong số 2010 tập hợp đang xét và khác A0 , A1 , A2 
,  , A45 ). Lần lƣợt xét giao của B với A0 , A1 , A2 ,  , A45 : 0 0| |B bA ; 
1 1| |B bA ;  ; 45 45|| B A b . Nhận thấy rằng các tập hợp ( 0,1,2,...,45)i iA đã 
có chung một phần tử là 1x và do đó không có chung phần tử nào khác, từ đó các phần tử 
( 0,1,2,...,45)i ib đôi một phân biệt. Vậy B có ít nhất 46 phần tử (vô lí) . 
Điều giả sử là vô lí nên tất cả các tập hợp trong 2010 tập đang xét đều chứa 1x . Do đó 
hợp của của tất cả các tập hợp đang xét có : (2010.45-2009) phần tử. 
C h u y ê n đ ề : T o á n L o g i c & R ờ i r ạ c | 10 
Problem 2: Tô màu 
“Toán học muôn màu” 
Tô màu nó mang một khái niệm và biểu diễn tƣơng tự nhƣ đồ thị nhƣng mang tính trừu 
tƣợng hơn, tô màu không chỉ là tô các màu mà nó có thể là đánh số hay đặt khái niệm cho 
một tính chất nào đó trong bài toán 
Bây giờ ta cùng đến với các bài toán sau đây 
Ví dụ 1: ( Kiểm tra 15’-10A2-LQĐ 2010)Cho một hình chữ nhật 3×7 chia thành 21 ô . 
Mỗi ô được tô bằng 2 màu xanh hoặc đỏ .chứng minh rằng luôn tồn tại một hình chững 
nhật không tầm thường có 4 đỉnh được tô cùng một màu. 
Giải: 
Cách 1: ( Lê Trần Nhạc Long) 
Ta giả sử số ô đƣợc tô màu đỏ nhiều hơn số ô đƣợc tô màu xanh , theo nguyên lí Dirichlet 
thì có ít nhất 11 ô đƣợc tô màu đỏ 
Bây giờ ta chỉ xét cách tô màu đỏ. Nếu tồn tại một cột có 3 ô đƣợc tô 3 màu thì số màu 
của 6 ô còn lại là 8 thì theo nguyên lí Dirichlet sẽ tồn tại ít nhất một cột có 2 ô đƣợc tô 2 
màu và cột có 3 ô tô màu đỏ và cột có 2 ô tô màu đỏ tạo thành 1 hình chữ nhật cần tìm 
Do đó ta xét mỗi cột chỉ có nhiều nhất 2 ô đƣợc tô màu đỏ, theo nguyên lí Dirichlet thì có 
4 cột có 2 ô đƣợc tô màu đỏ . 
Xét theo hang ngang ta có 23 3 cách tô cho mỗi cột mà ta lại có 4 cách tô nên theo 
nguyên lí Dirichlet có 2 cách tô trùng nhau hai cách tô nàylà hai cột tạo thành hình chữ 
nhật có 4 đỉnh đƣợc tô cùng màu. 
C h u y ê n đ ề : T o á n L o g i c & R ờ i r ạ c | 11 
Cách 2:(Trần Nguyễn Quốc Cường)Cách này thuần túy tô màu 
Ta xét hai hàng đầu tiên , hai ô của một cột đƣợc tô hai màu giống nhau đƣợc gọi là 
“cùng màu”, và hai ô đƣợc tô hai màu khác nhau đƣợc gọi là “khác màu ... 7( 1) 1k là thế thắng cho ngƣời thứ hai ( chứng minh 
trên) 
Vậy trƣờng hợp này ngƣời thứ nhất thua 
Nhƣ thế dự đoán của ta đã đƣợc chứng minh hoàn toàn 
2011 chia 7 dƣ 2 nên theo lí luận trên ngƣời thứ nhất có chiến thuật thắng 
Ví dụ 4: Trên bàn có 2 đống kẹo gồm 2010 và 2011 cây kẹo. 2 người cùng nhau bốc 
kẹo sao cho nếu chọn một đống bốc thì họ phải bốc số kẹo là ước của đống kia. Ai là 
người bốc viên kẹo cuối cùng thì người đó thắng. 
Giải: 
Ngƣời thứ nhất bốc 1 cây ở đống 2010 thì số kẹo 2 bên là một số lẻ. Do đó dù ngƣời 
thứ hai bốc thế nào đi nữa thì số kẹo 2 bên sẽ khác tính chẵn lẻ. Và ngƣời thứ nhất tiếp 
tục bốc 1 cây kẹo ở đống chẵn đƣa về trạng thái (lẻ;lẻ). Nhƣ vậy sau khi ngƣời thứ nhất 
bốc thì sẽ không có đống nào hết cả. Do đó phải đến một thời điểm ngƣời thứ 2 bốc hết 
số kẹo ở một đống và ngƣời thứ nhất chỉ việc bốc số kẹo còn lại của đống còn lại là 
chiến thắng. 
Ở bài này chúng ta lại đến với đại lƣợng bất biến là chẵn lẻ và ta có thể tổng quát bài 
toán với 2 đống kẹo là chẵn và lẻ. Các bạn có thể dựa vào bài trên để giải bài toán với 2 
đống kẹo (4k+2;4l+2). 
Ví dụ 5: Có 2010 viên sỏi. Hai người chơi thay phiên nhau bốc sỏi, mỗi lượt đi người 
chơi được qyền bốc một lượng sỏi là lũy thừa với số mũ tự nhiên bất kì của 2(1;2;3;...). 
Ai bốc được viên sỏi cuối cùng là người chiến tháng. Giả sử cả 2 người chới đều là 
người thông minh. Hỏi ai là người chiến thắng? 
Giải: ta có 2010 chia hết cho 6 và để ý rằng nếu số kẹo sau một số lần bốc là một bội 
của 6 nhƣ 6,12,18,24 thì ngƣời thứ 2 luôn thắng vì vậy nếu ngƣời thứ 2 bốc số kẹo sao 
cho tổng số kẹo của ngƣời thứ 2 và ngƣời thứ nhất sau mỗi lƣợt là một bội của 6 thì sau 
một số lần bốc số kẹo còn lại sẽ là bội "nhỏ" của 6 tức là nằm trong 2 số 24,18,12,6. 
Vậy ngƣời thứ 2 sẽ có chiến thật thắng 
Nếu ngƣời thứ 1 bốc số kẹo là lũy thừa chẵn chả 2 thì ngƣời thứ 2 sẽ bốc số kẹo lũy 
thừa lẻ ( hoặc ngƣợc lại) để bảo toàn số kẹo là bội của 6 
Viết số, tô màu 
Ví dụ 6: Hai người cùng chơi một trò chơi. Ban đầu trên bảng có các số là 1,2,3,4. Mỗi 
lần thực hiện người thứ nhất cộng vào 2 số cạnh nhau một đơn vị, người thứ hai có thể 
đổi chỗ 2 số cạnh nhau. Hai người thay phiên nhau thực hiện, khi nào các số bằng 
nhau thì người thứ nhất thắng. Hỏi người thứ hai có cách nào ngăn người thứ nhất 
thắng hay không? 
Giải: 
Câu trả lời là ngƣời thứ hai có thể ngăn cản ngƣời thứ nhất chiến thắng.Ta thấy sau thao 
tác đầu tiên ngƣời thứ nhất thực hiện thì khoảng cách giữa số lớn nhất và số nhỏ nhất 
C h u y ê n đ ề : T o á n L o g i c & R ờ i r ạ c | 56 
thấp nhất là 2. Và số nhỏ nhất chắc chắn phải là số 1 (có thể sau lần đầu nâng lên 2), số 
lớn nhất là 4(có thể nâng lên 5) ngƣời thứ hai chỉ cần để số 1 ngoài cùng và sắp số 4 
cạnh số 1, các lần sau chỉ dịch chuyển 2 số ở vị trí còn lại tráo đổi cho nhau thì vì 
khoảng cách 2 số đầu chênh nhau ít nhất 2 đơn vị và chúng cùng tăng hoặc chỉ số lớn 
tăng nên không thể bằng nhau. 
Ví dụ 7: Trên bảng có số 2. Hai người chơi trò chơi, nếu trên bảng có số n thì người 
tiếp theo xóa đi số này và viết vào số n+d với d là ước của n và bé hơn n. Ai là người 
viết lên bảng số lớn hơn 2011 trước thì người đó thua. Hỏi ai là người có chiến thuật 
thắng? 
Giải: 
Đầu tiên trên bảng có số 2 thì ngƣời thứ nhất chỉ việc cộng thêm vào số 1 để đƣợc 1 số 
lẻ. Do đó sau khi ngƣời thứ hai thực hiện thì trên bảng còn lại một số chẵn. Cứ nhƣ thế 
thì sau khi ngƣời thứ hai thực hiện thì số trên bảng không thể đạt đến 2011 và ngƣời thứ 
nhất chỉ viết vào số n+1 nên số đó không thể quá 2011 và nhƣ vậy ngƣời thứ nhất luôn 
chiến thắng. 
Ví dụ 8: Hai người cùng chơi trò chơi tô màu lên một bảng hình chữ nhật m×n. Đánh 
số các cột là từ 1 đến m và các hàng là từ 1 đến n. Hai người cùng lần lượt thay phiên 
tô màu các ô sao cho đến lượt tô của một người thì họ không được tô ô cùng hàng,cùng 
cột hoặc cùng đường chéo với ô người kia đã tô liền trước đó . Hai người chỉ dùng 
đúng 2 màu là trắng và đen. Giả sử rằng họ luôn có thể tô kín bảng.Nếu sau khi tô, tồn 
tại một hình vuống 2×2 thuộc hình chữ nhật có số ô trắng là lẻ thì người thứ nhất 
thắng. Hỏi người thứ hai có ngăn người thứ nhất thắng được không? 
Giải: 
Trong ví dụ này thì ngƣời thứ nhất luôn thắng. Chú ý là nếu ngƣời thứ nhất lần đầu tô 
(1;1) thì ngƣời thứ nhất sẽ đƣợc tô cả 4 ô ở đỉnh hỉnh chữ nhật. Và một điều thật thú vị 
là chỉ dựa vào 4 ô đỉnh thì ngƣời thứ nhất có thể thắng mà không cần quan tâm đến 
cách tô các ô khác. Thật vậy nếu nhƣ ngƣời thứ nhất tô 4 ô ở đỉnh trong đó có 3 ô màu 
trắng một ô màu đen thì luôn tồn tại một hình vuông thỏa mãn đề bài. 
Ý tƣởng rõ ràng là ta sẽ phản chứng giả sử tất cả các ô 2x2 đều có số chẵn ô màu trắng. 
Đánh số các cột là 1 đến m và các hàng là 1 đến n. 
Xét 2 ô (1;i) (tức hàng 1 cột i) và ô (1;i+1) thì tổng số ô trắng của 2 ô này với 2 ô (2;i) 
và (2;i+1) là số chẵn, ô (2;i)+(2;i+1)+(3;i)+(3;i+1) cũng là số chẵn nên suy ra 
(1;i)+(1;i+1)+(3;i)+(3;i+1) là số chẵn và cứ nhƣ thế thì ta suy ra 
(1;i)+(1;i+1)+(n;i)+(n;i+1) là số chẵn. 
Xét 2 đỉnh màu trắng cùng nằm trên 1 cột thì 2 ô này vs 2 ô bên cạnh của mỗi ô này có 
tổng ô trắng là số chẵn suy ra 2 ô cạnh mỗi ô này cùng màu, tiếp tục nhƣ thế 2 ô cạnh 2 
ô đó lại cùng màu,... dẫn đến 2 ô cuối cùng của 2 hàng cùng màu, điều này vô lí vì 2 ô 
đó là 1 trắng 1 đen. 
C h u y ê n đ ề : T o á n L o g i c & R ờ i r ạ c | 57 
Bài toán trên rất thú vị ở chỗ nó không cần một quá trình nhất định mang tính bất biến 
nhƣ những bài toán trên mà chỉ cần quan tâm đến một vài vị trí đặc biệt quyết định. 
Trên thực tế nếu suy nghĩ tìm một lời giải cho cách tô ngay từ giả thiết là một điều rất 
khó!! 
C h u y ê n đ ề : T o á n L o g i c & R ờ i r ạ c | 58 
Problem 7: Giới thiệu sơ lƣợc định lí Ramsey-số Ramsey 
“ Thượng đế tạo ra số tự nhiên, còn tất cả các loại số khác đều là 
công trình sáng tạo của con người” 
Như đã nói ở ví dụ 1 trong phần này ta sẽ tổng quát nó 
Trong phần này với kiến thức lớp 10 ta chỉ thể hiện bằng ngôn ngữ quen thuộc và chỉ 
sơ lược một vài trường hợp của định lí:(ta sẽ thể hiện bằng ngôn ngữ “quen nhau”) 
số người nhỏ nhất sao cho trong số chừng ấy người bất kỳ, tồn tại m người đôi một 
quen nhau hoặc n người đôi một không quen nhau”. 
“Chừng ấy người đó chính là R(m,n)-số Ramsey 
Và ta có tính chất của số Ramsey nhƣ sau: 
Hệ quả: 
 , 1, , 1R m n R m n R m n 
1
2
2
,
1
m
m n
m n
R m n C
m
và , ( , )R m n R n m 
Các đẳng đƣợc chứng minh qua một số trƣờng hợp trong bảng sau: 
m,
n 
1 2 3 4 5 6 7 8 9 10 
1 1 1 1 1 1 1 1 1 1 1 
2 1 2 3 4 5 6 7 8 9 10 
3 1 3 6 9 14 18 23 28 36 40–43 
4 1 4 9 18 25 35–41 49–61 56–84 73–115 92–149 
5 1 5 14 25 43–49 58–87 80–143 101–216 125–316 143–442 
6 1 6 18 35–41 58–87 102–165 113–298 127–495 169–780 179–1171 
7 1 7 23 49–61 80–143 113–298 205–540 216–1031 233–1713 289–2826 
8 1 8 28 56–84 101–216 127–495 216–1031 282–1870 317–3583 317-6090 
9 1 9 36 73–115 125–316 169–780 233–1713 317–3583 565–6588 580–12677 
10 1 10 40–43 92–149 143–442 179–1171 289–2826 317-6090 580–12677 798–23556 
C h u y ê n đ ề : T o á n L o g i c & R ờ i r ạ c | 59 
Định lí Ramsey đã được chứng minh từ lâu nhưng hiện nay người ta vẫn chưa xác 
định được số R(m,n) bất kì và theo ngôn ngữ toán học thì không phải như thế này mà 
dùng khái niệm tô 2 màu, mà nó còn mở rộng cho bộ R(m,n,r) nhưng với kiến thức chúng 
ta hiện tại để dễ hiểu ta nên đưa về ngôn ngữ như trên. 
Các bài toán về một số trường hợp của định lí Ramsey ở các bài như ví dụ 1 , bài 
1.4 , 
Với tư tưởng của những bài đó bằng cách dùng đồ thi các bạn hãy giải với các số 
R(4,4) ; R(4;5) 
 Và để kết thúc bài viết xin dành tặng bạn đọc một số bài tập tổng hợp sau: 
C h u y ê n đ ề : T o á n L o g i c & R ờ i r ạ c | 60 
Một số bài tập tổng hợp 
Bài 1: Cho đa giác n cạnh trên mặt phẳng tọa độ với các đỉnh nguyên và độ dài các cạnh 
nguyên. Chứng minh chu vi đa giác là một số chẵn. 
Bài 2: (Olympic 30/4 2010 lớp 10) Trong một môn thi đấu thể thao có x tấm HCV đƣợc phát 
trong n ngày. Ngày thứ nhất ngƣời ta phát 1 HCV và 
1
10
 số HC còn lại. Ngày thứ hai, ngƣời 
ta phát 2 tấm HC và 
1
10
số HC còn lại. Tƣơng tự, ngày thứ k ngƣời ta phát k tấm HC với 
3 k n . Vào ngày cuối cùng, còn đúng n $n$ tấm HC để phát. Hỏi môn thể thao đó có bao 
nhiêu tấm HC và đƣợc phát trong bao nhiêu ngày? 
Bài 3: Cho hình (T) nhƣ sau: 
Hỏi có thể phủ kín một hình vuông 10x10 bởi các hình này không? 
Bài 4: Trên mặt phẳng có n điểm (n>3) mà không có bất cứ 3 điểm nào thẳng hàng và không 
có 4 điểm nào cùng nằm trên một đƣờng tròn. Chứng minh tồn tại một đƣờng tròn đi qua 3 
điểm trong n điểm đó mà chứa bất kì điểm nào trong các điểm còn lại? 
 Bài 5: Trên mỗi ô của bảng kẻ ô vuông 8x8 có ghi một số , số này là tích của chỉ số hàng và 
chỉ số cột của ô ấy. Lấy ra 8 ô bất kì và trong 8 ô ấy không có 2 ô nào cùng nằm trong cùng 
một hàng hoặc nằm trong cùng một cột . Chứng minh rằng tích của các số nằm trong các ô 
này là không đổi 
Bài 6:Cho một bộ số lƣợng 2k các số +1 và -1. Từ đó ta nhận đƣợc bộ số mới bằng cách : 
Mỗi số nhân với số tiếp theo , số cuối cùng nhân với số đầu tiên. Với bộ số mới lặp lại thao 
tác trên liên tục. Chứng minh rằng cuối cùng ta có nhận đƣợc chỉ có số +1 đƣợc không? 
Bài 7: Cho một số điểm màu đỏ và màu xanh . Một số trong chúng nối với nhau thành một 
đọa thẳng. Ta nói rằng một điểm gọi là đặc biệt nếu hơn một nửa các điểm còn lại nối với nó 
và có màu khác với màu của nó .Nếu tồn tại điểm đặc biệt ta chọn điểm đặc biệt này và tô lên 
nó một màu khác . Chứng minh sau một hữu hạn bƣớc không còn một điểm đặc biệt nào 
Bài 8: Trên mặt phẳng cho N điểm , từ chúng có thể nối với nhau thành những đoạn thẳng. 
Biết từ 1 điểm bất kì không xuất phát quá 11 đoạn thẳng. Chứng minh những điểm này có thể 
tô bằng 4 màu sao cho những đoạn thẳng có 2 đầu mút cùng màu không vƣợt quá N 
Bài 9: Cho n ( n ≥ 2) học sinh đứng thành một hàng dọc để tập thể dục. sau mỗi lần thầy giáo 
thổi còi có 2 học sinh đổi chỗ cho nhau. Hỏi sau một số lẻ lần thầy giáo thổi còi các học sinh 
có trở lại trạng thái ban đầu không? 
C h u y ê n đ ề : T o á n L o g i c & R ờ i r ạ c | 61 
Bài 10: (Nam Tƣ, 75) Trong một hội nghị nọ cứ 2 ngƣời quen nhau bất kì thì không có ngƣời 
quen chung , còn có 2 ngƣời không quen nhau nhau bất kì thì có đúng 2 ngƣời quen chung. 
Chứng minh rằng trong hội này, tất cả mọi ngƣời đều có số ngƣời quen chung 
Bài 11: (Bungari,79) Trên một tờ giấy kẻ ô vuông đánh dấu n ô. Chứng minh rằng từ chúng 
luôn có thể nhận đƣợc không ít hơn 
4
n
 ô vuông đôi một không tiếp xúc với nhau ( ô vuông 
đƣợc coi là tiếp xúc với nhau nếu có ít nhất 1 đỉnh chung) 
Bài 12: (Nam từ , 74) Trên một bàn cờ kích thƣớc 8 × 8 có 8 quân cờ trắng đứng trên hàng 
ngang thứ nhất và 8 quân cờ đen nằm trên hàng ngang thứ tám. Các đấu thủ lần lƣợt đi ( trắng 
đi trƣớc) bằng cách di chuyển một quân cờ theo hàng dọc một hoặc vài ô về phía trƣớc hay 
phía sau. Không đƣợc phép bỏ quân ra khỏi bàn, hay đi vào ô đã có quân của đối phƣơng 
đứng , hoặc nhảy qua nó. Ngƣời thua cuộc là ngƣời không có nƣớc đi nào nữa 
Bài 13 Một tấm bảng ô vuông vô hạn và có các quân cờ đứng thành hàng tạo thành hình chữ 
nhật 3k × n. Có một trò chơi theo các nguyên tắc sau: mỗi quân cờ có thể nhay qua quân cờ 
bất kì bên cạnh mình ( theo chiều dọc hoặc chiều ngang ) vào ô trống , sau đó quân cờ bị 
nhảy qua ta lấy ra khỏi bàn cờ. Chứng minh rằng trên bảng không bao giờ còn lại đúng một 
quân cờ 
Bài 14: Cho trƣớc một đa diện lồi với n ≥ 5 mặt, mà từ mỗi đỉnh của no có đúng 3 cạnh. Hai 
ngƣời chơi một trò chơi nhƣ sau: Mỗi ngƣời lần lƣợt viết tên mình lên một từ các mặt còn 
trống. Để thắng ngƣời chơi cần viết tên mình lên 3 mặt có cùng đỉnh chung. Chứng minh rằng 
tồn tại một cách chơi mà ngƣời thứ nhất luôn thắng 
Bài 15* : Số lơn nhất các con xe có thể đặt trên các bàn cờ 3n × 3n có thể là bao nhiêu để sao 
cho mỗi con xe chỉ bị ăn không nhiều hơn một trong các con xe còn lại 
Bài 16: Trong một thành phố “ Hữu Nghị” có tất cả 10.000 công dân . Cứ bất kì 2 ngƣời dân 
thì hoặc là bạn của nhau, hoặc là kẻ thù của nhau. Hằng ngày không nhiều hơn 1 ngƣời cãi 
nhau với các bạn của mình và làm lành với kẻ thù của mình . Mặt khác 3 ngƣời dân nào cũng 
có thể làm bạn với nhau. Chứng minh rằng sau một số ngày nào đó tất cả mọi ngƣời sẽ là bạn 
của nhau . Hỏi số ngày ít nhất cần phải có là bao nhiêu ? 
Bài 17: ( HSG lớp 9- Vĩnh Phúc ,2010) Mỗi ô vuông đơn vị của bảng kích thƣớc 10x10 (10 
dòng, 10 cột) đƣợc ghi một số nguyên dƣơng không vƣợt quá 10 sao cho bất kì hai số nào ghi 
trong hai ô chung một cạnh hoặc hai ô chung một đỉnh của bảng là hai số nguyên tố cùng 
nhau. Chứng minh rằng có số đƣợc ghi ít nhất 17 lần. 
Bài 18: CMR: 2n luôn tồn tại 1 tập hợp gồm n số nguyên dƣơng sao cho tổng 2 số bất kì 
chia hết hiệu của chúng. 
Bài 19: Chứng minh rằng với bất kì cách chia tập {1,2,3,...,3n} thành 3 lớp 3 phần tử, chúng 
ta luôn chọn đƣợc từ mỗi lớp 1 số sao cho 1 trong 3 số chọn ra là tổng 2 số còn lại. 
Bài 20: Giả sử có 1 cách chia các số 1,2,3,.., 100 thành 7 lớp . CMR: Tồn tại 1 vài lớp mà 
trong mỗi lớp có 4 số phân biệt a,b,c,d mà a b c d hoặc 3 số phân biệt , ,e f g sao cho 
2e f g 
C h u y ê n đ ề : T o á n L o g i c & R ờ i r ạ c | 62 
Bài 21: Trong một cuộc lấy ý kiến về 7 vấn đề, ngƣời đƣợc hỏi ghi vào một phiếu trả lời sẵn 
bằng cách để nguyên hoặc phủ định các câu trả lời tƣơng ứng với 7 vấn đề đã nêu.Chứng 
minh rằng với 1153 ngƣời đƣợc hỏi luôn tìm đƣợc 10 ngƣời trả lời giống hệt nhau. 
Bài 22: Cho 36 số nguyên, trong đó tích của 5 số bất kỳ trong các số đó là một số nguyên âm. 
Chứng tỏ rằng tích của 36 số đã cho là một số nguyên dƣơng 
Bài 23: (VMO-2010) Cho bảng 3×3 , n là một số nguyên dƣơng cho trƣớc, tìm số cách tô màu 
không nhƣ nhau khi tô mỗi ô bởi 1 trong n màu 
Hai cách tô đƣợc gọi là nhƣ nhau nếu mỗi 1 cách nhận đƣợc từ cách kia bằng phép quay tâm 
Bài 24: Ngƣời ta dùng 4 màu để tô tất cả các đỉnh của một thất giác đều sao cho mỗi đỉnh 
đƣợc tô bởi một màu và hai đỉnh kề nhau đƣợc tô bằng 2 màu khác nhau. Hai cách tô thỏa 
mãn các điều kiện trên đƣợc gọi là nhƣ nhau nếu cách tô màu này có thể nhận đƣợc từ cách tô 
màu kia qua phép quay tâm của thất giác. Hỏi có bao nhiêu cách quay đôi một không nhƣ 
nhau? 
Bài 25: Cho 12 đa giác đều. Tại 12A , ngƣời ta ghi một dấu " " , còn ở tất cả các đỉnh còn lại, 
ở mỗi đỉnh ngƣời ta ghi một dấu " " . Cho phép thay đổi các dấu theo quy tắc sau: Mỗi lần lấy 
3 dấu của một ta giác cân, không cân rồi thay mỗi dấu bằng dấu ngƣợc lại. Hỏi nhờ việc thực 
hiện liên tiếp một số hữu hạn lần phép thay dấu nói trên đối với đa giác ban đầu, ta có thể 
nhận đƣợc đa giác 1 2 12...A A A mà tại đỉnh 1A ghi dấu " " , còn tất cả các đỉnh khác ghi dấu " " 
C h u y ê n đ ề : T o á n L o g i c & R ờ i r ạ c | 63 
Tài liệu tham khảo: 
 w.w.w.diendantoanhoc.net 
 w.w.w.mathscope.org 
 Lí thuyết tổ hợp ( Ngô Thế Phiệt) 
 Tuyển tập các bài toán từ những cuộc thi tại Trung Quốc 
 Các đề thi vô địch Toán 19 nước ( trong đó có Việt Nam) 
 Vietnamese IMO Team Training camp 2010 ( Trần Nam Dũng) 
 Nguyên lí Dirichlet và ứng dụng ( Tài liệu Mathscope) 
 Đơn biến, bất biến và ứng dụng ( Trần Nam Dũng)