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

[E. Galois]

Vào hồi 20h00, Thứ Sáu, ngày 07/02/2014, Tổ trọng tài sẽ ra đề vào topic này, sau khi có đề, các toán thủ bắt đầu thi đấu.
 

 

I- Bạn cần biết:

1) Điều lệ giải đấu

2) Lịch thi đấu và kết quả

 

 

II - Lưu ý

1) Các toán thủ khi thi đấu, cứ yên tâm rằng, sau khi trả lời là bài làm đã được lưu, BTC đã nhận được bài làm của bạn, có điều bạn không nhìn thấy được mà thôi. Bạn nên mừng vì điều này, như thế các toán thủ khác không thể copy bài của bạn được.

Bạn cũng nên sử dụng chức năng xem trước của diễn đàn để sửa các lỗi LATEX trước khi gửi bài, vì gửi rồi sẽ không xem và sửa lại được nữa.

 

 

Để sử dụng chức năng xem trước, bạn click vào Sử dụng bộ soạn thảo đầy đủ và chọn Xem trước.

 

2) Các toán thủ chớ quên rằng mỗi một mở rộng đúng sẽ được 10 điểm, các bạn nên mở rộng bài toán để thu được nhiều điểm hơn

 

3) Thành viên diễn đàn không đăng kí thi đấu vẫn có thể giải bài, nhưng phải ghi rõ là: Mình không phải là toán thủ thi đấu

 

4) Trận 3 sẽ loại 1 toán thủ có số điểm thấp nhất

[E. Galois]

Đề bài của LNH

 

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?

[hoangtrunghieu22101997]

Bài làm

Xét thành phố A bất kỳ

Gọi $S_1$ là tập hợp các thành phố mà có đường đi từ A đến

 

$S_2$ là tập hợp các thành phố mà có đường đi nơi đó đến A

 

$S_1$ là tập hợp các thành phố không có đường nối trực tiếp đến A

Do có 210 thành phố nên $|S_1|+|S_2|+|S_3|=209$

Nhận thấy các thành phố thuộc $S_1 $ không có đường đi trực tiếp với nhau.
Tương tự với $S_2$
Nhưng số đường đi giữa thành phố thuộc $S_1$ với thành phố thuộc $S_2$ nhỏ hơn hoặc bằng $|S_1|.|S_2|$

Số các đường đi giữa các thành phố thuộc tập $S_3$ không quá $|S_3|(|S_1|+|S_2|)$

Như vậy tổng số đường đi lớn nhất là:
$|S_1|+|S_2|+|S_1|.|S_2|+|S_3|(|S_1|+|S_2|)$
$=|S_1|.|S_2|+(|S_3|+1)|S_1|+(|S_3|+1)S_2$
$\le \dfrac{(|S_1|+|S_2|+|S_3|+1)^2}{3}=14700$

Dấu bằng có xảy ra nếu như có 70 thành phố thuộc nhóm I ;70 thành phố thuộc nhóm II ;70 thành phố thuộc nhóm III
Sao cho thành phố nhóm I có đường đến nhóm II ; nhóm II có đường đến nhóm II và nhóm III có đường đến nhóm I

Bài viết đã được chỉnh sửa nội dung bởi TRONG TAI: 12-02-2014 - 23:47

[Tru09]

Bài Làm :
Gọi A là thành phố có nhiều đường đi +đường đi đến nhất 

Gọi tập các thành phố có đường đi từ A đến là X . Có x phần tử

Gọi tập các thành phố đi đến A là Y .Có y phần tử

Gọi tập các thành phố không đến cũng không đi đến A là Z . Có z phần tử.

Khi đó $x+y+z =209$

Nếu tồn tại 1 đường đi trong tập X thì vô lý

Nếu tồn tại 1 đường đi trong tập Y cũng vô lý

Do A là thành phố có nhiều đường đi và đi đến nhất nên x+y >x+z và x+y >y+z

Nên để có nhiều đường đến nhất thì các thành phố ở Z liên kết với các thành phố ở X,Y 

Vậy Số các đường đi liên quan đến Z không quá z(x+y)

Các đường đi giữa X,Y là xy

Vậy tổng số đường đi là  $xy+ z(x+y) +x+y  =yx +x(z+1) +(z+1)y \leq (x+y+z+1)^2 =\frac{210^3}{3}$ ( theo bunia )

