Bài giảng Chương II: Các phương pháp đếm và nguyên lý Dirichlet (Phần 2) - GVC ThS. Võ Minh Đức

Chia sẻ: Vo Minh Duc | Ngày: | Loại File: PPTX | Số trang:12

Thêm vào BST

Báo xấu

337
lượt xem 53
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Chương II: Các phương pháp đếm và nguyên lý Dirichlet (Phần 2)" cung cấp cho các bạn những kiến thức về: sinh các hoán vị và tổ hợp, hệ thức truy hồi, nguyên lý Dirichlet. Tài liệu hữu ích với các bạn chuyên ngành Toán họ

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Chương II: Các phương pháp đếm và nguyên lý Dirichlet (Phần 2) - GVC ThS. Võ Minh Đức

Ch¬ng II c ¸c ph¬ng ph¸p ®Õm vµ ng uyªn lý diric hle t 10/1/14 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 1
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 10/1/14
III. SINH CÁC HOÁN VỊ VÀ TỔ HỢP. 1. Sinh các hoán vị Cho tập gồm n phần tử {1, 2, 3,. . .n} Hóan vị đi trứớc: Hoán vị a1a2...an được gọi là đi trước hoán vị b1b2...bn nếu tồn tại k (1  k  n), a1 = b1, a2 = b2,..., ak1 = bk1 và ak < bk. 10/1/14 ThS. Võ Minh Đức, CĐSP Đăklăk 3
III. SINH CÁC HOÁN VỊ VÀ TỔ HỢP. 1. Sinh các hoán vị Giả sử có hoán vị: a1a2 ...an. Nếu an-1 < an thì rõ ràng đổi chỗ an-1 và an cho nhau thì sẽ nhận được hoán vị mới đi liền sau hoán vị đã cho. Nếu tồn tại các số nguyên aj và aj+1 sao cho aj < aj+1 và aj+1 > aj+2 > ... > an để nhận được hoán vị liền sau ta đặt vào vị trí thứ j số nguyên nhỏ nhất trong các số lớn hơn aj của tập aj+1, aj+2, ..., an, rồi liệt kê theo thứ tự tăng dần của các số còn lại của aj, aj+1, aj+2, ..., an vào các vị trí j+1, ..., n. Dễ thấy không có hoán vị nào đi sau hoán vị xuất phát và đi trước hoán vThS. Võ Minh Đức, CĐSP Đăklăk 10/1/14 ị vừa tạo ra 4
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. 10/1/14 GVC, ThS. Võ Minh Đức, CĐSP Đắk Lắk 5
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). 10/1/14 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 6
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? 10/1/14 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 7
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. 10/1/14 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 8
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. 10/1/14 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 9
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
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 10/1/14 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 11
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 10/1/14 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 12