Tài liệu Nguyên lý Dirichle và nguyên lý cực hạn

Nguyên lý Dirichle và nguyên lý cực hạn là hai nguyên lý có nội dung khá đơn

giản, song lại có thể áp dụng rộng rãi trong việc chứng minh các bài toán hình học tổ hợp,

số học, đại số, . Bài viết này sẽ giới thiệu một cách tổng quan về hai nguyên lý này.

A.Nguyên lý Dirichle

I.Giới thiệu:

-Dạng 1: Nếu có một ánh xạ từ tập hợp M có n+1 phần tử vào tập hợp có n phần tử

thì có ít nhất 2 phần tử của tập hợp M có cùng một ảnh của tập hợp N qua ánh xạ đó.

-Dạng 2: Nếu nhốt N chú thỏ vào n chuồng mà N>nk thì có ít nhất một chuồng nhốt

nhiều hơn hai chú thỏ.

Mở rộng: nếu chia tập hợp vô hạn các “chú thỏ” vào hữu hạn “chuồng” thì tồn tại ít

nhất một chuồng có vô hạn “chú thỏ”.

II. Ví dụ:

Các bài toán trong phần này sẽ giúp bạn đọc làm quen với cách áp dụng nguyên lý

này.

Bài toán 1: Cho bảng vuông gồm n x n ô vuông. Mỗi ô vuông ghi một trong các số

0,1,2. CM: không tồn tại bảng vuông nào mà tổng các ô trên hàng ngang, cột dọc và

đường chéo là các số khác nhau hoàn toàn.

Giải:

Giá trị trên cột, hàng, đường chéo có giá trị nhỏ nhất là 0 x n=0 và có giá trị lớn

nhất là 2n, mà ta có 2n+2 tổng nhưng chỉ có 2n+1 giá trị (từ 0 đến 2n) nên theo nguyên lý

Dirichle phải có ít nhất 2 tổng có giá trị bằng nhau => đpcm