Dấu = xảy ra khi x=y=z+1 Khi A đi đến 70 thành phố  , và bị 70 thành phố khác đi đến . Các thành phố đi đến và bị đi đến A đều đi đến và bị đến 69 thành phố còn lại

Bài viết đã được chỉnh sửa nội dung bởi TRONG TAI: 12-02-2014 - 23:46

[nhatquangsin]

Xét đồ thì $210$ đỉnh.

Gọi $A$ là thành phố có nhiều đường đi nhất. Khi đó ta xét các trường hợp sau:

-Hai thành phố $B$ và $C$ có đường đi từ $A$ đến: không thể có đường giữa hai thành phố.$(1)$

-Hai thành phố $B$ và $C$ cùng có đường đến $A$: không thể có đường giữa hai thành phố.$(2)$

-Hai thành phố $B$ và $C$ có đường từ $A$ đến $B$ và từ $C$ đến $A$ thì có đường từ $B$ đến $C$ và không có đường ngược lại.

Đặt số thành phố có đường từ $A$ đến là $a$, số thành phố có đường đến $A$ là $b$, các thành phố không có đường đến $A$ cũng không có đường từ $A$ là $c$.

Khi đó ta có $a+b+c=209$.

Theo $(1)$ và $(2)$ thì các thành phố có đường từ $A$ đến và từ $A$ đi sẽ không có đường nối tới nhau. Xét đồ thị $210$ đỉnh thì $A$ là đỉnh có bậc cao nhất là $a+b$. Do đó số thành phố không liên quan đến $A$ phải có số đỉnh nhỏ hơn hoặc bằng $a+b$. Gọi $S_1$ là số đường đi của các thành phố này thì vì có $c$ thành phố như vậy nên $S_1\leq c(a+b)$.

Gọi $S_2$ là số đường tới $A$ thì $S_2=a+b$. Gọi $S_3$ là số đường giữa các thành phố còn lại thì vì trong $a$ thành phố có đường từ $A$ và $b$ thành phố có đường đến $A$ có thể có đường nối nhau nên số đường lớn nhất có thể là $ab$.

Vậy số đường đi là $S=S_1+S_2+S_3\leq ab+a+b+(a+b)c=ab+c(a+1)+c(b+1)\leq \frac{(a+b+c+1)^2}{3}=14700$

Dấu = xảy ra khi $a=b=c+1$ tức ta cần xây dựng $70$ thành phố có đường từ $A$ đến các đỉnh, $70$ thành phố có đường đến $A$ và các đỉnh còn lại xây dựng tương tự điểm $A$.

Bài viết đã được chỉnh sửa nội dung bởi TRONG TAI: 12-02-2014 - 23:46

[VodichIMO]

Goi $A$ là thành phố có nhiều đường đi nhất (gồm cả đường đi xuất phát từ $A$ và đường đi đến $A$ ). Ta chia các thành phố còn lại thành $3$ loại. Loại $I$: Có đường đi xuất phát từ $A$. Loại $II$: Có đường đi đến $A$. Loại $III$: Không có đường đi đến $A$ hoặc xuất phát từ $A$.

Đặt $m=|I|;n=|II|;p=|III|$. Ta có $m+n+p=209$

Dễ thấy giữa các thành phố loại $I$ không có đường đi. Tương tự, giữa các thành phố loại $II$ không có đường đi

Số các đường đi liên quan đến thành phố loại $III$ không vượt quá $p(m+n)$ (Do bậc của $A=m+n$ là lớn nhất).

Tổng số đường đi bao gồm:

+ Các đường đi liên quan đến $A:m+n$

+ Các đường đi liên quan đến $III\leq p(m+n)$

+ Các đường đi giữa $I$ và $II$ $\leq$ $mn$.

Suy ra tổng các đường đi nhỏ hơn:

$mn+m(p+1)+n(p+1)\leq\frac{(m+n+p+1)^2}{3}=\frac{210^2}{3}$

Dấu bằng xảy ra với đồ thị $3$ phe, mỗi phe có $70$ thành phố , thành phố phe $1$ có đường đi đến thành phố phe $2$, thành phố phe $2$ có đường đi đến thành phố phe $3$, thành phố phe $3$ có đường đi đến thành phố phe $1$

