Chứng minh rằng trong 9 người bất kì luôn tìm được 3 người đôi một quen nhau hoặc

Chứng minh rằng trong 9 người bất kì luôn tìm được 3 người đôi một quen nhau hoặc

Đề bài: Chứng minh rằng trong 9 người bất kì luôn tìm được 3 người đôi một quen nhau hoặc 4 người đôi một không quen nhau.

Lời giải:

Xét người A bất kì trong 9 người.

Khi đó A quen hoặc không quen với mỗi người trong 8 người còn lại.

Do đó theo nguyên lí Dirichlet, tồn tại ít nhất $1+\left[\frac{8-1}{2}\right]=4$  người quen hoặc không quen A.

Vậy trong 9 người bất kì luôn tìm được 3 người đôi một quen nhau hoặc 4 người đôi một không quen nhau.

Xem thêm các câu hỏi ôn tập Toán chọn lọc, hay khác: