Chuyên đề Toán logic và rời rạc

 đ ề : 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)