[henry0905]

Ta xét một thành phố bất kỳ, không mất tính tổng quát giả sử đó là thành phố A.

Chia 209 các thành phố còn lại thành 3 nhóm:

+Nhóm có đường vào A có số đường đi là a (nhóm 1)

+Nhóm có đường từ A đi có số đường đi là b (nhóm 2)

+Nhóm không liên quan đến A có số đường đi là c (nhóm 3)

Giữa các thành phố nhóm 1 không có đường đi: Giả sử A đến B, A đến C thì (B đến C) hay (C đến B) đều mâu thuẫn với giả thiết.

Tương tự ở nhóm 2 cũng không có đường giữa các thành phố.

Xét nhóm 3: Số các đường đi của nhóm 3 không lớn hơn c(a+b); do A có a+b đường đi)

Số các đường đi giữa nhóm 1 và nhóm 2 là ab

Do đó tổng số đường đi bằng: $a+b+ab+c(a+b)=ab+a(c+1)+b(c+1)\leq \frac{(a+b+c+1)^{2}}{3}=\frac{210^{2}}{3}= 14700$

Dấu "=" xảy ra khi a=b=c+1 $\Leftrightarrow$ $\begin{pmatrix} a=70 & & \\ b=70 & & \\ c=69 & & \end{pmatrix}$

Hay mỗi nhóm có 70 thành phố, nhóm 1 có đường đến nhóm 2, nhóm 2 có đường đến nhóm 3 và nhóm 3 có đường đến nhóm 1.

 

[nhatquangsin]

Em xin bổ sung một chút bài làm:

Ta xây dựng $70$ thành phố có đường đến $A$, $70$ thành phố có đường từ $A$ đến và xây dựng các đỉnh còn lại tương tự $A$. Ngoài ra ở mỗi thành phố trong $70$ có đường từ $A$ đến thì ta cũng xây dựng các đường đến $70$ thành phố có đường đến $A$ với mỗi một đỉnh như vậy.

[dinhthanhhung]

Quy ước : đường xuất phát từ thành phố X đến thành phố Y gọi là đường đi đối với thành phố X và là đường kết đối với thành phố Y ( X đi , Y kết ) .

 

Lời giải :

Ta xét thành phố H có nhiều đường đi nhất ( giả sử có $x$ đường đi và $y$ đường kết thì có $x$ thành phố kết , $y$ thành phố đi) .

Theo giả thiết thì trong hai thành phố bất kỳ mà H đi  ( hoặc kết ) thì không có con đường nào nối .

Chọn một thành phố mà H đi và một thành phố mà H kết thì giữa chúng có thể có ( một và chỉ một ) đường nối nên số đường nhiều nhất tạo được là $xy$ .

Bây giờ ta xét một trong $z$ thành phố mà không có đường đi và kết H thì có thể xây tối đa $x+y$ đường nối nên số đường nhiều nhất là $z(x+y)$

Tổng số đường xây nhiều nhất là $A=x+y+xy+z(x+y)$ và thêm đó $x+y+z+1=210$

Theo BDT quen thuộc : $A=xy+y(z+1)+(z+1)x\leq \frac{(x+y+z+1)^2}{3}=\frac{210^3}{3}$

Dấu bằng xảy ra với cách xây như sau : có 3 nhóm thành phố A,B,C , mỗi nhóm 70 . Mối thành phố ở nhóm A có đường đi tới thành phố nhóm B , mối thành phố ở nhóm B có đường đi tới mỗi thành phố nhóm C và mối thành phố ở nhóm C có đường đi tới thành phố nhóm A .

[maitienluat]

Bài làm :

 

Gọi $X$ là thành phố có nhiều đường đi liên quan nhất ( theo nghĩa tổng số đường đi từ $X$ đến thành phố khác và từ thành phố khác đến $X$ là lớn nhất ).

Ta chia $209$ thành phố còn lại làm $3$ nhóm : Nhóm $A$ gồm tất cả các thành phố có đường đi một chiều tới $X$, nhóm $B$ gồm các thành phố mà từ $X$ có đường đi một chiều tới và nhóm $C$ bao gồm các thành phố còn lại (trừ X). Đặt $a,b,c$ lần lượt là số phần tử của $A, B, C$. Khi đó, số đường đi có liên quan tới $X$ là $a+b$ và $a+b+c =209$.

