Luận văn Thạc sĩ Khoa học: Một số bài toán hình học tổ hợp

Các bài toán hình học tổ hợp là các bài toán hay và được nhiều người quan tâm. Trong những đề thi học sinh giỏi quốc gia và quốc tế cũng thường xuyên xuất hiện những bài toán về hình học tổ hợp. Đó là lý do luận văn này trình bày một số bài toán về hình học tổ hợp.
Nội dung trích xuất từ tài liệu:
Luận văn Thạc sĩ Khoa học: Một số bài toán hình học tổ hợp ĐẠI HỌC QUỐC GIA HÀ NỘITRƢỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN _______________******______________ VŨ MINH HẢI MỘT SỐ BÀI TOÁN HÌNH HỌC TỔ HỢP LUẬN VĂN THẠC SĨ KHOA HỌC Hà nội - 2015 1 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN _______________******______________ VŨ MINH HẢI MỘT SỐ BÀI TOÁN HÌNH HỌC TỔ HỢPChuyên ngành: Phương pháp toán sơ cấp. Mã số: 60460113. LUẬN VĂN THẠC SĨ KHOA HỌC NGƢỜI HƢỚNG DẪN KHOA HỌC PGS.TS. LÊ ANH VINH Hà nội – 2015 2 MỤC LỤCCHƢƠNG 1. BÀI TOÁN PHỦ HÌNH .....................................................................5 1.1. Một số lý thuyết cơ sở ................................................................................................ 5 1.2. Một số bài toán phủ hình .......................................................................................... 6CHƢƠNG 2. BÀI TOÁN ĐỒ THỊ, TÔ MÀU ......................................................19 2.1. Lý thuyết cơ bản về bài toán tô màu ....................................................................... 19 2.2. Phương pháp tô màu giải bài toán hình học.......................................................... 20 2.2.1. Một số bài toán tô màu đồ thị ........................................................................ 20 2.2.2. Một số bài toán tô màu ô vuông ..................................................................... 37 2.2.3. Một số bài toán dùng phương pháp tô màu ô vuông và tính chất bất biến41CHƢƠNG 3. NGUYÊN LÝ CỰC HẠN ................................................................47 3.1. Nguyên lý cực hạn ................................................................................................... 47 3.2. Ứng dụng nguyên lý cực hạn .................................................................................. 47 3.2.1. Một số bài toán đánh giá góc.......................................................................... 47 3.2.2. Một số bài toán đánh giá khoảng cách, độ dài ............................................. 54 3.2.3. Một số bài toán đánh giá diện tích, thể tích .................................................. 63 1LỜI NÓI ĐẦU Các bài toán hình học tổ hợp là các bài toán hay và được nhiều người quantâm. Trong những đề thi học sinh giỏi quốc gia và quốc tế cũng thường xuyênxuất hiện những bài toán về hình học tổ hợp. Đó là lý do luận văn này trìnhbày một số bài toán về hình học tổ hợp. Luận văn “Một số bài toán hình học tổ hợp” được chia làm 3 chương: Chương 1. Trình bày một số lý thuyết về bài toán phủ hình và cách giảinhững bài toán dạng đó. Chương 2. Trình bày về các bài toán đồ thị, tô màu và một số bài toánthuộc dạng này được sử dụng trong các kì thi học sinh giỏi trong nước vàquốc tế. Chương 3. Trình bày về nguyên lý cực hạn và các bài toán hình học tổhợp sử dụng nguyên lí cực hạn. Mục đích của luận văn là trình bày ngắn họn dễ hiểu lý thuyết về các bàitoán : phủ hình, đồ thị, tô màu, bài toán sử dụng nguyên lý cực hạn và trìnhbày chi tiết cách giải các bài toán đó. Mặc dù có nhiều cố gắng trong việc nghiên cứu và thực hiện luận văn nàynhưng không thể tránh khỏi có sai sót, kính mong được sự góp ý quý báu củacác thầy, cô và các bạn. Tôi xin chân thành cảm ơn. 4 CHƢƠNG 1. BÀI TOÁN PHỦ HÌNH Bài toán phủ hình là một dạng bài toán có nhiều trong thực tế. Ví dụ như làviệc lát vỉa hè, quảng trường, sàn nhà, ... bằng những viên gạch đa giác giốngnhau. Câu hỏi được đặt ra ở đây là “Những viên gạch đa giác lồi giống nhau nhưthế nào thì có thể lát kín được mặt phẳng?”. Mặt phẳng được lấp đầy bởinhững đa giác giống nhau sao cho hai đa giác tuỳ ý không có điểm chung,nhưng có thể có chung cạnh chung đỉnh. Từ câu hỏi trên có một số các dạng toán được sinh ra, đó là “Phủ hìnhbằng mạng lưới ô vuông”, “Phủ đa giác lồi bằng những đa giác vị tự (hoặcđồng dạng) với chính nó”, ... Dưới đây luận văn sẽ trình bày một số định lí, hệ quả và những bài toáncho dạng bài toán phủ hình như thế. 1.1. Một số lý thuyết cơ sở Một hệ thống vô hạn ô vuông tạo nên mặt phẳng được gọi là mạng lướiđỉnh ô vuông. Các ô vuông đó được gọi là ô vuông cơ sở. Các đỉnh ô vuông làcác điểm nguyên (điểm có cả tung độ và hoành độ là các số nguyên) của mộthệ trục toạ độ song song với các cạnh hình vuông cơ sở và có đơn vị gốc là độdài cạnh hình vuông cơ sở. Một đa giác có đỉnh là các đỉnh lưới của mạng ôvuông được gọi là đa giác nguyên. Ta có một tính chất cơ bản của mạng lưới ô vuông là định lí sau Định lí 1. Đ ...