Đến nội dung


Chú ý

Nếu các bạn đăng kí thành viên mà không nhận được email kích hoạt thì hãy kiểm tra thùng thư rác (spam). Nếu không biết cách truy cập vào thùng thư rác thì các bạn chịu khó Google hoặc đăng câu hỏi vào mục Hướng dẫn - Trợ giúp để thành viên khác có thể hỗ trợ.


Hình ảnh

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


  • Please log in to reply
Chủ đề này có 1 trả lời

#1 marsu

marsu

    Sĩ quan

  • Thành viên
  • 327 Bài viết
  • Giới tính:Nam
  • Đến từ:TP.HCM

Đã gửi 19-02-2006 - 09:06

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.



#2 buiminhhieu

buiminhhieu

    Thượng úy

  • Thành viên
  • 1150 Bài viết
  • Giới tính:Nam
  • Sở thích:Inequality

Đã gửi 06-12-2013 - 21:24

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


%%- Chuyên Vĩnh Phúc

6cool_what.gif





1 người đang xem chủ đề

0 thành viên, 1 khách, 0 thành viên ẩn danh