Tại một buổi giao lưu có 100 người bào gồm 15 giáo viên và 85 học sinh. Trong sô...

· 13:47 15/03/2025

Tại một buổi giao lưu có 100 người bào gồm 15 giáo viên và 85 học sinh. Trong sô 15 giáo viên, mỗi người quen với ít nhất 70 người khác. Trong số 85 học sinh, mỗi người quen với không quá 10 người khác. Họ được phân vào 21 phòng. Chứng minh rằng có một phòng nào đó không chứa một cặp nào quen nhau

Trả Lời (+5 điểm)

Hỏi chi tiết

Quảng cáo

2 câu trả lời 1033

草原 (Phone 🐼)

9 tháng trước

Để chứng minh rằng có một phòng nào đó không chứa một cặp nào quen nhau, ta sẽ sử dụng phương pháp phản chứng.

Giả sử rằng trong mỗi phòng đều có ít nhất một cặp người quen nhau. Vì có 21 phòng, nên sẽ có ít nhất 21 cặp người quen nhau.

**Bước 1: Phân tích số lượng giáo viên và học sinh**

* Có 15 giáo viên, mỗi người quen ít nhất 70 người.
* Có 85 học sinh, mỗi người quen không quá 10 người.

**Bước 2: Xét số cặp quen nhau có thể xảy ra**

* **Cặp giáo viên - giáo viên:** Số lượng tối đa các cặp giáo viên là \(C(15, 2) = \frac{15 \times 14}{2} = 105\).
* **Cặp giáo viên - học sinh:**
* Mỗi giáo viên quen ít nhất 70 người, nên mỗi giáo viên quen ít nhất \(70 - 14 = 56\) học sinh (vì có 14 giáo viên khác).
* Tổng số mối quan hệ giữa giáo viên và học sinh ít nhất là \(15 \times 56 = 840\). Tuy nhiên, mỗi học sinh chỉ quen không quá 10 người, nên tổng số mối quan hệ giữa học sinh và giáo viên không thể vượt quá \(85 \times 10 = 850\).
* **Cặp học sinh - học sinh:** Số lượng tối đa các cặp học sinh là \(C(85, 2) = \frac{85 \times 84}{2} = 3570\).

**Bước 3: Đánh giá số cặp quen nhau tối thiểu**

* Giả sử mỗi phòng đều có một cặp quen nhau. Vì có 21 phòng, nên có ít nhất 21 cặp quen nhau.

**Bước 4: Tìm mâu thuẫn**

* Nếu mỗi giáo viên quen ít nhất 70 người, thì số người lạ mà giáo viên quen (ngoài 14 giáo viên khác) ít nhất là 56. Tuy nhiên, số lượng học sinh chỉ là 85. Điều này có nghĩa là mỗi giáo viên quen gần như tất cả học sinh.
* Vì mỗi học sinh chỉ quen không quá 10 người, nên không thể có quá nhiều cặp học sinh quen nhau.

**Bước 5: Chứng minh bằng phản chứng**

* Xét trường hợp xấu nhất, mỗi giáo viên quen 70 người, và 15 giáo viên này tạo thành các cặp quen nhau.
* Vì có 21 phòng, giả sử mỗi phòng có một cặp quen nhau.
* Nếu giả sử mỗi phòng chứa ít nhất một cặp quen nhau, thì phải có ít nhất 21 cặp quen nhau trong tổng số 100 người này. Tuy nhiên, với điều kiện mỗi học sinh quen không quá 10 người, việc tạo ra 21 cặp quen nhau trong mỗi phòng là rất khó xảy ra, đặc biệt khi số lượng học sinh lớn hơn số lượng giáo viên.
* Do đó, giả thiết ban đầu là sai.

**Kết luận:**

Phải tồn tại ít nhất một phòng không chứa một cặp nào quen nhau. Điều này chứng minh rằng có ít nhất một phòng mà không có hai người nào trong phòng đó quen biết nhau.

...Xem thêm

2 bình luận