Bài tập toán rời rạc 4

Chia sẻ: Nguyen Doan Minh Tri | Ngày: | Loại File: PPT | Số trang:5

Thêm vào BST

Báo xấu

2.487
lượt xem 211
download

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

Tham khảo tài liệu 'bài tập toán rời rạc 4', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

Chủ đề:

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

Lưu

Nội dung Text: Bài tập toán rời rạc 4

Bài 5: Chứng minh rằng trong số 10 người bất kỳ bao giờ cũng tìm được hoặc là 2 người có cùng tổng số tuổi chia hết cho 16, hoặc là hai người mà hiệu chia hết cho 16. Giải: Gọi a0……a15 là số dư khi chia tuổi của 10 người cho 16 =>ai € {0,1….15} với i=0…15; TH1: Ta chia 16 thành 16=15+1=14+2=…………=8+8=0+0; =>Có tất cả là 9 cặp trong khi đó có 10 người.Theo nguyên lý Dirichlet=>tồn tại 2 tổng số các ai thuộc cùng 1 tổng >Luôn tìm được 2 người có tổng số tuổi chia hết cho 16.
TH2:  Do có 10 người mà lại có 15 số dư >Tồn tại 2 người có cùng 1 số dư khi chia tuổi của họ cho 16 Suy ra luôn tồn tại ai=aj >Tìm được 2 người mà hiệu số tuổi của họ chia hết cho 16.
Bài 6:  Cần có ít nhất bao ngiêu bộ có thứ tự gồm 2 số nguyên (a,b)sao cho chắc chắn tìm được  trong số hai bộ (c,d)&(e,f) sp cho ce & df là các số có tận cùng bằng 0. Giải: Ta xét cặp (a,b) bất kỳ.Chia các cặp này thành 10 nhóm có số dư của a khi chia cho 10 là 0,……9; Vậy 2 cặp (a1,a2) &(a3,a4) trong cùng 1 nhóm thì a1&a3 cùng số dư khi chia cho 10. Do đó chỉ cần tìm cặp (a,b) sao cho ít nhất 1 trong 10 nhóm trên >ít nhất là 11 cặp. Trong nhóm vừa nên trên sẽ có 2 cặp (c,d)&(e,f) sao cho (ce) tận cùng bằng 0 và (df) tần cùng =0. Mà có 10 nhóm nên để tồn tại ít nhất 1 nhóm có ít nhất 11 cặp thì số cặp (a,b) cần chọn là: 11*10+1=101.
Bài 7: 17 nhà bác học đôi 1viết thư trao đổi cho nhau vè 3 chủ đề , mỗi cặp chỉ trao đổi với nhau về 1 chủ đề.Chứngminh rằng luôn tìm được 3 nhà bác học đôi một viết thư trao đổi với nhau về cùng 1 chủ đề. Giả sử lấy 1 nhà bác học bất kì là a1 viết thư cho 16 bác học còn lại > do có 3 vấn đề cần trao đổi nên tồn tại ít nhất 6 nhà bác học a1vấn đề 1 nào đó. Trong 6 nhà bác học trên lấy ra 1 nhà bác học bất kì là a2. 5 người còn lại nếu có 1 nhà bác học viết thư trao đổi với a2 về vấn đề 1 thì bài toán đã giải quyết. Ta xét TH: a2 viết thư trao đổi với 5 người về 2 vấn đề còn lại. Theo nguyên lý dicrichlet tồn tai 3 người trao đổi với a2 về vấn đề nào đó gọi là vấn đề 2. Trong 3 người trao đổi về vấn đề 2 nếu có 1 người trao đổi vấn đề 2 thì bài toán được giải. Ngược lại nếu không có ai trong 3 người đó trao đổi về vấn đề 2 thì chắc chắn họ sẽ trao đổi về vấn đề 3. =>Bào toán đã được giải.
Bài 8:  Trong không gian cho 9 điểm có toạ độ nguyên.Chứng minh rằng trong số 9 điểm luôn tìm được 2 diểm sao cho đoạn thẳng nối chúng đi qua điểm có tạo độ nguyên. Giải:  Xét 1 diểm bất kì trong không gian (x,y,z). Do 1 giá trị x hoặc y hoặc z chỉ nhận 1 trong 2 giá trị chẵn, lẽ. >có tất cả là 2*2*2=8 bộ mà (x,y,z) có thể nhận. Ví dụ như (chẵn, chẵn, chẵn),(chẵn, chẵn, lẽ)……. Mà theo bài ra thì có tất cả là 9 điểm.Theo nguyên lý Dirichle thì tồn tại 2 điểm có cùng tọa độ chẵn,lẽ. =>trung điểm của đoạn thẳng nối 2 điểm đó là số nguyên>dpcm