Ta có một số nhận xét sau

$\bullet$ Giữa các thành phố cùng thuộc nhóm A không có đường đi nối với nhau.

  C/minh: giả sử $A_1,A_2$ là 2 thành phố cùng thuộc $A$ sao cho có đường đi nối giữa $A_1$ và $A_2$, không mất tổng quát giả sử đó là đường đi từ $A_1$ tới $A_2$. Khi đó có đường đi từ $A_1$ tới $A_2$ và từ $A_2$ tới $X$, nên theo giả thiết không có đường đi từ $A_1$ tới $X$, vô lí vì $A_1 \in A $

  Tuơng tự, giữa các thành phố cùng thuộc nhóm B không có đường đi nối với nhau.

  Từ đó, số đường đi nối giữa các thành phố thuộc $A$ và $B$ không lớn hơn $ab$.

$\bullet$ Số đường đi liên quan tới các thành phố thuộc nhóm $C$ không lớn hơn $c(a+b)$.

   Thật vậy, vì nếu ngược lại thì theo nguyên lí Đirichlet tồn tại một thành phố thuộc $C$ có số đường đi liên quan lớn

hơn $a+b$, mâu thuẫn với cách chọn $X$.

Từ các nhận xét trên ta suy ra số con đường có thể xây dựng không lớn hơn: $a+b+ab+c(a+b)$.

Ta có $P = a+b+ab+c(a+b) \leq a+b+\frac {(a+b)^2} {4} + (209 -a-b)(a+b) = 2d + d^2+2d(209 -2d) = - 3(d-70)^2 +  3.70^2 \leq 14700$.

(với $d= \frac {a+b} {2} $)

Ta chỉ ra một cách xây dựng đường đi thoả mãn yêu cầu bài toán. 

Chia $210$ thành phố thành 3 nhóm $A,B,C$, mỗi nhóm có 70 thành phố. Với mỗi bộ ba thành phố $X,Y,Z$ với $X \in A, Y \in B, Z \in C$ thì ta xây dựng đường đi theo quy tắc $X \Rightarrow Y \Rightarrow Z \Rightarrow X$. Dễ thấy cách xây dựng này thoả yêu cầu bài. Khi đó số bộ thành phố là $70^3$, với mỗi bộ có $3$ con đường được xây và mỗi con đường được tính lặp lại $70$ lần nên số đường đi là $3.70^2=14700$.

Tóm lại, số đường đi nhiều nhất có thể là $14700$

[gk25dtm]

Gọi A là thành phố nhiều đường đi nhất ( tính cả xuất phát và đi đến )

Ta chia các thành phố còn lại làm 3 phần 

Phần 1 : có đường xuất phát từ A , phần 2: có đường đi đến A , phần 3 : không liên quan đến A

đặt $ x = | 1 | , y = | 2 | , z=| 3 | $ . Ta có : $x+y+z=209$

Rõ ràng giữa các thành phố trong loại 1 và 2 không có đường đi đến nhau

Suy ra , các đường đi liên quan đến A : $m+n$

Lưu ý rằng : các đường đi giữa 1 và 2 $ \leq mn $ 

và các đường đi liên quan đến các thành phố loại 3 $\leq  p(m+n ) $

Vậy , tông số đường đi nhỏ hơn 

 $mn+ (p+1)m + (p+1)n  \leq ( m+n+p+1)^{\frac{2}{3}} = 210^{\frac{2}{3}} $

Dấu đẳng thức xảy ra đối với đồ thị 3 nhóm , mỗi nhóm có 70 thành phố , thành phố nhóm 1 có đường đi đến thành phố nhóm 2 , thành phố nhóm 2 có đường đi đến thành phố nhóm 3, thành phố nhóm 3 có đường đi đến thành phố nhóm 1

[maitienluat]

Mở rộng 1: Ta sẽ thay số thành phố $210$ bới $n=3k$ bất kì.

Với lập luận tương tự như trong bài làm, ta có số con đường một chiều có thể xây dựng không vượt quá $P=a+b+ab+c(a+b)$ với $a+b+c=n-1$.

