[Mashimaru]

Nguyên văn bởi namdung

OK. Tuy nhiên vì đây là đường 1 chiều nên phải hiểu là: nếu có đường đi từ A --> thì không có đường đi từ B đến A nữa.

Dạ, nếu vậy thì vẫn có thể dựa vào định lý Mantel-Turan, nhưng trong trường hợp tổng quát hơn:
Định lý. Đồ thị vô hướng $n $ đỉnh không có $k $-clique thì có không quá $[\frac{(k-2)n^2}{2(k-1)}] $ cạnh.

Chứng minh của định lý vẫn dựa vào quy nạp và ta vẫn có chú ý rằng có thể dựng đồ thị vô hướng $n $ đỉnh, $[\frac{(k-2)n^2}{2(k-1)}] $ cạnh và không có $k $-clique.

Với bài toán, trước hết ta cũng vô hướng hoá đồ thị các đường đi và thành phố để tạo ra đồ thị $G $. Nhận xét rằng $G $ không chứa 4-clique. Thật vậy, giả sử $G $ có 4-clique với các đỉnh $A, B, C, D $. Dễ thấy trước khi vô hướng hoá, trong $A, B, C, D $ có một đỉnh vừa có cung vào vừa có cung ra (giả sử mỗi đỉnh chỉ có cung vào hoặc ra, vậy nếu $A $ có 3 cung ra thì $B, C, D $ phải có toàn cung vào, và ngược lại, vô lý khi ta xét đồ thị con cảm sinh bởi $B, C, D $). Vậy giả sử trong $G $ có các cung $AB $ và $BC $. Theo giả thiết thì trong $G $ phải có cung $CA $. Xét định hướng cạnh $AD $:
1. Nếu ta định hướng $AD $ thì xét tam giác $ABD $, do đã có các cung $AB $ và $AD $ nên cạnh $BD $ định hướng thành cung $BD $ hay $DB $ đều gây ra mâu thuẫn.
2. Nếu ta định hướng $DA $ thì xét tam giác $ABD $, đo dã có các cung $DA $ và $AB $ nên phải có cung $BD $. Lúc này đều vô lý như trường hợp 1 xảy ra với tam giác $BCD $ đã định hướng các cung $BC $ và $BD $.
Vậy trong vô hướng hoá của $G $ không có 4-clique. Theo định lý Mantel-Turan, $G $ theo ý nghĩa của đề bài (định hướng mỗi cạnh thành 1 trong 2 cung có thể) có không quá $[\frac{(4-2)\cdot 210^2}{2(4 - 1)}] = \frac{210^2}{3} $ cung.

Ta cũng có thể xây dựng $\frac{210^2}{3} $ dựa trên hình ảnh của đồ thị 3 phía. Thậy vậy, phân hoạch tập đỉnh của $G $ thành $A[1..70], B[1..70] $ và $C[1..70] $. Xét tập cung $E(G) = \{A_iB_j, B_jC_k, C_kA_i 1 \leq i, i, k \leq 70\} $, dễ thấy chúng có $3 \cdot 70^2 = \frac{210^2}{3} $ cung (với mỗi bộ $B_iC_j $ tạo ra 3 cung).

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

Viết xong em mới thấy bài của anh Traum

Mình xin đóng góp một bài cho các bạn sắp đi thi luyện tập. Đây là bài luyện Putnam của trường mình. Vì viết sau thầy Nam Dũng nên mình đặt đây là bài 5 vậy.

5. Cho $\{a_1, \cdots, a_n\} $ và $\{b_1, \cdots, b_n\} $ là các dãy số nguyên dương thoả mãn đồng thời các điều kiện: $a_1 < a_2 < \cdots < a_n $, $b_1 > b_2 > \cdots > b_n $, và $\{a_1, \cdots, a_n, b_1, \cdots, b_n\} = \{1, 2, \cdots 2n\} $. Chứng minh rằng $\sum_{i = 1}^{n} |a_i - b_i| = n^2 $.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]