zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Khoa Học Tự Nhiên

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

Chia sẻ: Le Xuan Manh | Ngày: | Loại File: PDF | Số trang:16

Báo xấu

141
lượt xem 14
download

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

Giới thiệu bài toán tồn tại, nguyên lý lồng chim câu, bài tập bài toán tồn tại là những nội dung chính trong bài 4 "Bài toán tồn tại" thuộc bài giảng Toán rời rạc. Mời các bạn cùng tham khảo.

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 Toán rời rạc: Bài 4 - TS. Nguyễn Văn Hiệu

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
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
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.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
4.2 . Nguyên lý lồng chim câu • Ví dụ 2.1 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 5
4.2 . Nguyên lý lồng chim câu Nguyễn Văn Hiệu, 2012, Discrete Mathematics 6
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
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
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
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
4.2. Nguyên lý lồng chim câu a1, a2,..., an+1 aj = 2kj *qj qj là số dương lẻ nhỏ hơn 2n. Dirichlet : qi = qj = q. Khi đó ai= 2ki *q và aj = 2kj *q. Nếu ki  kj thì aj chia hết cho ai Nguyễn Văn Hiệu, 2012, Discrete Mathematics 11
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
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 bị điểm dưới 2, chỉ 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
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.
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
THAT’S ALL; THANK YOU • WHAT NEXT? BÀI TOÁN ĐẾM LIỆT KÊ

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.