Ứng dụng nguyên lý Dirichle trong giải các bài toán Hình học tổ hợp

Thuvientoan.net xin gửi đến bạn đọc tài liệu Ứng dụng nguyên lý Dirichle trong giải các bài toán Hình học tổ hợp.

Trước khi đi vào một số phương pháp cơ bản để giải bài toán hình học tổ hợp, ta xét các khái niệm sau
+ Một hình F được gọi là lồi nếu với hai điểm A và B bất kì thuộc F, thì đoạn thẳng nối hai điểm A, B cũng thuộc F.

+ Khoảng cách lớn nhất giữa hai điểm bất kì trong một hình lồi là đường kính của hình lồi đó.

Người đầu tiên đề xuất nguyên lí này được cho là nhà toán học Đức Johann Đirichlê khi ông đề cập tới nguyên lí với tên gọi “nguyên lí ngăn kéo” (The Drawer Principle). Ngoài ra  nguyên lí này còn được biết đến như nguyên lí chim bồ câu (The Pigeonhole Principle) hoặc nguyên lí những cái lồng nhốt thỏ.
Nguyên lí này được Đirichlê phát biểu đầu tiên năm 1834.
“Nguyên lý Đirichlê ở dạng cổ điển thường được dùng để chứng minh tồn tại theo kiểu không xây dựng (non-constructive), tức là biết đối tượng tồn tại nhưng không chỉ ra cụ thể.” (Trích bài giảng Các phương pháp và kỹ thuật chứng minh, trình bày tại chương trình Gặp gỡ toán học 2010 do ĐHQG Tp.HCM tổ chức từ ngày 25/1 - 31/1/2010.)

Nguyên lí Đirichlê cơ bản
Nhốt n + 1 thỏ vào n lồng thì tồn tại một lồng có ít nhất hai thỏ.

Nguyên lí Đirichlê thường liên quan đến các bài toán thi đấu thể thao, chia hết, nguyên tố cùng nhau, đồ thị, tô màu, quen nhau và các bài toán hình học. Ở đây chỉ đưa ra một số bài toán cơ bản sau.

Tải tại đây.

THEO THUVIENTOAN.NET

Liên hệ
Tin liên quan
    2020 Copyright © THUVIENTOAN.NET Web Design by Nina.vn
    Online: 10   |   Total: 126380
    Hotline tư vấn miễn phí: 0907233487
    icon zalo

    Ứng dụng nguyên lý Dirichle trong giải các bài toán Hình học tổ hợp