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

Mashimaru · 18-02-2012, 10:14 AM

Trích:

Nguyên văn bởi namdung

3. (Trận đấu toán học Nga 2010, khó) Một quốc gia có 210 thành phố. Ban đầu giữa các thành phố chưa có đường. Người ta muốn xây dựng một số con đường một chiều nối giữa các thành phố sao cho: Nếu có đường đi từ A đến B và từ B đến C thì không có đường đi từ A đến C.Hỏi có thể xây dựng được nhiều nhất bao nhiêu đường?

Em nghĩ ý của bài này là dựa vào định lý Mantel-Turan (không biết có đúng không ạ):
Định lý. Đồ thị vô hướng $n $ và có hơn $[\frac{n^2}{4}] $ cạnh thì có tam giác.

Quan sát định lý, ta nhận thấy có thể xây dựng đồ thị vô hướng $n $ đỉnh với $[\frac{n^2}{4}] $ cạnh mà không có tam giác. Thật vậy, ta quy nạp: với $n = 1, 2 $ thì nhận xét đúng. Giả sử nhận xét với $n $, ta xét $n+2 $. Để ý rằng $[\frac{(n+2)^2}{4}] = [\frac{n^2}{4}] + n + 1 $. Trước hết chọn ra hai đỉnh A, B rồi dùng giả thiết quy nạp, ta xây dựng đồ thị $[\frac{n^2}{4}] $ cạnh với $n $ đỉnh còn lại. Sau đó, với mỗi đỉnh còn lại, nối chúng với đúng một trong hai đỉnh $A, B $, đồng thời nối $A, B $ với nhau, ta có thêm $n + 1 $ cạnh. Chú ý rằng với hai đỉnh $X, Y $ khác $A, B $, mà trong đồ thị có cạnh $XY $, vì ta nối $AB $, nên nếu nối $XA $ thì phải nối $YB $. Tuy nhiên đều này không gây ra mâu thuẫn, vì giả sử có 3 đỉnh $X, Y, Z $ khác $A, B $ mà có các cạnh $XY, XZ $ (thì không có $YZ $), và ta có thể nối $XA, YA, ZB $. Nhận xét được chứng minh.

Xem xét trường hợp đồ thị có hướng $n $ đỉnh, ta thấy có thể xây dựng $2[\frac{n^2}{4}] $ cạnh (mỗi cạnh vô hướng làm thành 2 cung có hướng).

Mặt khác, ta chứng minh không thể có nhiều cạnh hơn thế được. Thật vậy, ta vẫn sử dụng quy nạp. Với $n = 3,4 $ ta có thể kiểm tra trực tiếp. Giả sử kết luận này đúng với $n $, xét đồ thị $G $ có hướng $n + 2 $ đỉnh với $2[\frac{(n + 2)^2}{4}] + 1 = 2[\frac{n^2}{4}] + 2n + 3 $ cạnh.
Nếu trong $G $ có 2 đỉnh $A, B $ sao cho có các cung $AB $ và $BA $ thì do giả thiết quy nạp, đồ thị con của $G $ cảm sinh bởi $n $ đỉnh còn lại chỉ có tối đa $2[\frac{n^2}{4}] $ cạnh, hơn nữa mỗi đỉnh $X $ trong số $n $ đỉnh này chỉ có thể tạo 2 cạnh trong số 4 cạnh $AX, XA, BX, XB $ (do nếu có $AX $ thì không có $BX $, cũng như nếu có $XA $ thì không có $XB $ và ngược lại), do vậy tổng số cạnh của $G $ không vượt quá $2[\frac{n^2}{4}] + 2n + 2 $ (các cạnh trong $n $ đỉnh còn lại, các cạnh nối giữa chúng với $A, B $, $AB $ và $BA $).
Nếu $G $ không có hai đỉnh $A, B $ nào như nói trên (tức nếu có cung $AB $ thì không có cung $BA $), ta chọn 2 đỉnh $A, B $ sao cho trong đồ thị có cung $AB $. Theo giả thiết đồ thị con cảm sinh bởi $n $ đỉnh còn lại của $G $ (ngoài $A, B $) có tối đa $2[\frac{n^2}{4}] $ cạnh, đồng thời mỗi đỉnh $X $ trong số $n $ đỉnh này chỉ tạo 1 cạnh với $A $ hoặc 1 cạnh với $B $ (bởi nếu có cung $XA $ thì không có cung $AX $, cũng như có cung $XB $ thì không có cung $BX $ và ngược lại). Vậy tổng số cạnh của $G $ không vượt quá $2[\frac{n^2}{4}] + 2n + 1 $ (gồm các cạnh trong $n $ đỉnh còn lại, các cạnh nối chung với $A, B $, và $AB $), ta cũng gặp điều vô lý. Tóm lại nhận xét này cũng được chứng minh.

Vậy kết quả của bài toán là $2[\frac{210^2}{4}] $.