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

[marsu]

Trên bờ một biển hồ hình tròn có $2n$ thành phố $(n \geq 2)$. Giữa hai thành phố tùy ý có thể có hoặc không có đường thủy nối trực tiếp với nhau. Người ta nhận thấy rằng đối với $2$ thành phố $A$ và $B$ bất kì thì giữa chúng có đường thủy nối trực tiếp với nhau khi và chỉ khi giữa các thành phố $A$' và $B'$ không có đường thủy nối trực tiếp với nhau, trong đó $A'$ và $B'$ theo thứ tự là hai thành phố gần với $A$ và $B$ nhất nếu đi từ $A$ đến $A'$ và $B$ đến $B'$ trên bờ hồ dọc theo cùng một chiều (cùng chiều kim đồng hồ hoặc ngược chiều kim đồng hồ). Chứng tỏ rằng: từ mỗi thành phố đều có thể đi bằng đường thủy đến một thành phố tùy ý khác nhau theo một lộ trình qua không quá hai thành phố trung gian.

[buiminhhieu]

Trên bờ một biển hồ hình tròn có $2n$ thành phố $(n \geq 2)$. Giữa hai thành phố tùy ý có thể có hoặc không có đường thủy nối trực tiếp với nhau. Người ta nhận thấy rằng đối với $2$ thành phố $A$ và $B$ bất kì thì giữa chúng có đường thủy nối trực tiếp với nhau khi và chỉ khi giữa các thành phố $A$' và $B'$ không có đường thủy nối trực tiếp với nhau, trong đó $A'$ và $B'$ theo thứ tự là hai thành phố gần với $A$ và $B$ nhất nếu đi từ $A$ đến $A'$ và $B$ đến $B'$ trên bờ hồ dọc theo cùng một chiều (cùng chiều kim đồng hồ hoặc ngược chiều kim đồng hồ). Chứng tỏ rằng: từ mỗi thành phố đều có thể đi bằng đường thủy đến một thành phố tùy ý khác nhau theo một lộ trình qua không quá hai thành phố trung gian.

Với 3 thành phố liên tiếp X,Y,Z kể theo chiều nào đó ta có $Y={X}'$ và $Z={Y}'$

Do đó theo giả thiết $(X,Y)=1\Rightarrow ({X}',{Y}')=(Y,Z)=0$

$(X,Y)=0\Rightarrow ({X}',{Y}')=(Y,Z)=1$

trong đó kí hiệu $(X,Y)=1(hay 0)$ chỉ rằng giữa 2 thành phố X  và Y có (không có) đường thủy nối trực tiếp với nhau. Từ đo suy ra có thể biểu diễn 2n thành phố đã cho bởi sơ đồ sau như hình 1 trong đó mũi tên chỉ rõ cặp 2 thành phố kề nhau có đương thủy nối trực tiếp(hình ứng với n=4)

Xét 2 thành phố A,B tùy ý

Nếu (A,B)=1 ta có điều phải chứng minh

Nếu (A,B)=0 ta có 3 trường hợp 

TH1:$(A,{A}')=(B,{B}')=1$(hình 1)

Lúc này vì (A,B)=0 nên ($({A}',{B}')=1$

Ta có đường đi $A\rightarrow {A}'\rightarrow {B}'\rightarrow B$

TH2:$(A,{A}')=1,(B,{B}')=0$ (hình 2)

Nếu B=$B_{1}$ thì 3 thành phố $B_{1},B,{B}'$ liên tiếp

Mà $(B,{B}')=0$ nên $(B_{1},B)=1\Rightarrow (A,B_{1})=1$ thì có đường đi $A\rightarrow B_{1}\rightarrow B$

Nếu $(A,B_{1})=0$ thì $({A}',B)=1\Rightarrow A\rightarrow {A}'\rightarrow B$

TH3:$(A,{A}')=(B,{B}')=0$(hình 3) Giả sử $A=A_{1}$ và $B=B_{1}$ tương tự như trên ta phải có:

$(A,A_{1})=(B,B_{1})=1$ vì (A,B)=0 nên $(A_{1},B_{1})=1\Rightarrow A\rightarrow A_{1}\rightarrow B_{1}\rightarrow B$

Tóm lại trong mọi trường hợp ta có ĐPCM

để em tìm hiểu cách vễ hình rồi em fix