Chủ đề này có 1 trả lời

[kelieulinh]

VNTST 2001:
Trong 1 hội nghị có 42 người gồm nam và nữ.Trong số 31 người bất kì luôn tìm được 1 đôi nam nữ quen nhau.Chứng minh rằng trong số 41 người đó luôn tìm được 12 đôi nam nữ quen nhau.

DDTH

Bài viết đã được chỉnh sửa nội dung bởi ducvipdh12: 23-06-2015 - 21:02

[LNH]

VNTST 2001:
Trong 1 hội nghị có 42 người gồm nam và nữ.Trong số 31 người bất kì luôn tìm được 1 đôi nam nữ quen nhau.Chứng minh rằng trong số 41 người đó luôn tìm được 12 đôi nam nữ quen nhau.

DDTH

Đề bị sai, lẽ ra phải là 42 người chứ

Giải:

Giả sử trong số 42 người đó không tồn tại 12 đôi nam nữ quen nhau

Tồn tại cách sắp xếp các cặp nam nữ quen nhau lớn nhất. Đặt số cặp nam nữ quen nhau là $k$, còn cặp nam nữ quen nhau là $\left ( a_{i},b_{i} \right )$ với $i=\overline{1,k}$

Ta chia tập hợp 41 người thành 2 phần:

Phần 1:2k người ứng với k cặp nam nữ quen nhau

Phần 2:$42-2k$ người còn lại. Dễ thấy trong $42-2k$ người này không tồn tại đôi nam nữ nào quen nhau

Ta tách $11-k$ người trong phần 2(vì $k\leq 11$ nên $11-k$ không âm). Xét $31-k$ người còn lại:

Ta thêm k nam vào thì theo giả thiết, tồn tại 1 người nam trong k người nam quen với 1 người nữ của tập hợp $31-k$ người trên.

Giả sử người đó là $a_1$

Khi đó $b_1$ không quen người nào trong $31-k$ người này (vì nếu $b_1$ quen người nào trong $31-k$ người này thì tồn tại 1 cách sắp xếp khác có số người quen lớn hơn k, vô lí)

Ta tiến hành thay $a_1$ thành $b_1$ và tiếp tục quá trình trên, ta có k nữ đều không quen người nào trong $31-k$ người này.

Ta xét tập hợp gồm $31-k$ người này và k nữ, nhận thấy rằng 31 người này không tồn tại cặp nam nữ nào quen nhau, trái với giả thiết.

Vậy trong số 42 người đó luôn tồn tại 12 đôi nam nữ quen nhau

Bài viết đã được chỉnh sửa nội dung bởi lenhathoang1998: 28-07-2013 - 13:35