Trong một cuộc chạy đua, người tham gia phải chạy từ chỗ cờ đỏ đến cờ xanh dương, rồi chạy tiếp từ cờ xanh dương đến cờ xanh lá. Biết rằng 4 đường khác nhau từ cờ đỏ đến cờ xanh dương và 6 đường khác nhau từ cờ xanh dương đến cờ xanh lá. Hỏi cần ít nhất bao nhiêu người tham gia để chắc chắn rằng tồn tại 3 người chạy cùng một đường trong suốt cuộc...
Đọc tiếp
Trong một cuộc chạy đua, người tham gia phải chạy từ chỗ cờ đỏ đến cờ xanh dương, rồi chạy tiếp từ cờ xanh dương đến cờ xanh lá. Biết rằng 4 đường khác nhau từ cờ đỏ đến cờ xanh dương và 6 đường khác nhau từ cờ xanh dương đến cờ xanh lá. Hỏi cần ít nhất bao nhiêu người tham gia để chắc chắn rằng tồn tại 3 người chạy cùng một đường trong suốt cuộc đua?
Ta sẽ chứng minh cần ít nhất 21 người. Thật vậy, nếu có ít nhất 21 người tham gia đường đua thì do có tổng cộng 10 con đường khác nhau nên theo nguyên lí Diriclet tồn tại 1 con đường có từ 3 người tham gia trở lên.
Với trường hợp có 20 người tham gia, ta chỉ ra 1 trường hợp không thỏa mãn:
Ta dễ dàng lập những sơ đồ tương tự để chứng minh nếu có \(\le19\) người tham gia thì không đảm bảo điều kiện đề bài.
Như vậy cần có ít nhất 21 người tham gia để đảm bảo điều kiện bài toán được thỏa mãn.