#027 Toán Rời Rạc Phương Pháp Đếm Nguyên Lý Dirichlet Toán Rời Rạc

thuydunga9tx

Trung sĩ

*

Thành viên

*

190 Bài viết Giới tính: Nữ Đến từ: CQT-IK15 Sở thích: Ngủ

Đang xem: Nguyên lý dirichlet toán rời rạc

Nguồn: toan.hoctainha

 

I.                   NGUYÊN LÝ DIRICHLET
Nguyên lí Dirichlet:

Không thể nhốt $7$ chú thỏ vào $3$ cái lồng sao cho mỗi lồng không quá $2$ chú thỏ. 

Nguyên lí Dirichlet tổng quát
Nếu đặt $n$ viên bi vào $k$ cái hộp ($n,k$ nguyên dương), thì sẽ tồn tại một hộp chứa ít nhất $ leftlceil frac
ight
ceil$ viên bi, với  $ leftlceil x
ight
ceil$ là số nguyên bé nhất không nhỏ hơn $x$ . 
 

Nguyên lí Dirichlet (còn gọi là nguyên lí chuồng bồ câu) tuy có phát biểu đơn giản nhưng lại được vận dụng rất nhiều trong thực tế. Nhờ nguyên lí này mà trong nhiều tr ường hợp ,  người ta dễ dàng chứng minh được sự tồn tại mà không đưa ra được phương pháp t ìm kiếm cụ thể.

 

II.                BÀI TẬP CĂN BẢN

Bài 1:

Một trường học có $1000$ học sinh gồm $23$ lớp. Chứng minh rằng phải có ít nhất một lớp có từ $44$ học sinh trở lên

Giải:  
Giả sử $23$ lớp mỗi lớp có không quá $43$ học sinh. 
Khi đó số học sinh là: 
$43.23 = 989$ học sinh (ít hơn $1000 – 989 = 11$ học sinh) 
Theo nguyên lí Dirichlet phải có ít nhất một lớp có từ $44$ học sinh trở lên
 

Bài 2:

Một lớp có $50$ học sinh. Chứng minh rằng có ít nhất $5$ học sinh có tháng sinh giống nhau 

Giải:  
Giả sử có không quá $4$ học sinh có tháng sinh giống nhau 
Một năm có $12$ tháng, khi đó số học sinh của lớp có không quá: $12 . 4 = 48$ (học sinh)
Theo nguyên lí Dirichlet phải có ít nhất $5$ học sinh có tháng sinh giống nhau

 

Bài 3:

Có năm loại học bổng khác nhau. Hỏi rằng phải có ít nhất bao nhiêu sinh viên để chắc chắn rằng có ít ra là $6$ ng ười cùng nhận học bổng như nhau.

Giải:

Gọi $N$ là số sinh viên, khi đó:
$ leftlceil frac
ight
ceil =6 Rightarrow 5 < frac≤ 6$ hay  $25 < N ≤ 30$.
Vậy số N bé nhất thỏa mãn là $26$. 
 

Bài 4:

Trong $45$ học sinh làm bài kiểm tra, không có ai bị điểm dưới $2$, chỉ có $2$ học sinh được điểm $10$. Chứng minh rằng ít nhất cũng tìm được $6$ học sinh có điểm kiểm tra bằng nhau (điểm kiểm tra là một số tự nhiên) 

Giải
Có $43$ học sinh phân thành $8$ loại điểm (từ $2$ đến $9$) 
Giả sử trong $8$ loại điểm đều là điểm của không quá $5$ học sinh thì lớp học có:
$5 . 8 = 40$ học sinh, ít hơn $3$ học sinh so với $43$.
Theo nguyên lý Dirichlet tồn tại $6$ học sinh có điểm kiểm tra bằng nhau.

 

Bài 5 :

Một lớp học có $50$ học sinh, có duy nhất một học sinh thiếu nhiều bài tập nhất là thiếu $3$ bài tập. Chứng minh rằng tồn tại $17$ học sinh thiếu $1$ số bài tập như nhau (trường hợp không thiếu bài tập coi như thiếu $0$ bài) 

Giải
Giả sử mỗi loại bài tập có $16$ học sinh. 
Số học sinh không quá $16 × 3 = 48$ (thiếu $2$ học sinh). 
Theo nguyên lí Dirichlet có ít nhất $17$ học sinh thiếu một số bài tập như nhau 
 

III.             BÀI TẬP NÂNG CAO 

Bài 1:

Trong một phòng họp có $n$ ng ười, bao giờ cũng t ìm được $2$ người có số người quen trong số những người dự họp là nh ư nhau.

Giải:

