Diễn Đàn MathScope - Xem bài viết đơn - Hướng tới kỳ thi chọn đội tuyển Việt Nam dự IMO 2012

**Traum** · 19-02-2012, 12:59 AM

Bài 3:

Nhận xét 1: nếu giữa 3 thành phố $A,B,C $ mà có 3 con đường một chiều thì chiều của chúng là $A\rightarrow B\rightarrow C $ hoặc $C\rightarrow B\rightarrow A $.

Chứng minh: Hiển nhiên

Nhận xét 2: Cứ $4 $ thành phố $A, B, C, D $ thì có 2 thành phố mà giữa chúng không có con đường nào.

Chứng minh: Giả sử ngược lại, cứ hai thành phố bất kì trong 4 thành phố $A,B,C,D $ thì có 1 con đường một chiều.
Không mất tính tổng quát, ta xét 3 thành phố $A,B,C $. Theo nhận xét 1, chiều của các con đường trong 3 thành phố này là $A\rightarrow B\rightarrow C $ hoặc ngược lại. Không mất tổng quát xem hướng của chúng là $A\rightarrow B\rightarrow C $. Xét thành phố $D $. Nếu có $D\rightarrow A $ thì sẽ không có $C\rightarrow D $. Tức là sẽ phải có $D\rightarrow C $. Nhưng khi đó ta có $D\rightarrow C \rightarrow A $ và $D\rightarrow A $ nên không thỏa mãn. Vai trò của $A,B,C $ như nhau nên ta cũng không có $D\rightarrow B $ hay $D\rightarrow C $. Như vậy thì ta phải có $A\rightarrow D, B\rightarrow D $ và $C\rightarrow D $. Nhưng khi đó $A\rightarrow B\rightarrow D $ và $A\rightarrow D $ nên cũng không thỏa mãn. Vậy điều giả sử là sai. Bổ đề được chứng minh.

Trở lại bài toán. Với bổ đề thì ta sẽ có 4 thành phố bất kì thì có hai thành phố không được nối với nhau bởi một con đường ( hướng tùy ý). Áp dụng định lý Turan ta có tổng số con đường không vượt quá $(1-\frac{1}{3})\frac{n^2}{2} = \frac{210^2}{3} $.
Xét một cách xây đường như sau: Chia 210 thành phố thành 3 nhóm $X,Y,Z $ mỗi nhóm có 70 thành phố. Ta xây các con đường từ mỗi thành phố trong nhóm X, đến mỗi thành phố trong nhóm Y. Tương tự Y đến Z và Z đến X. Tổng số con đường được xây là $3\times 70^2 = \frac{210^2}{3} $. Dễ thấy là cách xây này thỏa mãn điều kiện bài toán.

Kết luận: $\frac{210^2}{3} $.

19-02-2012, 12:59 AM	#8
Traum Moderator Tham gia ngày: Nov 2007 Đến từ: cyber world Bài gởi: 413 Thanks: 14 Thanked 466 Times in 171 Posts	Bài 3: Nhận xét 1: nếu giữa 3 thành phố $A,B,C $ mà có 3 con đường một chiều thì chiều của chúng là $A\rightarrow B\rightarrow C $ hoặc $C\rightarrow B\rightarrow A $. Chứng minh: Hiển nhiên Nhận xét 2: Cứ $4 $ thành phố $A, B, C, D $ thì có 2 thành phố mà giữa chúng không có con đường nào. Chứng minh: Giả sử ngược lại, cứ hai thành phố bất kì trong 4 thành phố $A,B,C,D $ thì có 1 con đường một chiều. Không mất tính tổng quát, ta xét 3 thành phố $A,B,C $. Theo nhận xét 1, chiều của các con đường trong 3 thành phố này là $A\rightarrow B\rightarrow C $ hoặc ngược lại. Không mất tổng quát xem hướng của chúng là $A\rightarrow B\rightarrow C $. Xét thành phố $D $. Nếu có $D\rightarrow A $ thì sẽ không có $C\rightarrow D $. Tức là sẽ phải có $D\rightarrow C $. Nhưng khi đó ta có $D\rightarrow C \rightarrow A $ và $D\rightarrow A $ nên không thỏa mãn. Vai trò của $A,B,C $ như nhau nên ta cũng không có $D\rightarrow B $ hay $D\rightarrow C $. Như vậy thì ta phải có $A\rightarrow D, B\rightarrow D $ và $C\rightarrow D $. Nhưng khi đó $A\rightarrow B\rightarrow D $ và $A\rightarrow D $ nên cũng không thỏa mãn. Vậy điều giả sử là sai. Bổ đề được chứng minh. Trở lại bài toán. Với bổ đề thì ta sẽ có 4 thành phố bất kì thì có hai thành phố không được nối với nhau bởi một con đường ( hướng tùy ý). Áp dụng định lý Turan ta có tổng số con đường không vượt quá $(1-\frac{1}{3})\frac{n^2}{2} = \frac{210^2}{3} $. Xét một cách xây đường như sau: Chia 210 thành phố thành 3 nhóm $X,Y,Z $ mỗi nhóm có 70 thành phố. Ta xây các con đường từ mỗi thành phố trong nhóm X, đến mỗi thành phố trong nhóm Y. Tương tự Y đến Z và Z đến X. Tổng số con đường được xây là $3\times 70^2 = \frac{210^2}{3} $. Dễ thấy là cách xây này thỏa mãn điều kiện bài toán. Kết luận: $\frac{210^2}{3} $. __________________ Traum is giấc mơ.