Nguyễn Hoàng Dũng đã viết:
Đây là cách giải kiểu Tin hả, anh sẽ suy nghĩ về hướng này sau. :x
Có một lời giải khác cho bài này khá gọn, nhờ một nhận xét đơn giản : một tour du lịch bắt đầu và kết thúc ở cùng một vùng, đi qua có thể một số các vùng khác, luôn phải vượt biên một số chẵn lần.
Em Sơn thử chứng minh rằng nhận xét trên và tính chất "tô được bằng 2 màu" là một xem !!! Nếu dễ quá thì chứng minh luôn nhận xét đó luôn ( tất nhiên là không dựa vào tính chất "tô được bằng 2 màu"
) )
A=nhận xét của anh
B=tính chất "tô được bẳng 2 màu"
1. CM Nếu B thì A:
mặt phẳng đã được tô bẳng 2 màu thỏa mãn tính chất B. Suy ra, tour du lịch khi vượt biên phải đi từ 1 vùng sang 1 vùng khác có màu khác. Suy ra, tour du lịch muốn đi từ 1 vùng màu vàng sang 1 vùng màu vàng khác sẽ phải vượt biên 1 số chẵn lần (chuyển màu chẵn lần). Suy ra A.
2. CM Nếu A thì B:
Với mặt phẳng được chia bởi các đường thẳng như vậy, ta luôn tìm được đường đi qua tất cả các vùng và trở về nơi xuất phát (đi qua 1 vùng nào đó nhiều hơn 1 lần cũng được). Gọi nó là con đường X (cho nó có vẻ toán học). Tô vùng xuất phát màu vàng, vùng kế tiếp màu tím, rồi vàng, rồi tím... Cứ như vậy vừa đi vừa tô, ta sẽ tô được tất cả các vùng.
Lấy 2 vùng có cùng màu bất kì V1 và V2. Giả sử 2 vùng này cạnh nhau. Theo con đường X ở trên, ta sẽ tìm được 1 con đường từ V1 đến V2 là một phần của X. Theo tính chất đường X, con đường từ V1 đến V2 phải vượt biên chẵn lần (vì V1, V2 cùng màu). Nhưng từ V2, ta nhảy sang V1, vượt biên thêm 1 lần nữa để về V1. Suy ra tồn tại đường từ V1 loanh quanh 1 lúc về V1 nhưng vượt biên 1 số lẻ lần, suy ra vô lý (vì A). Suy ra V1 và V2 không ở cạnh nhau. Suy ra 1 vùng chỉ có thể giáp giới với 1 vùng khác màu. Suy ra B.
Đấy, nếu A thì B, nếu B thì A, suy ra A và B là một. (Chứng minh đầy đủ dài quá, ặc)
Còn chứng minh nhận xét A của anh thế nào thì em chưa biết. đi ngủ đã em sẽ trả lời sau.