Đặt $d= \frac {a+b} {2}$, ta có:

$P=a+b+ab+c(a+b) \leq 2d+d^2+(n-1-2d).(2d) = -3d^2+2nd = -3(d-k)^2+3k^2 \leq 3k^2$

Ta chỉ ra một cách xây dựng cấu hình có $3k^2$ đường đi.

Chia $n$ thành phố thành 3 nhóm $A,B,C$, mỗi nhóm gồm $k$ thành phố. Với mỗi bộ ba thành phố $X,Y,Z$ với $X \in A, Y \in B, Z \in C$, ta xây dựng đường một chiều theo quy tắc $X \Rightarrow Y \Rightarrow Z \Rightarrow X$. Dễ thấy cách xây này thoả mãn yêu cầu và có số đường đi là $3k^2$ (có $k^3$ bộ thành phố, ứng với mỗi bộ có $3$ đường một chiều, trong đó mỗi con đường được tính đúng $k$ lần).

Tóm lại, số con đường đi nhiều nhất có thể xây dựng với $n=3k$ thành phố là $3k^2$.

[nguyenqn1998]

Đề bài của LNH

 

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?

Gọi A là thành phố có nhiều đường đi nhất.

Khi đó ta chia các thành phố còn lại thành 3 nhóm sao cho:

+Nhóm 1: có đường đi xuất phát từ A 

+Nhóm 2: có đường đi đến A

+Nhóm 3:không có đường đi đến A hoặc xuất phát từ A

Gọi $a$ là số thành phố của nhóm 1

       $b$ là số thành phố của nhóm 2

       $c$ là số thành phố của nhóm 3

Khi đó ta có $a+b+c=209$

Theo giả thiết thì không có đường đi giữa các thành phố trong nhóm và nhóm 2

Số các đường đi liên quan đến các thành phố nhóm 3 không vượt quá c(a+b) (Do bậc của $A=a+b$ lớn nhất)

Khi đó tổng số đường đi bao gồm:

+Số đường đi liên quan đến A: $a+b$

+Số đường đi liên quan đến các thành phố trong nhóm 3: $\leq c(a+b)$ 

+Số đường đi giữa nhóm 1 và 2: $\leq a.b$

Suy ra tổng số đường đi nhỏ hơn:

$ab+a+b+c(a+b)=ab+a(c+1)+b(c+1) \geq \frac{(a+b+c+1)^2}{3}=\frac{210^2}{3}$ (Theo AM-GM)

Dấu "=" xảy ra khi đồ thị có 3 nhóm, mỗi nhóm có 70 thành phố, thành phố nhóm 1 có đường đi đến thành phố nhóm 2, thành phố nhóm 2 có đường đi đến thành phố nhóm 3,thành phố nhóm 3 có đường đi đến thành phố nhóm 1 

[maitienluat]

Mở rộng 2: Tổng quát cho số thành phố là $n \geq 3$ bất kì

Ta chỉ cần giải quyết cho trường hợp $n=3k+1$ và $n=3k+2$

Tương tự như bài làm và mở rộng 1, ta có số đường đi không vượt quá $P=a+b+ab+c(a+b)$ với $a+b+c=n-1$

Và $P \leq -3d^2 + 2dn$ với $d=\frac {a+b} {2}$

Xét $n=3k+1$.

Ta có $-3d^2+2dn=-3(d- \frac {n} {3})^2 +\frac {n^2} {3} \leq \frac {n^2} {3} = \frac {9k^2+6k+1} {3} = 3k^2+2k+\frac {1} {3}$

Do $a,b,c$ nguyên nên $P$ nguyên, suy ra $P \leq 3k^2+2k$

Ta chỉ ra một cách xây dựng đường đi.

Chia $3k+1$ thành phố thành 4 nhóm $A,B,C,D$ với các nhóm $A,B,C$ đều có $k$ thành phố và nhóm $D$ có 1 thành phố $M$, Với bộ 3 thành phố $X,Y,Z$ trong đó $X \in A, Y \in B, Z \in C$ ta xây dựng đường đi theo quy tắc $X \Rightarrow Y \Rightarrow Z \Rightarrow X$. Sau đó ta xây dựng đường đi từ mọi thành phố thuộc nhóm $A$ tới thành phố $M$ và từ thành phố $M$ tới mọi thành phố thuộc nhóm $C$.Dễ thấy cách xây dựng này thoả mãn và có đúng $3k^2+2k$ đường đi.

