Toán học - Chương học: Các phương pháp đếm và nguyên lý dirichlet

Nội dung text: Toán học - Chương học: Các phương pháp đếm và nguyên lý dirichlet

1. Chương II CÁC PHƯƠNG PHÁP ĐẾM VÀ NGUYÊN LÝ DIRICHLET 5/25/2021 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 1
2. III. SINH CÁC HOÁN VỊ VÀ TỔ HỢP 2 1. Sinh các hoán vị (Tổ 1) 2. Sinh các tổ hợp (tổ 2) 3. Nhị thức Newton (tổ 3) Đọc sách TL1 (tr ): Chuẩn bị nội dung, tuần sau mỗi tổ trình bày trong 5 phút. GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 5/25/2021
3. IV. NGUYÊN LÝ DIRICHLET nhà toán học người Đức, Peter Gustav Dirichlet (1805-1859) 1. Nguyên lý: Nếu có k+1 đồ vật (hoặc nhiều hơn) được đặt vào trong k hộp thì tồn tại một hộp có ít nhất hai đồ vật. 2. Nguyên lý Dirichlet tổng quát: Nếu có n đồ vật được đặt trong k hộp thì sẽ tồn tại một hộp chứa ít nhất ]n/k[ đồ vật. ] x [: Số nguyên nhỏ nhất có giá trị lớn hơn hoặc bằng x. 5/25/2021 GVC, ThS. Võ Minh Đức, CĐSP Đắk Lắk 5
4. IV. NGUYÊN LÝ DIRICHLET 3. Ví dụ: Chứng minh rằng trong 100 người có ít nhất 9 người sinh cùng một tháng. Giải: Xếp những người sinh cùng tháng vào một nhóm thì ta có tất cả 12 nhóm. Theo nguyên lý Dirichlet tồn tại một nhóm có ít nhất ]100/12[ = 9 (người). 5/25/2021 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 6
5. IV. NGUYÊN LÝ DIRICHLET 4. Một số ứng dụng của nguyên lý Dirichlet: VD1: 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. Tại sao? 5/25/2021 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 7
6. IV. NGUYÊN LÝ DIRICHLET Giải: Số người quen của mỗi người trong phòng họp nhận các gía trị từ 0 đến n-1. Trong phòng không thể đồng thời có người có số người quen là 0 và có người có số ngừơi quen là n-1. Vì vậy theo số lượng người quen ta có thể phân n người thành n -1 nhóm. Theo NL Dirichlet tồn tại một nhóm có ít nhất 2 người, nghĩa là luôn tìm được ít nhất 2 người có số người quen là như nhau. 5/25/2021 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 8
7. IV. NGUYÊN LÝ DIRICHLET VD2: Trong một tháng gồm 30 ngày, một đội bóng chuyền thi đấu mỗi ngày ít nhất một trận nhưng chơi tất cả không quá 45 trận. Chứng minh rằng tìm được một giai đoạn gồm một số ngày liên tục nào đó trong tháng sao cho giai đoạn đó đội chơi đúng 14 trận. 5/25/2021 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 9
8. IV. NGUYÊN LÝ DIRICHLET Giải: Gọi Aj là số trận mà đội bóng đó chơi từ đầu tháng đến ngày thứ j: 1<=A1<A2<A3< <A30<=45. Vậy: 15 <=A1+14<A2+14 <A3+14< <A30 +14 <= 59 60 số nguyên A1, A30, A1+14, ,A30+14 nằm giữa 1 và 59. Vì vậy theo Dirichlet có ít nhất hai trong số 60 số này phải bằng nhau. Nghĩa là: tồn tại i và j sao cho Ai = Aj+14 (j<i). Điều này có nghĩa là từ ngày thứ j+1 đến ngày i đội đã chơi đúng 14 trận 5/25/2021 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 10
9. IV. NGUYÊN LÝ DIRICHLET Bài tập: 1. Chứng tỏ rằng trong n+1 số nguyên dương không vượt quá 2n tồn tại ít nhất một số chia hết cho số khác. 2. Chứng minh rằng trong 11 số tự nhiên bất kì bao giờ cũng tồn tại ít nhất 2 số có hiệu chia hết cho 10. 3. Chứng minh rằng tồn tại số có dạng 19941994 199400 0 chia hết cho 1995. 4. Chứng minh rằng tồn tại số tự nhiên k sao cho (1999^k – 1) chia hết cho104 5/25/2021 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 11
10. V. HỆ THỨC TRUY HỒI Bài tập: 1. Chứng tỏ rằng trong n+1 số nguyên dương không vượt quá 2n tồn tại ít nhất một số chia hết cho số khác. 2. Chứng minh rằng trong 11 số tự nhiên bất kì bao giờ cũng tồn tại ít nhất 2 số có hiệu chia hết cho 10. 3. Chứng minh rằng tồn tại số có dạng 19941994 199400 0 chia hết cho 1995. 4. Chứng minh rằng tồn tại số tự nhiên k sao cho (1999^k – 1) chia hết cho104 5/25/2021 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 12