Bài giảng Nguyên lý chuồng bồ câu - Trần Vĩnh Đức

Nguyên lý chuồng bồ câu<br /> <br /> Nguyên lý chuồng bồ câu1<br /> Trần Vĩnh Đức<br /> HUST<br /> <br /> Ngày 17 tháng 2 năm 2014<br /> <br /> 1<br /> <br /> Tham khảo: R. A. Brualdi, Introductory Combinatorics, Fifth Edition . . .<br /> <br /> .<br /> <br /> .<br /> <br /> .<br /> <br /> Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014<br /> <br /> 1 / 44<br /> <br /> Nội dung<br /> <br /> 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<br /> <br /> .<br /> <br /> .<br /> <br /> .<br /> <br /> .<br /> <br /> .<br /> <br /> .<br /> <br /> Nguyên lý chuồng bồ câu | Nguyên lý chuồng bồ câu<br /> <br /> .. ị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. .<br /> . . . . . .<br /> <br /> Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014<br /> <br /> 3 / 44<br /> <br /> Nguyên lý chuồng bồ câu | Nguyên lý chuồng bồ câu<br /> <br /> .. í 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.<br /> <br /> .<br /> <br /> .<br /> <br /> .<br /> <br /> .<br /> <br /> .<br /> <br /> .<br /> <br /> Trần Vĩnh Đức | HUST | Ngày 17 tháng 2 năm 2014<br /> <br /> 4 / 44<br /> <br /> Nguyên lý chuồng bồ câu | Nguyên lý chuồng bồ câu<br /> <br /> .. hứng minh. C Ta xét m tổng a1 , a1 + a2 , . . . , a1 + a2 + · · · + am .<br /> <br /> .<br /> . . . . . .<br /> <br />