Xét $n=3k+2$.

Tương tự như trường hợp $n=3k+1$, ta có $-3d^2+2dn \leq 3k^2+4k+ \frac {4} {3}$, nên $P \leq 3k^2+4k+1$.

Ta chỉ ra một cách xây dựng.

Chia $3k+2$ thành phố thành 4 nhóm $A,B,C,D$ với các nhóm $A,B,C$ đều có $k$ thành phố và nhóm $D$ có 2 thành phố $M$ và $N$. Với bộ 3 thành phố $X,Y,Z$ trong đó $X \in A, Y \in B, Z \in C$ ta xây dựng đường đi theo quy tắc $X \Rightarrow Y \Rightarrow Z \Rightarrow X$. Sau đó ta xây dựng đường đi từ mọi thành phố thuộc nhóm $A$ tới thành phố $M$ và từ thành phố $M$ tới mọi thành phố thuộc nhóm $C$. Ta tiếp tục xây dựng đường đi từ mọi thành phố thuộc nhóm $C$ đến $N$, từ $N$ đến mọi thành phố thuộc nhóm $B$ và từ $N$ đến $M$. Dễ kiểm tra cách xây này thoả và có đúng $3k^2+4k+1$ đường đi.

Tóm lại, trong mọi trường hợp, số đường đi lớn nhất có thể là $\left \lfloor \frac{n^2}{3} \right \rfloor$ , ở đó $n$ là số thành phố.

 

 

[Tru09]

Mở Rộng 1 :Một quốc gia có n ($n \vdots 3$) 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?

Bài làm

Gọi A là thành phố có nhiều đường đi +đường đi  đến 

Gọi tập X là tập các thành phố mà thành phố A đi đến . Có x phần tử

Gọi tập các thành phố đi đến A là Y .Có y phần tử

Gọi tập các thành phố không đến cũng không đi đến A là Z . Có z phần tử.

Khi dó $x+y+z =n-1$

Nếu tồn tại 1 đường đi trong tập X thì vô lý

Nếu tồn tại 1 đường đi trong tập Y cũng vô lý

Do A là thành phố có nhiều đường đi và đi đến nhất nên x+y >x+z và x+y >y+z

Nên để có nhiều đường đến nhất thì các thành phố  Z liên kết với các thành phố  X,Y 

Vậy Số các đường đi liên quan đến Z không quá z(x+y)

Các đường đi giữa X,Y là xy

Vậy tổng số đường đi là  $xy+ z(x+y) +x+y  =yx +x(z+1) +(z+1)y \leq \frac{(x+y+z+1)^2}{3} =\frac{n^2}{3}$ ( theo bunia )

Dấu = xảy ra khi x=y=z+1 Khi A đi đến $\frac{n}{3}$ thành phố  , và $\frac{n}{3}$ thành phố khác đi đến . Các thành phố đi đên và bị A đi đến đều đi đến và bị các thành phố còn lại đi đến

-------------

p/s Bài làm e viết lộn 1 tí ở phần bunia :3 , em sửa thành  $\frac{(x+y+z+1)^2}{3} =\frac{210^2}{3}$ . Em rất xin lỗi về sự nhầm lẫn trên

[thuan192]

Lời giải:

Gọi A là thành phố có nhiều đường đi nhất (gồm cả đường đi xuất phát từ A và đường đi đến A). Ta chia các thành phố còn lại thành ba loại: loại I có đường đi xuất phát từ A; loại II có đường đi đến A; lọa III không có đường đi xuất phát từ A và đường đi đến A. Đặt $m=\left | I \right |,n=\left | II \right |,p=\left | III \right |$. Ta có m+n+p=209

Dễ thấy thành phố loại I không có đường đi. Tương tự các thành phố loại II không có đường đi 

Số các đường đi liên quan đến các thành phố loại 3 không vượt quá p(m+n). (Do bậc của A = m + n là lớn nhất). 

Tổng số đường đi bao gồm: 

+ Các đường đi liên quan đến A: m + n 

+ Các đường đi liên quan đến III : $\leq p(m+n)$

