Đề cương ôn thi môn Toán Lớp 9 - Chuyên đề 18 Nguyên lí và áp dụng - Trần Kim Oanh

GIÁO VIÊN: TRẦN KIM OANH CHUYÊN ĐỀ: NGUYÊN LÍ VÀ ÁP DỤNG 1. Nguyên lí Dirichlet. 1.1. Nội dung Nguyên lí Dirichlet - còn gọi là nguyên lí chim bồ câu (The Pigeonhole Principle) hoặc nguyên lý những cái lồng nhốt thỏ hoặc nguyên lí sắp xếp đồ vật vào ngăn kéo (The Drawer Principle) - đưa ra một nguyên tắc về phân chia phần tử các lớp.

Nguyên lý Dirichlet cơ bản: Nếu nhốt  n 1 con thỏ vào n cái chuồng thì bao giờ cũng có một chuồng chứa ít nhất hai con thỏ.

Nguyên lý Dirichlet tổng quát: Nếu có N đồ vật được đặt vào trong k hộp thì sẽ tồn tại một hộp

chứa ít nhất      

N

k đồ vật. (Ở đây   x là số nguyên nhỏ nhất có giá trị nhỏ hơn hoặc bằng x)

Nguyên lí Dirichlet mở rộng: Nếu nhốt n con thỏ vào  m 2 cái chuồng thì tồn tại một chuồng

có ít nhất       

n m 1 m con thỏ.

Nguyên lí Dirichlet dạng tập hợp: Cho A và B là hai tập hợp khác rỗng có số phần tử hữu hạn, mà số lượng phần tử của A lớn hơn số lượng phần tử của B. Nếu với một quy tắc nào đó, mỗi phần tử của A cho tương ứng với một phần tử của B, thì tồn tại ít nhất hai phần tử khác nhau của A mà chúng tương ứng với một phần tử của B. 1.2. Phương pháp ứng dụng. Nguyên lí Dirichlet tưởng chừng như đơn giản như vậy, nhưng nó là một công cụ hết sức có hiệu quả dùng để chứng mình nhiều kết quả hết sức sâu sắc của toán học. Nguyên lí Dirichlet cũng được áp dụng cho các bài toán của hình học, điều đó được thể hiện qua hệ thống bài tập sau: Để sử dụng nguyên lý Dirichlet ta phải làm xuất hiện tình huống nhốt “thỏ” vào “chuồng” và thoả mãn các điều kiện: + Số ‘thỏ” phải nhiều hơn số chuồng. + “Thỏ” phải được nhốt hết vào các “chuồng”, nhưng không bắt buộc chuồng nào cũng phải có thỏ. Thường thì phương pháp Dirichlet được áp dụng kèm theo phương pháp phản chứng. Ngoài ra nó còn có thể áp dụng với các nguyên lý khác. 1.3. Một số ví dụ minh họa. Ví dụ 1. Cho bảng ô vuông kích thước 10.10 gồm 100 ô vuông đơn vị. Điền vào mỗi ô vuông của bảng này một số nguyên dương không vượt quá 10 sao cho hai số ở hai ô vuông chung cạnh hoặc chung đỉnh nguyên tố cùng nhau. Chứng minh rằng trong bảng ô vuông đã cho có một số xuất hiện ít nhất 17 lần.

Lời giải Xét hình vuông cạnh 2x2 , do hình vuông này có mỗi hình vuông nhỏ luôn chung cạnh hoặc chung đỉnh nên tồn tại nhiều nhất 1 số chẵn, nhiều nhất 1 số chia hết cho 3 do đó có ít nhất 2 số lẻ không chia hết cho 3. Bảng 10x10 được chia thành 25 hình vuông có cạnh 2x2 nên có ít nhất 50 số lẻ không chia hết cho 3. Từ 1 đến 0 có 3 số lẻ không chia hết cho 3 là 1, 5, 7. Áp dụng nguyên

lí Dirichlet ta được một trong ba số trên xuất hiện ít nhất       

50 1 17 3 lần

Ví dụ 2. Cho tập hợp    X 1; 2; 3;...; 2024 . Chứng minh rằng trong 90 số khác nhau bất kỳ

được lấy ra từ tập X luôn tồn tại hai số x và y sao cho  1 x y 2 .

Lời giải

Chia 2012 số 1; 2; 3;...; 2012 thành 44 đoạn gồm           1; 3 , 4; 8 ,..., 1936; 2012 .

Các đoạn trên có dạng tổng quát là          

2 2 k ; k 1 1 .

DeThi.edu.vn

GIÁO VIÊN: TRẦN KIM OANH Như vậy 90 số thuộc tập hợp X nằm trong 44 đoạn trên. Theo nguyên lí Dirichlet thì tồn tại ba số trong 90 số trên nằm trong cùng một đoạn. Không mất tính tổng quát ta giả sử hai số đó là x, y, z và

chúng nằm trong đoạn          

2 2 k ; k 1 1 .

Chia đoạn          

2 2 k ; k 1 1 thành hai đoạn là       

2 2 k ; k k và           

2 2 k k; k 1 1

Khi đó theo nguyên lí Dirichlet tồn tại hai số nằm trên cùng một đoạn. Giả sử hai số đó là x và y. Khi đó

 Nếu x và y nằm trên đoạn       

2 2 k ; k k thì ta được

            2 2 2 2 1 1 1 x y k k k k k k k k 4 2 2

 Nếu x và y nằm trên đoạn           

2 2 k k; k 1 1 thì ta được

   

 

               

2 2 2 2

2 2

k 1 1 k k k 1 x y k 1 1 k k 2k 2 k 1 1 k k

.

Từ đó ta có điều phải chứng minh.

Ví dụ 3. Cho A là tập hợp gồm 6 phần tử bất kỳ của tập hợp   0;1;2;...;14 . Chứng minh rằng tồn

tại hai tập hợp con 1 2 B ,B của tập …