n khách du lịch

Một nhóm có http://dientuvietnam...n/mimetex.cgi?n khách du lịch.Trong mỗi http://dientuvietnam...n/mimetex.cgi?3 trong họ có http://dientuvietnam...n/mimetex.cgi?2 người không quen nhau.Với mỗi cách chia họ thành hai nhóm ta có thể tìm http://dientuvietnam...n/mimetex.cgi?2 khách du lịch trong cùng một nhóm và họ quen nhau.Chứng minh rằng một khách du lịch quen nhiều nhất http://dientuvietnam.net/cgi-bin/mimetex.cgi?\dfrac{2}{5}n khách du lịch.

Nhìn lại các bài toán của Bulgaria 2004

Với mỗi cách chia họ thành hai nhóm ta có thể tìm http://dientuvietnam...n/mimetex.cgi?2 khách du lịch trong cùng một nhóm và họ quen nhau.

Chia như thế nào đây, chẳng nhẽ chia thành 2 và n-2 cũng được ah, anh quanvu lai dịch nhầm rồi.

Với mỗi cách chia họ thành hai nhóm ta có thể tìm http://dientuvietnam...n/mimetex.cgi?2 khách du lịch trong cùng một nhóm và họ quen nhau.

Chia như thế nào đây, chẳng nhẽ chia thành 2 và n-2 cũng được ah, anh quanvu lai dịch nhầm rồi.

Hi hi,lần này anh dịch đúng rồi,2 người trong cùng 1 nhóm chứ không phải mỗi nhóm đều có 2 người như vậy Nếu không đem chia như chú thì n người đôi một quen nhau mất .

Ta lập 1 đồ thị có http://dientuvietnam...n/mimetex.cgi?n đỉnh biểu thị http://dientuvietnam...n/mimetex.cgi?n người;2 người quen nhau thì 2 đỉnh tưong ứng nối bởi 1 cạnh.Giả thiết thứ 2 cho thấy đồ thị ko phải là lưỡng phân;do đó tồn tại ít nhất 1 chu trình lẻ;ta chọn chu trình http://dientuvietnam...gi?A_1A_2...A_m có độ dài nhỏ nhất.Theo giả thiết thứ nhất ko tồn tại tam giác suy ra http://dientuvietnam...n/mimetex.cgi?X nối với http://dientuvietnam...gi?A_i,A_j,(i<j);Do ko có tam giác nên 2 đỉnh trên ko kề nhau trong chu trình; ta thấy http://dientuvietnam...mimetex.cgi?j-i phải lẻ hoặc bằng 2 nếu ko http://dientuvietnam.....A_iXA_j...A_n sẽ là 1 chu trình có độ dài lẻ nhỏ hơn http://dientuvietnam...imetex.cgi?m;vô lí;nếu http://dientuvietnam...mimetex.cgi?j-i lẻ thì http://dientuvietnam...x.cgi?A_i..A_jX là 1 chu trình có dộ dài lẻ nhỏ hơn http://dientuvietnam.net/cgi-bin/mimetex.cgi?m, vô lí;vậy http://dientuvietnam.net/cgi-bin/mimetex.cgi?j-i=2. Dễ thấy http://dientuvietnam.net/cgi-bin/mimetex.cgi?X ko thể được nối với đỉnh nào nữa.
Từ khẳng định trên suy ra http://dientuvietnam.net/cgi-bin/mimetex.cgi?A_isao cho

Bài viết đã được chỉnh sửa nội dung bởi anhminh: 29-08-2006 - 20:51

Chứng minh rằng một khách du lịch quen nhiều nhất http://dientuvietnam.net/cgi-bin/mimetex.cgi?\dfrac{2}{5}n khách du lịch.

đề bài là cm mỗi khách hay là cm tồn tại 1 khách quen nhiều nhất http://dientuvietnam.net/cgi-bin/mimetex.cgi?\dfrac{2}{5}n khách du lịch?

Chứng minh rằng một khách du lịch quen nhiều nhất http://dientuvietnam.net/cgi-bin/mimetex.cgi?\dfrac{2}{5}n khách du lịch.

đề bài là cm mỗi khách hay là cm tồn tại 1 khách quen nhiều nhất http://dientuvietnam.net/cgi-bin/mimetex.cgi?\dfrac{2}{5}n khách du lịch?

mình cũng không rõ lắm! Anh Quan Vũ, đề bài là thế nào vậy?

Chứng minh rằng một khách du lịch quen nhiều nhất http://dientuvietnam.net/cgi-bin/mimetex.cgi?\dfrac{2}{5}n khách du lịch.

đề bài là cm mỗi khách hay là cm tồn tại 1 khách quen nhiều nhất http://dientuvietnam.net/cgi-bin/mimetex.cgi?\dfrac{2}{5}n khách du lịch?

mình cũng không rõ lắm! Anh Quan Vũ, đề bài là thế nào vậy?

À,đầu bài là:có một khách du lịch quen nhiều nhất... Dịch thế là rõ rồi còn gì?