Cho hai tập hợp số nguyên dương phân biệt mà mỗi số đều nhỏ hơn \(n\). Chứng minh rằng nếu

Câu hỏi số 552602:

Vận dụng cao

Cho hai tập hợp số nguyên dương phân biệt mà mỗi số đều nhỏ hơn \(n\). Chứng minh rằng nếu tổng số phần tử của hai tập hợp không nhỏ hơn \(n\) thì có thể chọn được trong mỗi tập hợp một phần tử sao cho tổng của chúng bằng \(n\).

Quảng cáo

Xem lời giải

Câu hỏi:552602

Phương pháp giải

+ Nguyên lý Dirichlet cơ bản : Nếu nhốt \(n + 1\) con thỏ vào \(n\) cái chuồng thì bao giờ cũng có một cái chuồng chứa ít nhất hai con thỏ.

+ Số thỏ: \(m + k\) con; Số lồng: \(n - 1\) lồng

Giải chi tiết

Gọi hai tập số nguyên dương đã cho là:

\(\begin{array}{l}A = \left\{ {{a_1};{a_2};...;{a_m}} \right\}\\B = \left\{ {{b_1};{b_2};...;{b_k}} \right\}\end{array}\), trong đó \(\left\{ \begin{array}{l}{a_i} < n\left( {i = 1;2;...;m} \right)\\{b_j} < n\left( {j = 1;2;...;k} \right)\\m + k \ge n\end{array} \right.\)

Xét \(C = \left\{ {n - {b_1};n - {b_2};...;n - {b_k}} \right\}\)

Ta coi “thỏ” là các số nguyên dương thuộc tập hợp \(A\)\( \Rightarrow \) Có \(\left( {m + k} \right)\) con.

“Lồng” là các số nguyên dương từ \(1\) đến \(n - 1\)\( \Rightarrow \) Có \(\left( {n - 1} \right)\) lồng.

Ta có: \(\left( {m + k} \right) \ge n > n - 1 \Rightarrow \left( {m + k} \right) > n - 1\)

Theo nguyên lý Dirichlet tồn tại ít nhất \(2\) phần tử bằng nhau, không đồng thời thuộc tập \(A\) và \(C\)

Tức là \({a_i} = n - {b_j} \Rightarrow {a_i} - {b_j} = n\)

Vậy tổng số phần tử của hai tập hợp không nhỏ hơn \(n\) thì có thể chọn được trong mỗi tập hợp một phần tử sao cho tổng của chúng bằng \(n\).

Tham Gia Group Dành Cho Lớp 6 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 6 chương trình mới 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 6 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