XÉT HỆ TẤT CẢ CÁC ĐƯỜNG GẤP KHÚC KHÉP KÍN GỒM CÓ AJ+1AIN KHÚC...
Bài 17.
Xét hệ tất cả các đường gấp khúc khép kín gồm có
A
j+1
A
i
n khúc với n đỉnh chính là n điểm đã cho. Vì số
đường gấp khúc là hữu hạn nên tồn tại một đường
A
j
có tổng độ dài bé nhất. Gọi đường gấp khúc có
A
i+1
tổng độ dài bé nhất là
A A ...A A
1
2
n
1
. Khi đó nó
chính là một đường gấp khúc cần tìm và không có
hai cạnh nào của đường cắt nhau.
Thật vậy, ta giả sử hai cạnh của đường gấp khúc cắt nhau tại O là
A A
i
i 1
+
và
A A
j
j 1
+
.
Từ đó ta có
A A
i
i 1
+
+
A A
j
j 1
+
>
A A A A . Theo bất đẳng thức tam giác thì đường gấp
i
j
+
i 1
+
j 1
+
CH
UY
ÊN
Đ
Ề
S
Ố
H
Ọ
C
khúc nhày khép kín và
A A ...A A A ...A A A ...A A
1
2
i
j
j 1
−
i 1
+
j 1
+
j 2
+
n
1
có tổng đội dài ngắn hơn
đường gấp khúc đã chọn. Điều này mâu thuẫn. Do đó bài toán được chứng minh.