+ Các đường đi giữa I và II: $\leq m.n$

Suy ra tổng số đường đi nhỏ hơn $mn+\left ( p+1 \right )m+\left ( p+1 \right )n\leq \frac{\left ( m+n+p+1 \right )^{2}}{3}=\frac{210^{2}}{3}$

. Dấu bằng xảy ra với đồ thị 3 phe, mỗi phe có 70 thành phố, thành phố phe 1 có đường đi 

đến thành phố phe 2, thành phố phe 2 có đường đi đến thành phố phe 3, thành phố phe 3 

có đường đi đến thành phố phe 1. 

[PTKBLYT9C1213]

Bài làm của MO26:

Gọi M là thành phố có nhiều con đường đi và đến nhất. Các thành phố còn lại chia làm 3 loại:

Loại 1: Các thành phố có đường đi từ M đến , giả sử có a thành phố  

Loại 2: Các thành phố có đường đi đến M, giả sử có b thành phố

Loại 3: Các thành phố còn lại, giả sử có c thành phố.

Theo giả thiết ta có a + b + c = 209.

Vì nếu có đường đi từ thành phố A đến thành phố B và từ thành phố B đến thành phố C thì không có đường đi từ thành phố A đến thành phố C nên các thành phố trong loại 1 sẽ không có đường nối với nhau, các thành phố trong loại 2 sẽ không có đường nối với nhau.

Suy ra số đường nối M với các thành phố trong loại 1 là a đường, trong loại 2 là b đường.        

Mặt khác, ta cũng có mỗi thành phố trong loại 1 sẽ nối với mỗi thành phố trong loại 2 nên số đường nhiều nhất là $ab$ đường

Mỗi thành phố trong loại 3 có thể nối với a thành phố trong loại 1 và b thành phố trong loại 2 nên số đường nhiều nhất là $c(a+b)$ đường

Suy ra số đường nhiều nhất có thể xây là a + b + ab + c(a+b).

Ta có: $a+b+ab+c(a+b)=ab+a(c+1)+b(c+1)\leq \frac{(a+b+c+1)^{2}}{3}=\frac{210^{2}}{3}=14700$

Dấu "=" xảy ra khi a = b = 70, c = 69

Vậy số đường nhiều nhất có thể xây là 14700 đường

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

  

 

 

[PTKBLYT9C1213]

Mở rộng 1. 210 thành phố chỉ là một số cụ thể, ta có thể tổng quát bài toán thành n thành phố và các giả thiết khác không thay đổi, với cách làm tương tự ta được kết quả là (n^2)/3
Mở rộng 2: một quốc gia có n thành phố, người ta muốn xây đường một chiều giữa các thành phố sao cho: nếu có đường đi từ A đến B và từ C đến A thì không có đường đi từ B đến C. Hỏi có thể xây được nhiều nhất bao nhiêu đường?
Mở rộng 3: Một quốc gia có n thành phố, người ta muốn xây đường giữa các thành phố sao cho: Nếu có đường từ a1 đến a2 và từ a2 đến a3 thì không có đường từ a1 đến a3, nếu có đường từ a1 dđến a2, a2 đến a3, a3 đến a4 thì ko có đường a1 đến a4, nếu có đường từ a1 đến a2, a2 đến a3, a3 đến a4, a4 đến a5, a5 đến a6 thì ko có đường a1 đến a6,.... hỏi xây nhiều nhất bao nhiêu đường.
Đáp số vẫn là (n^2)/3 vì điều kiện đầu đã bao gồm tất cả điều kiện sau

[nguyenqn1998]

Cách 2: 

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->B->C$hoặc $C->B->A$.(Hiển nhiên đúng)
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->B->C$ hoặc ngược lại. Không mất tổng quát xem hướng của chúng là $A->B->C$. Xét thành phố $D$. Nếu có $D->A$ thì sẽ không có $C->D$. Tức là sẽ phải có $D->C$. Nhưng khi đó ta có $D->C->A$ và $D->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->B$hay $D->C$. Như vậy thì ta phải có $A->D,B->D$ và $C->D$. Nhưng khi đó $A->B->D$ và $A->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}=210^2.(với $n=210$)
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.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.

 

[gk25dtm]

mở rộng  :

thay 210 = 3n , giải tương tự như bài trên