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

[QUANVU]

Cho $M$ là tập tất cả các điểm có tọa độ nguyên trong mặt phẳng.Với mỗi $(x-1,y),(x+1,y),(x,y-1),(x,y+1)$ được gọi là kề với $P$.$S$ là tập con hữu hạn khác rỗng của $M$,một song ánh $f:\mathbb{S} \to \mathbb{S}$ được gọi là hoàn hảo nếu $f(P)$ kề với $P$.CM :$g:\mathbb{S} \to \mathbb{S}$ với tính chất $g(g(P))=P \quad \forall P\in S.$ là song ánh hoàn hảo.

Bài viết đã được chỉnh sửa nội dung bởi dark templar: 16-03-2013 - 12:29

[salida]

Một khi hàm f hoàn hảo như vậy tồn tại từ một tập hữu hạn S vào chính S, ta có thể suy ra rằng, với mỗi điểm P_1 bất kỳ, tồn tại một dãy hữu hạn P_1,...,P_k sao cho:
f(P_1) = P_2
...
f(P_k-1) = P_k
f(P_k) = P_0
với P_1 kề P_2, P_2 kề P_3,... P_k kề P_1
Tức là nếu ta nối P_1, P_2, ... , P_k ,P_1 ta được một đường khép kín trên giá các đường thằng tọa độ nguyên, bắt đầu từ P_1 và kết thúc tạo P_1. Rõ ràng: k phải chẵn, vì giả sử mình qua trái bao nhiêu nấc thì lại qua phải bấy nhiêu, lên bao nhiêu thì phải xuống bấy nhiêu thì mới về lại chỗ cũ được.
Từ đó mình có thể định nghĩa một hàm g bằng cách "chia cặp" các điểm trên như sau:
g(P_1) = P_2 và g(P_2) = P_1
g(P_3) = P_4 và g(P_4) = P_3
...
g(P_k-1) = P_k và g(P_k) = P_k-1

Với mỗi một điểm P bất kỳ của S đều phải thuộc một đường khép kín như trên, và dễ thấy các đường này không giao nhau (vì f là hàm song ánh, mỗi điểm chỉ có 1 ảnh và chỉ có một nghịch ành).
Do đó mọi điểm của S đều được định nghĩa theo g. Dễ kiểm tra là g là song ánh từ S vào S, hơn nửa ảnh của P vào g là kề với P --> g hòan hảo