Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Bài giảng Nguyên lý chuồng bồ câu do Trần Vĩnh Đức biên soạn có nội dung trình bày về nguyên lý chuồng bồ câu, nguyên lý chuồng chim bồ câu dạng tổng quát, định lý Ramsey, chứng minh định lý Ramsey, ví dụ và tổng quát hóa. | Nguyên lý chuồng bồ câu Nguyên lý chuồng bồ câu1 Trần Vĩnh Đức HUST Ngày 17 tháng 2 năm 2014 1 Tham khảo: R. A. Brualdi, Introductory Combinatorics, Fifth Edition . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 1 / 44 Nội dung 1 Nguyên lý chuồng bồ câu 2 Nguyên lý chuồng chim bồ câu dạng tổng quát 3 Định lý Ramsey 4 Chứng minh định lý Ramsey 5 Ví dụ và tổng quát hóa . . . . . . Nguyên lý chuồng bồ câu | Nguyên lý chuồng bồ câu ịnh lý Đ Nếu bỏ n + 1 đối tượng vào n hộp thì có ít nhất một hộp có nhiều hơn hoặc bằng hai đối tượng. . í dụ V Trong 13 người có ít nhất 2 người sinh cùng tháng. . . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 3 / 44 Nguyên lý chuồng bồ câu | Nguyên lý chuồng bồ câu í dụ V Cho m số nguyên a1 , a2 , . . . , am , luôn tồn tại các số nguyên k và ℓ với 0 ≤ k < ℓ ≤ m sao cho ak+1 + ak+2 + · · · + aℓ chia hết cho m. . Nói cách khác, luôn có dãy liên tiếp các ai sao cho tổng của chúng chia hết cho m. . . . . . . Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014 4 / 44 Nguyên lý chuồng bồ câu | Nguyên lý chuồng bồ câu hứng minh. C Ta xét m tổng a1 , a1 + a2 , . . . , a1 + a2 + · · · + am . . . . . . . .
