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

[tangkhaihanh]

Một cơ quan cần tuyển 3 người để lập thành một nhóm có đủ năng lực biên dịch các tài liệu từ 6 thứ tiếng Anh, Pháp, Nga, Đức, Trung Quốc và Bồ Đào Nha sang tiếng việt. có 7 người đến dự tuyển, trong đó mỗi người đều biết hai và chỉ 2 trong 6 thứ tiếng đó và bất kỳ hai người nào cũng cùng biết nhiều nhất 1 thứ tiếng chung trong số 6 thứ tiếng đó . Biết rằng thứ tiếng nào cũng có ít nhất hai người biết, hỏi có thể xảy ra trường hợp không thể tuyển chọn được như yêu cầu đã nêu không? Tại sao?

Bài viết đã được chỉnh sửa nội dung bởi perfectstrong: 30-08-2012 - 20:02

[The Gunner]

Mình giải thử ( cách này thấy ko hay lắm, ko bik có cách nào tốt hơn ko?)
Dịch bài toán ra ngôn ngữ đồ thị với 6 thứ tiếng là 6 đỉnh $A,B,C,D,E,F$.Một người dự tuyển xem như đoạn thẳng nối hai đỉnh nếu họ bik hai tiếng ứng với hai đỉnh đó. Ta nhận thấy rằng đồ thị này sẽ là đồ thị đơn và thỏa mãn điều kiện bậc của mỗi đỉnh ko nhỏ hơn 2. Do có 7 cạnh --> đồ thị có tổng bậc là 14 nên chỉ có thể có hai trường hợp là hai đỉnh bậc 3 và 4 đỉnh bậc 2 hoặc một đỉnh bậc 4 và 5 đỉnh bậc 2
TH1: Trường hợp có đỉnh bậc 4.
Giả sử A là đỉnh bậc 4 và kề với B,C,D,E. Xét đỉnh F thì F phải có bậc 2 và B,C,D,E mới chỉ bậc 1. Trong khi chỉ còn 3 cạnh nên chỉ có thể xảy ra trường hợp hai cạnh nối với F đỉnh hai đỉnh trong B,C,D,E và hai đỉnh còn lại có bậc 1 nối với nhau. Giả sử F nói với B và E còn C,D nối với nhau thì ta có ba cạnh CD,AE,BF tương ứng sẽ là 3 người đc chọn
TH2: Trường hợp A là đỉnh bậc 3 nối với C,D,B. nếu một trong 3 đỉnh C,D,B là bậc 3. giả sử B là đỉnh bậc 3
+Nếu hai cạnh còn lại xuất phát từ B nối với hai đỉnh nằm ngoài tâp kề của A tức là E và F. thì ta còn 2 cạnh còn lại để nối 4 đỉnh C,D,E,F ( lúc này chúng mới bậc 1) ta thấy hai cạnh này và AB luôn là 3 cạnh thỏa mãn
+Nếu hai cạnh còn lại của B nối với C và D thì ta chỉ còn 2 cạnh trong khi E và F mới bậc 0 nên trường hợp này ko thể nối để thảo mãn E và F có bậc 2
+ Nếu hai cạnh còn lại của B nối với một trong hai đỉnh C,D và một trong hai đỉnh E,F giả sử B nối với C và E thì chỉ còn hai cạnh còn lại trong khi F mới bậc 0 còn E và D nậc 1 nên F nối với E và D khi đó ta có 3 cạnh EF,AD,BC thỏa mãn
Tóm lại là ko có trường hợp nào mà có thể xảy ra trường hợp không thể tuyển chọn được như yêu cầu
P/s: mình nghĩ có một hướng khác để cm hay hơn là chứng minh luôn tồn tại một cách phân hoạch các đỉnh thành hai tập với một tập là hai đỉnh kề nhau, tập còn lại là trong 4 đỉnh còn lại phải có ít nhất 4 cạnh để nối các đỉnh trong 4 đỉnh đó là OK