Bài giảng Toán rời rạc - Bài 4: Bài toán tồn tại - Nguyễn Văn Hiệu

Nội dung text: Bài giảng Toán rời rạc - Bài 4: Bài toán tồn tại - Nguyễn Văn Hiệu

1. BÀI 4 BÀI TOÁN TỒN TẠI Giáo viên: TS. Nguyễn Văn Hiệu Email: nvhieuqt@dut.udn.vn
2. Nôi dung 4.1. Giới thiệu 4.2. Nguyên lý lồng chim câu 4.3. Bài tập
3. 4.1.Giới thiệu • Có nhiều điều tưởng chừng hiển nhiên – 11 số tự nhiên bất kỳ, tồn tại ít nhất 2 số có chữ số tận cùng giống nhau. – Đúng/Sai: cần chứng minh • Mục tiêu chung – Chứng minh sự tồn tại của một cấu hình – Không tiến hành liệt kê tất cả • Nguyên lý Dirichlet
4. 4.2 . Nguyên lý lồng chim câu • Nguyên lý Dirichlet Nếu đem xếp nhiều hơn n đối tượng vào n cái hộp, thì luôn tìm được một cái hộp chứa không ít hơn 2 đối tượng. • Nguyên lý Dirichlet (tổng quát) Nếu đem xếp n đối tượng vào k cái hộp, thì luôn tìm được một cái hộp chứa không ít hơn n/k đối tượng. Nguyễn Văn Hiệu, 2012, Discrete Mathematics 4
5. 4.2 . Nguyên lý lồng chim câu • Ví dụ 2.1 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 5
6. 4.2 . Nguyên lý lồng chim câu Nguyễn Văn Hiệu, 2012, Discrete Mathematics 6
7. 4.2. Nguyên lý lồng chim câu Ví dụ 2.2 . Có 5 loại học bổng khác nhau. . Chắc chắn rằng có 6 người cùng một loại học bổng . Cần tối thiểu bao nhiêu người n/5 > 5 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 7
8. 4.2. Nguyên lý lồng chim câu Ví dụ 2.3: Trong một tháng gồm 30 ngày, một đội bóng chuyền chơi ít nhất mỗi ngày một trận, nhưng không chơi quá 45 trận. CMR có một giai đoạn gồm một số ngày liên tiếp trong tháng, đội bóng phải chơi tất cả 14 trận. Nguyễn Văn Hiệu, 2012, Discrete Mathematics 8
9. 4.2. Nguyên lý lồng chim câu ai - là tổng số trận mà đội bóng đã chơi từ đầu tháng cho đến hết ngày thứ i. 1 a1<a2< . . . <a30 45 15 a1 + 14 < a2 +14 < . . . <a30 +14 59 a1,. . .,a30 ,a1 + 14 , a2 +14 ,. . . ,a30 +14 59 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 9
10. 4.2. Nguyên lý lồng chim câu • Ví dụ 2.4 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. Nguyễn Văn Hiệu, 2012, Discrete Mathematics 10
11. 4.2. Nguyên lý lồng chim câu a1, a2, , an+1 kj aj = 2 *qj qj là số dương lẻ nhỏ hơn 2n. ki kj Dirichlet : qi = qj = q. Khi đó ai= 2 *q và aj = 2 *q. Nếu ki kj thì aj chia hết cho ai Nguyễn Văn Hiệu, 2012, Discrete Mathematics 11
12. 4.2. Nguyên lý lồng chim câu • Ví dụ 2.6 . 5x5 ô vuông, ô (i,j) = 1||-1||0 . CM: tồn tại Si = Sj
13. 4.2. Nguyên lý lồng chim câu • Ví dụ 2.7 . Trong 45 SV làm bài kiểm tra, không có ai bị điểm dưới 2, chỉ có 2 SV được điểm 10. CMR tồn tại 6 SV có điểm kiểm tra bằng nhau? . HD: . Xây dựng thang điểm từ 2 đến 9
14. 4. 3. Bài tập 1. Chọn 5 số từ tập X = {1,2, ,8}. Chứng minh tồn tại ít nhất một cặp số có tổng bằng 9 2. Chứng tỏ 10 người bất kỳ tồn tại hai người có tổng tuối chia hết cho 16 hoặc hiệu tuổi chia hết cho 16. 3. Chứng tỏ 7 số nguyên bất kỳ tồn tại hai số nguyên x,y: x+ y chia hết cho 10 hoặc x-y chia hết cho 10.
15. 4. 3. Bài tập 4. Chứng minh nếu chọn 151 giáo trình máy tính phân biệt đánh số từ 1 đến 300, thì ít nhất có hai giáo trình có thứ tự liên tiếp. 5. Một nhóm gồm 6 người, cứ lấy một cặp bất kỳ, thì hai người này hoặc là bạn hoặc là thù. Chứng minh rằng sẽ có các bộ ba hoặc là bạn của nhau hoặc là thù của nhau. Nguyễn Văn Hiệu, 2012, Discrete Mathematics 15
16. THAT’S ALL; THANK YOU • WHAT NEXT? BÀI TOÁN ĐẾM LIỆT KÊ