Giáo trình Toán logic và rời rạc
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.
Tóm tắt nội dung tài liệu: 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)
File đính kèm:
- giao_trinh_toan_logic_va_roi_rac.pdf