* Tuyển tập các đề thi chọn đội tuyển 2020-2021 * Tuyển sinh CLB Toán Lim năm học mới * Tuyển tập các bài toán số học hay ôn thi chọn đội tuyển VMO 2022 * Tuyển tập các bài toán Hình Học Phẳng ôn thi chọn đội tuyển hay * Tuyển chọn các bài toán hay trong ôn tập thi vào 10 chuyên Toán * Hướng dẫn cách chèn hình ảnh vào web sử dụng Imgur

Nguyên lý Dirichle trong tổ hợp rời rạc


Được tạo lúc 2021-05-24 11:45:10 , cập nhật lúc 2021-05-26 10:12:29


hangtuan

Bài đăng này sẽ gồm các bài toán mà ở đó sử dụng nguyên lý Dirichle sẽ đem lại những kết quả thú vị. Nguyên lý Dirichle là một trong những nguyên lý quan trọng, cùng với nguyên lý cực hạn, đã có rất nhiều bài toán hay được xây dựng nên qua các kỳ thi. Mời các bạn cùng đóng góp.

Bài toán 1. (Russia 2000) Bảng 100x100 được chia thành các ô vuông đơn vị. Mỗi ô vuông sẽ được tô bởi 1 trong 4 màu, mỗi màu được tô cho 25 ô vuông tại mỗi hàng, mỗi cột. Chứng minh rằng : tồn tại 2 hàng và 2 cột mà 4 ô giao của chúng có 4 màu khác nhau.

Trả lời