Đến nội dung

Hình ảnh

RMO1995;problem 8

- - - - -

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

#1
lvd

lvd

    Hạ sĩ

  • Thành viên
  • 72 Bài viết
Trong bản đồ của một thị trấn mỗi đường phố được coi là cạnh của một đường gấp khúc;hai phố khác nhau không cắt nhau ở điểm trong mỗi cạnh.Mỗi phố được tô một trong 3 màu:trắng đỏ hoặc xanh.Mỗi phố nỗi 2 ngã ba và tại mỗi ngã ba có đúng ba phố gặp nhau và chúng tô bởi ba màu phân biệt.Ngã ba được gọi là dương nếu tại đó quay ngược chiều kim đồng hồ các phố sẽ xuất hiện theo thứ tự:trắng,xanh,đỏ.Ngã ba được gọi là âm trong trường hợp ngược lại.Chứng minh rằng hiệu của số ngã ba dương và âm là chia hết cho 4
:”...và đột nhiên ,hoàn toàn bất ngờ,tôi đã có được sự phát hiện huyền diệu đó...Nó đẹp đến mức không sao mô tả nổi ,mà lại đơn giản và tao nhã nữa..."
andrews wiles

#2
poset

poset

    Trung sĩ

  • ĐHV Toán Cao cấp
  • 125 Bài viết

Trong bản đồ của một thị trấn mỗi đường phố được coi là cạnh của một đường gấp khúc;hai phố khác nhau không cắt nhau ở điểm trong mỗi cạnh.Mỗi phố được tô một trong 3 màu:trắng đỏ hoặc xanh.Mỗi phố nỗi 2 ngã ba và tại mỗi ngã ba có đúng ba phố gặp nhau và chúng tô bởi ba màu phân biệt.Ngã ba được gọi là dương nếu tại đó quay ngược chiều kim đồng hồ các phố sẽ xuất hiện theo thứ tự:trắng,xanh,đỏ.Ngã ba được gọi là âm trong trường hợp ngược lại.Chứng minh rằng hiệu của số ngã ba dương và âm là chia hết cho 4

Coi bản đồ là một đồ thị phẳng bậc $3$ đều trên mặt phẳng, các đường phố là các cạnh. Có thể giả sử đồ thị liên thông vì hiệu ta cần xét bằng tổng các hiệu của các thành phần liên thông, nên ta chỉ cần xét các thành phần liên thông.
Giả sử thị trưởng muốn làm thành phố của mình đồng đều, tức tất cả các ngã ba đều dương (hoặc âm). Giả sử thành phố chưa đồng đều, vì đồ thị liên thông nên sẽ có hai ngã ba một âm một dương được nối với nhau. Ta có $3$ trường hợp, và sẽ xử lý như hình dưới đây:
Ta có số ngã ba sẽ giảm đi $2$, nên quá trình này sẽ dừng lại cho đến khi thành phố đồng đều. Ta có hiệu của số ngã ba dương và âm không đổi trong quá trình này, nên ta chỉ cần chứng minh số ngã ba của thành phố đồng đều chia hết cho $4$.
Giả sử thị trưởng muốn đập đi sửa lại hết các đường sơn trắng, đồ thị sau khi xóa hết các cạnh trắng sẽ là đồ thị phẳng bậc $2$ đều, nên nó sẽ gồm các đồ thị cyclic rời nhau trên mặt phẳng, gọi chúng là các vòng. Mỗi vòng sẽ gồm các cạnh xanh đỏ nối tiếp nhau. Ta sẽ định hướng cho các vòng như sau:
-Xét các vòng không nằm trong các vòng nào cả, cho chúng định hướng theo chiều kim đồng hồ.
-Xét các vòng chưa được định hướng không nằm trong các vòng chưa được định hướng nào cả, cho chúng định hướng ngược chiều kim đồng hồ.
-Xét các vòng chưa được định hướng không nằm trong các vòng chưa được định hướng nào cả, cho chúng định hướng theo chiều kim đồng hồ.
-Tiếp tục làm vậy xen kẽ.
Giờ cho xe đi theo các vòng theo chiều được định hướng của nó. Gọi một ngã ba là XĐ nếu khi ta đi qua ngã ba đó ta đi từ đường xanh tới đường đỏ, và ĐX nếu ngược lại. Dễ thấy số ngã ba XĐ bằng số ngã ba ĐX, do đó số ngã ba của thành phố gấp đôi số ngã ba XĐ.
Giờ ta muốn xây lại, chú ý thành phố cần đồng đều và các đường không được cắt nhau nên ta nhận thấy ta phải xây các đường màu trắng nối hai các ngã ba cùng loại tức ĐX nối với ĐX, XĐ nối với XĐ, để xây được vậy thì số ngã ba XĐ phải là số chẵn, do vậy số ngã ba của thành phố phải chia hết cho $4$.
Từ đó ta có đpcm.

Hình gửi kèm

  • math.png

Bài viết đã được chỉnh sửa nội dung bởi poset: 10-11-2021 - 13:32





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

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