Số người quen của mỗi người trong ph òng họp nhận các giá trị từ $0$ đến $n – 1$. Rõ ràng trong phòng không thể đồng thời có người có số người quen là $0$ (tức là không quen ai) và có ng ười có số người quen là  $n – 1$  (tức là quen tất cả). V ì vậy theo số l ượng người quen, ta chỉ có thể phân n người ra thành  $n – 1$  nhóm.

Vậy theo nguyên lí Dirichlet tồn tai một nhóm có ít nhất  $2$  người, tức là luôn t ìm được ít nhất $2$ người có số người quen là nh ư nhau.

 

Bài 2:

Trong một lưới ô vuông kích thước $5.5$, người ta điền ngẫu nhiên vào các ô một trong các giá trị $-1, 0$ hoặc $1$, sau đó tính tổng tất cả các ô theo hàng ; theo cột và theo hai đường chéo. Chứng minh rằng tồn tại ít nhất hai tổng có giá trị bằng nhau.

Giải:

Gọi các tổng lần lượt là $S_1, S_2,..S_$.
Có tất cả $12$ tổng. Ta nhận thấy rằng các tổng này chỉ có thể nhận các giá trị là $$.

Xem thêm: mẫu giấy 4 ô ly chuẩn violet

Xem thêm: Mẫu Báo Cáo An Ninh Trật Tự 2019, Báo Cáo Trường Học An Toàn Về An Ninh Trật Tự

Có tất cả $11$ giá trị khác nhau. Từ đó, theo nguyên lý Dirichlet ta suy ra điều cần chứng minh. 

 

Bài 3:

Giả sử trong một nhóm $6$ người mỗi cặp hai hoặc là bạn hoặc là thù. Chứng tỏ rằng trong nhóm có ba người là bạn lẫn nhau hoặc có ba người là kẻ thù lẫn nhau.

Giải:

Gọi $A$ là một trong $6$ người. Trong số $5$ người của nhóm hoặc là có ít nhất ba người là bạn của $A$ hoặc có ít nhất ba người là kẻ thù của $A$, điều này suy ra từ nguyên lí Dirichlet, vì những người khác chỉ có thể là bạn hoặc thù của $A$.
Trong trường hợp đầu ta gọi $B, C, D$ là bạn của $A$. nếu trong ba người này có hai người là bạn thì họ cùng với $A$ lập thành một bộ ba người bạn lẫn nhau, ngược lại, tức là nếu trong ba người $B, C, D$ không có ai là bạn ai cả thì chứng tỏ họ là bộ ba người thù lẫn nhau.
Tương tự có thể chứng minh trong trường hợp có ít nhất ba người là kẻ thù của $A$. (ĐPCM)

 

Bài 4:

Có $5$ đấu thủ thi đấu cờ, mỗi người đấu một trận với mỗi đấu thủ khác. Chứng minh rằng trong suốt thời gian thi đấu, luôn tồn tại hai đấu thủ có số trận đã đấu bằng nhau.

Giải:

Ta có số trận đã đấu của mỗi người có thể là $0, 1, 2, 3,4$. Nh ưng v ì không thể có cùng lúc một ng ười đ ã đấu $4$ trận và một ng ười chưa đấu trận nào , nên  có tối đa  $4$  loại số trận đ ã đấu.

Vận dụng nguyên lý Dirichlet ta có ít nhất có $2$ ng ười có cùng số trận đ ã đấu.

 

IV.             BÀI TẬP TỰ GIẢI 

Bài 1:

Chia $50$ kẹo cho $10$ em bé (em nào cũng được chia kẹo). Chứng minh rằng dù chia cách nào đi nữa cũng tồn tại hai em có số kẹo bằng nhau. 

Bài 2:

Bốn lớp $11A, 11B, 11C, 11D$ có tất cả $44$ học sinh giỏi, trong đó số học sinh giỏi của lớp $11D$ không quá $10$ người. Chứng minh rằng ít nhất một trong $3$ lớp $11A, 11B, 11C$ có số học sinh giỏi từ $12$ em trở lên.  

Bài 3:

Có $33$ con chim đậu trên một sân vuông hình vuông cạnh $4m$.

Chứng minh rằng có ít nhất $3$ con đậu trong một đường tròn có bán kính $1m$ 

Bài 4:

Một cuộc họp gồm $12$ người tham dự để bàn về $3$ vấn đề. Có $8$ người phát biểu về vấn đề $I$, $5$ người phát biểu về vấn đề $II$ và $7$ người phát biểu về vấn đề $III$. Ngoài ra, có đúng $1$ người không phát biểu vấn đề nào.

Hỏi nhiều nhất là có bao nhiêu người phát biểu cả $3$ vấn đề. 

Bài 5:

Có $17$ nhà bác học viết thư cho nhau trao đổi $3$ vấn đề. Chứng minh rằng luôn tìm được $3$ người cùng trao đổi một vấn đề.

Viết một bình luận