chuyên đề toán logic và rời rạc

chuyên đề toán logic và rời rạc đề 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.
Nội dung trích xuất từ tài liệu:
chuyên đề toán logic và rời rạcChuyên đề:Toán Logic& Rời rạc|1Lê Trần Nhạc Long ( Chủ Biên) – Trần Nguyễn Quốc CườngChuyªn ®ÒTo¸n logicvµ rêi r¹cĐà Nẵng 1/2011⎈⪸⪷Chuyên đề:Toán Logic& Rời rạc|2Lêi nãi ®ÇuThượng đế có tất cả những lời giải ngắn nhấtvà 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 sinhchú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àitoá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ũngyê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ạnyê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ứccò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ọcngoạ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: winwave1995Lê Trần Nhạc LongChuyên đề:Toán Logic& Rời rạc|3MỤC LỤCLời nói đầu……………………………………………………………………………..2Problem 1:Các bài toán giải bằng đồ thịLê Trần Nhạc Long………………………………………………………………………..……..4Problem 2:Các bài toán giải bằng tô màuLê Trần Nhạc Long………………………………………………………………………………………10Problem 3: Nguyên lí bất biến, đơn biến.Lê Trần Nhạc Long……………………………………………………………………………18Problem 4: Nguyên lí cực hạnTrần Nguyễn Quốc Cường…………………………………………………………..………26Problem 5: Nguyên lí Dirichlet và ứng dụngLê Trần Nhạc Long, Võ Quốc Bá Cẩn………………………………………………………41Problem 6:Các bài toán về trò chơiTrần Nguyễn Quốc Cường……………………………………………………………………53Problem 7:Giới thiệu về định lí Ramsey-số RamseyLê Trần Nhạc Long…………………………………………………………………………….58Một số bài tập tổng hợp………………………………………………………………..60Tài liệu tam khảo……………………………………………………………………….63Chuyên đề:Toán Logic& Rời rạc|4Problem 1: Lý thuyết đồ thị“Toán học và con người như hai đỉnh luôn nối với nhaubởi một đoạn thẳng”Lê Trần Nhạc LongTrường THPT chuyên Lê Quý Đôn –tp Đà NẵngLý 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ánkhô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étVà 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ểmthể hiện sự quen nhau và và các điểm nốinét đứt với nhau chỉ sự không quen nhauBây giờ ta xét 6 điểm O,A,B,C,D,E lấyO làm tâm ,Trong 5 điểm còn lại , ta thấy 2 ngườibất kì hoặc là quen nhau , hoặc là khôngquen nhau , trên hình theo nguyên líDirichlet thì tồn tại ít nhất 3 đườngthẳng nét liền từ O đến 5 điểmA,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ậtvậy nếu trong 3 điểm A,B,C mà nối lạivới nhau thì ta được 1 tam giác có đỉnhlà 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ặckhô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 BBâ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 đôimộ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 sauChuyên đề:Toán Logic& Rời rạc|5Ví 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ảiviế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ê ...