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

[thinhnarutop]

cho n điểm xanh và n điểm đỏ trên mặt phẳng, trong đó không có 3 điểm nào thẳng hàng. Chứng minh rằng ta có thể nối 2n điểm này bằng n đoạn có đầu mút khác màu sao cho chúng đôi một không giao nhau.

[wanderboy]

Trường hợp n=2 mà 2 cái đoạn đó cắt nhau là sai rồi bạn

// xin lỗi bạn mình đọc sai đề bài

Bài viết đã được chỉnh sửa nội dung bởi wanderboy: 02-11-2016 - 01:30

[thinhnarutop]

nh

 

Trường hợp n=2 mà 2 cái đoạn đó cắt nhau là sai rồi bạn

theo mình nghĩ đó mới chỉ là một cách nối thôi còn cách nối khác không cắt mà bạn

[thinhrost1]

cho n điểm xanh và n điểm đỏ trên mặt phẳng, trong đó không có 3 điểm nào thẳng hàng. Chứng minh rằng ta có thể nối 2n điểm này bằng n đoạn có đầu mút khác màu sao cho chúng đôi một không giao nhau.

Ứng với mỗi cách nối các cặp điểm xanh, đỏ với nhau ta cho tương ứng với một số, số đó là tổng độ dài n đoạn thẳng vừa nối. Rõ ràng số cách này là hữu hạn. Gọi $\mu _i$ là cách nối thứ i, và tương ứng với nó là số $l_i$.

 

Xét tập hợp A={$l_i$ | i=1,2,..k} ở đây k là số tất cả các nối. Theo nguyên lí cực hạn tồn tại:

 

l*=min $l_i$ $( 1 \le i \le k)$

 

Ứng với độ dài l* tta có cách nối $\mu _j$  (giả sử $l*=l_j$). Ta chứng minh rằng cách nối $\mu _j$  thỏa mãn mọi yêu cầu đề bài.

 

Điều kiện thứ nhất mặc nhiên thỏa mãn.

 

Giả thiết phản chứng điều kiện thứ hai không thỏa mãn, tức là trong các nối $\mu _j$  có hai đoạn nào đó cắt nhau. Không giảm tổng quát có thể cho là $A_1B_1 $cắt $A_2B_2$ ( Lưu ý rằng ta kí hiệu $A_1, ..A_n$ là các điểm đỏ, còn $B_1, .. B_n$ là cách điểm xanh.) GIả sử $A_1B_1 \cap A_2B_2= O.$ Trong cách nôi $\mu _j$ ta giữ nguyên n-2 cách nối, còn $A_1B_1$ thay bằng $A_1B_2$. Rõ ràng đây là cũng là một trong các cách nối điểm đỏ với xanh. Gọi $\overline{l}$ là tổng độ dài trong cách nói này. Khi đó ta có:

 

$\overline{l}=l*-(A_1B_1+A_2B_2)+A_1B_2+A_2B_1 (1)$

Do $A_1B_2+A_2B_1= (A_1O+OB_2)+(A_2O+OB_1) >A_1B_2+A_2B_2 $

 

Thay vào (1) ta có: $\overline{l} <l^* (2)$

 

Bất đẳng thức (2) là điều vô lí, vì $\overline{l}$ cũng là một phần tử của A, nên theo định nghĩa $l^*$ ta phải có $ \overline{l} \le l^*$. Như vậy giả thiết phản chứng là sai, tức là cách nối $\mu _j$ thỏa mãn điều kiện thứ hai, và đó chính là đpcm