Có \(20\) người quyết định đi bơi thuyền bằng \(10\) chiếc thuyền đôi. Biết rằng nếu hai

Câu hỏi số 599909:

Vận dụng cao

Có \(20\) người quyết định đi bơi thuyền bằng \(10\) chiếc thuyền đôi. Biết rằng nếu hai người \(A\) và \(B\) mà không quen nhau thì tổng số những người quen của \(A\) những người quen của \(B\) không nhỏ hơn \(19.\) Chứng minh rằng có thể phân công vào các thuyền đôi sao cho mỗi thuyền đôi đều là hai người quen nhau.

Quảng cáo

Xem lời giải

Câu hỏi:599909

Phương pháp giải

Vận dụng nguyên lí Dirichlet.

Giải chi tiết

Nếu trong \(20\) người không có hai người nào quen nhau thì tổng số người quen của cả hai người bất kì là \(0.\) Điều này mâu thuẫn với giả thiết là tổng số người quen của hai người không nhỏ hơn \(19.\) Vậy tồn tại một số cặp quen nhau.

Ta xếp mỗi cặp quen nhau đó vào một thuyền đôi. Gọi \(k\) là số lượng thuyền lớn nhất mà trong đó ta có thể xếp được những cặp quen nhau vào một thuyền và kí hiệu thuyền thứ \(i\) xếp hai người \({A_i}\) và \({B_i}\) quen nhau \(\left( {1 \le i \le k} \right).\)

Giả sử \(k \le 9,\) kí hiệu tập hợp \(M\) gồm những người chưa được xếp vào thuyền nào, tứ là gồm những người đôi một không quen nhau. Chọn hai người \(A\) và \(B\) trong tập hợp \(M.\) Theo bài ra thì tổng số người quen của \(A\) và số người quen của \(B\) không nhỏ hơn \(19\) và những người quen \(A\) hoặc quen \(B\) đã được xếp vào nhiều nhất là \(9\) thuyền đôi (trừ \(1\) thuyền vì \(A,\,B\) chưa được xếp), mà \(19 = 9.2 + 1\) nên theo nguyên lí Dirichlet tồn tại ít nhẩt một thuyền chở hai người quen cả \(A\) và \(B\) (thuyền thứ \(i\) nào đó). Nhưng khi đó ta có thể xếp lại như sau: trong \(k - 1\) thuyền đâu tiên vẫn giữ nguyên, còn thuyền thứ \(i\) xếp \({A_i}\) và \(B,\) còn thuyền \(k + 1\) xếp \(A\) và \({B_i}.\) Điều này mau thuẫn với giả sử \(k \le 9.\)

Theo các xếp này ta tiếp tục xếp đến hết \(10\) thuyền sao cho mỗi thuyền có hai người đều quen nhau.

Tham Gia Group Dành Cho 2K12 Chia Sẻ, Trao Đổi Tài Liệu Miễn Phí

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

>> Học trực tuyến lớp 7 trên Tuyensinh247.com Học bám sát chương trình SGK mới nhất của Bộ Giáo dục. Cam kết giúp học sinh lớp 7 học tốt, hoàn trả học phí nếu học không hiệu quả. Phụ huynh và học sinh tham khảo chi tiết khoá học tại: Link