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

[LNH]

Một nhóm du lịch gồm $n$ du khách. Ba người bất kì trong số họ luôn có $2$ người không quen nhau. Với mỗi cách phân chi $n$ du khách thành $2$ nhóm thì luôn tồn tại $2$ người ở cùng một nhóm quen nhau. Chứng minh rằng: tồn tại một du khách quen nhiều nhất $\frac{2n}{5}$ du khách khác.

P/s: bài đầu tiên trong năm mới

Bài viết đã được chỉnh sửa nội dung bởi LNH: 01-02-2014 - 14:00

[Karl Heinrich Marx]

http://diendantoanho...hất-la-frac2n5/

em có thể tham khảo cái này, lời giải đó của a còn thiếu chỉ ra đa giác mình xét là đa giác có số cạnh nhỏ nhất và chỗ bđt ở các trường hợp chưa chuẩn lắm, chỉ cần chỉnh lại 1 chút là đc.

[LNH]

http://diendantoanho...hất-la-frac2n5/

em có thể tham khảo cái này, lời giải đó của a còn thiếu chỉ ra đa giác mình xét là đa giác có số cạnh nhỏ nhất và chỗ bđt ở các trường hợp chưa chuẩn lắm, chỉ cần chỉnh lại 1 chút là đc.

Bài đây em có một cách khác cũng hay nè anh

Ta xây dựng một đồ thị $G=\left ( V,E \right )$ với mỗi đỉnh tương ứng với mỗi du khách, nếu $2$ du khách quen nhau thì ta sẽ nối $2$ đỉnh tương ứng bằng một cạnh

Xét hai trường hơp:

TH1: Đồ thị trên không có chu trình

Khi đó sẽ có một đỉnh $v_i$ bất kì có bậc là $1$. Vì $n \geq 3$ nên người này thỏa mãn điều kiện của đề bài

TH2: Đồ thị trên có chu trình.

Vì $G$ không là đồ thị lưỡng phân nên tồn tại ít nhất một chu trình lẻ.

Gọi chu trình lẻ nhỏ nhất là $v_1;v_2;...;v_k$

Xét một đỉnh $u$ ở ngoài chu trình trên và kề với $v_i$ và $v_j$ ($i<j$)

Khi đó $u;v_i;v_{i+1};...;v_j$ và $u;v_i;v_{i-1};...;v_1;v_t;...;v_j$ là chu trình

Mà theo giả thiết $v_1;v_2;...;v_k$ là chu trình lẻ có độ dài nhỏ nhất nên $2$ chu trình trên có độ dài chẵn

Từ đây lại suy ra $v_1;v_2;...;v_k$ là chu trình chẵn, vô lí

Vậy không có đỉnh nào bên ngoài kề với $2$ đỉnh của chu trình.

Suy ra: $\sum_{i=1}^{k}deg\left ( v_i \right )\leq 2n$

Mặt khác, $k \geq 5$ nên tồn tại $v_j$ bất kì sao cho: $deg\left ( v_j \right )\leq \frac{2n}{5}$

Suy ra đpcm