Đang chuẩn bị liên kết để tải về tài liệu:
Bài tập toán rời rạc 4

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ả | 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 c-e & d-f 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 (c-e) tận cùng bằng 0 và (d-f) 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 . | 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 c-e & d-f 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ư