Kiến Thức Cho Người lao Động Việt Nam > Chia Sẻ Kiến Thức > Bài tập chuyên đề nguyên lý Dirichlet

Bài tập chuyên đề nguyên lý Dirichlet

Nguyên lý Dirichlet do nhà Toán học người Đức đưa ra được áp dụng phổ biến trong nhiều bài toán thi học sinh giỏi từ lớp 1 đến lớp 12. Trong bài viết này hệ thống giáo dục onthihsg sẽ hướng dẫn cách giải bài toán nguyên lý Dirichlet. Kính mời quý phụ huynh, thầy cô và các em học sinh cùng tham khảo chuyên đề dirichlet dưới đây nhé.

Video bài tập về nguyên lý dirichlet

Tổng quan về chuyên đề dirichlet

I. Nguyên lí Dirichlet .

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 [Nk]Nk đồ vật. (Ở đây [x]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−1m]n+m-1m 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.

Bài tập chuyên đề nguyên lý Dirichlet

II. 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 

Bài tập về nguyên lý dirichlet

Ví dụ 1. Chứng minh rằng trong 11 số chính phương có hai số mà hiệu của chúng chia hết cho 20.

Lời giải ab a = mét vuông, b = n2a − b = mét vuông − n2m, nm2 − n2 = ( m − n ) ( m + n ) a − b = mét vuông − n2

Ví dụ 2. Với 4 số nguyên a,b,c,da,b,c,d.

Chứng minh rằng ( a − b ) ( a − c ) ( a − d ) ( b − c ) ( b − d ) ( c − d ) ( a − b ) ( a − c ) ( a − d ) ( b − c ) ( b − d ) ( c − d ) chia hết cho 12 Lời giải A = ( a − b ) ( a − c ) ( a − d ) ( b − c ) ( b − d ) ( c − d ) A

Ví dụ 3. Chứng minh rằng
a) rong 5 số nguyên thì có 3 số có tổng chia hết cho 3.
b) Trong 17 số nguyên thì có 9 số có tổng chia hết cho 9.

Lời giải

a1, a2, ⋯, a16, a17 a1, ⋯, a53a1, a2, a3 13 b1 = 13 ( a1 + a2 + a3 ) a4, a5, ⋯, a8a4, a5, a6 13 b2 = 13 ( a4 + a5 + a6 ) a13, a14, ⋯ a17a14, a15, a16 13 b5 = 13 ( a14 + a15 + a16 ) b1, b2, ⋯, b5b1, b2, b3b1 + b2 + b3 a1 + a2 + ⋯ + a8 + a9

Ví dụ 4. Chứng minh rằng trong 100 số phân biệt, luôn có một số hoặc một tổng vài số chia hết cho 100.

Lời giải S1 = a1 S2 = a2 S100 = a1 + a2 + ⋯ + a100 S1, S2, ⋯, S100 i > jSi – Sjaj + 1 + ⋯ + ai

Bài tập rèn luyện chuyên đề nguyên lý dirichlet

Bài 1. Chứng minh rằng tồn tại các số chỉ toàn chữ số 1 và chia hết cho 2019.

Bài 2. Chứng minh rằng mỗi tập con có n+1n+1 phần tử của tập 1,2,⋯,2n1,2,⋯,2n có hai số mà số này chia hết cho số kia.

Các dạng bài tập nguyên lý dirichlet

Bài viết liên quan
Bài Mới Nhất