Math Labs

Bài 6

Cho n≥2n\ge2 đoạn thẳng trong mặt phẳng sao cho hai đoạn thẳng bất kỳ đều cắt nhau, và không có ba đoạn thẳng nào đồng quy tại một điểm. Geoff phải chọn một đầu mút của mỗi đoạn thẳng và đặt một con ếch lên đó, hướng về đầu mút còn lại. Sau đó anh ta sẽ vỗ tay n−1n-1 lần; mỗi lần vỗ tay, mọi con ếch lập tức nhảy tới điểm giao tiếp theo trên đoạn thẳng của nó (các con ếch không bao giờ đổi hướng nhảy). Geoff muốn đặt các con ếch sao cho không có hai con nào từng chiếm cùng một điểm giao tại cùng một thời điểm. (a) Chứng minh rằng Geoff luôn có thể thực hiện được mong muốn của mình nếu nn lẻ. (b) Chứng minh rằng Geoff không bao giờ có thể thực hiện được mong muốn của mình nếu nn chẵn.
Bước 1 trên 4: Bao quanh cấu hình và đánh số lại
Hiểu nôm na

Việc chiếu các đầu mút của mỗi đoạn thẳng ra ngoài lên một đường tròn bao quanh lớn giữ được thứ tự vòng tròn mà không thay đổi việc đoạn nào cắt đoạn nào.

ω⊃{all (n2) intersection points},P1,…,P2n in clockwise order\omega\supset\{\text{all }\tbinom n2\text{ intersection points}\},\qquad P_1,\dots,P_{2n}\ \text{in clockwise order}
Phân tích chi tiết

Lấy một đường tròn ω\omega đủ lớn để chứa tất cả (n2)\binom n2 điểm giao của nn đoạn thẳng trong phần trong của nó, và kéo dài mỗi đoạn thẳng ra ngoài theo cả hai hướng cho tới khi gặp ω\omega; đánh số lại 2n2n điểm thu được trên ω\omega là P1,P2,…,P2nP_1,P_2,\dots,P_{2n} theo chiều kim đồng hồ. Vì hai đoạn thẳng bất kỳ trong số các đoạn thẳng ban đầu đều cắt nhau, và các đầu mút của những dây cung không cắt nhau của ω\omega sẽ không bao giờ cắt nhau bên trong, nên mỗi đoạn trong số nn đoạn thẳng thực chất phải nối một điểm PiP_i với điểm Pi+nP_{i+n} đối diện chính xác với nó trong cách đánh số vòng tròn này (chỉ số lấy theo mô-đun 2n2n): nếu một đoạn thẳng nối PiP_i với PjP_j mà j−i≠n(mod2n)j-i\ne n\pmod{2n}, thì dây cung của nó sẽ không cắt dây cung nối một cặp khác nào đó, mâu thuẫn với việc hai đoạn thẳng bất kỳ đều cắt nhau.