Tìm 2 bài toán sử dụng nguyên lí Diricle

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

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.

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 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à S1,S2,..S12.

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à {−5,−4…0,…4,5}. 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.