Huyện KS có \(33\) công ty, huyện KV có \(100\) công ty. Biết rằng, mỗi công ty của huyện KS hợp

Câu hỏi số 404765:

Vận dụng cao

Huyện KS có \(33\) công ty, huyện KV có \(100\) công ty. Biết rằng, mỗi công ty của huyện KS hợp tác với ít nhất \(97\) công ty huyện KV. Chứng minh rằng có ít nhất một công ty của huyện KV hợp tác với tất cả các công ty của huyện KS.

Quảng cáo

Xem lời giải

Câu hỏi:404765

Phương pháp giải

Sử dụng nguyên lý Dirichle để làm bài toán.

Giải chi tiết

Quy ước, ta xem sự hợp tác của công ty A với công ty B là một liên kết một chiều từ A vào B.

Và hiển nhiên, cũng sẽ có liên kết một chiều ngược từ B vào A.

Vì mỗi công ty của huyện KS hợp tác ít nhất \(97\) công ty huyện KV

\( \Rightarrow \) Số liên kết tối thiểu từ KS vào KV là: \(33.97 = 3201\) (liên kết).

Giả sử: Tất cả mỗi công ty huyện KV đều có tối đa \(32\) liên kết với các công ty huyện KS.

\( \Rightarrow \) Khi đó, số liên kết tối đa từ KV vào KS là: \(100.32 = 3200 < 3201\) (liên kết), mâu thuẫn.

Vậy tồn tại ít nhất một công ty huyện KV có \(33\) liên kết với các công ty huyện KS.

PH/HS 2K10 THAM GIA NHÓM ĐỂ CẬP NHẬT ĐIỂM THI, ĐIỂM CHUẨN MIỄN PHÍ!

Câu hỏi trước Câu tiếp theo

>> Học trực tuyến lớp 9 và Lộ trình UP10 trên Tuyensinh247.com Đầy đủ khoá học các bộ sách: Kết nối tri thức với cuộc sống; Chân trời sáng tạo; Cánh diều. Lộ trình học tập 3 giai đoạn: Học nền tảng lớp 9, Ôn thi vào lớp 10, Luyện Đề. Bứt phá điểm lớp 9, thi vào lớp 10 kết quả cao. Hoàn trả học phí nếu học không hiệu quả. PH/HS tham khảo chi tiết khoá học tại: Link