MathLabs

Bài 5

Có nn đoạn thẳng trên mặt phẳng, không có ba đoạn nào đồng quy, và mỗi cặp cắt nhau đúng một lần tại phần trong của mỗi đoạn. Tony và 2n−12n-1 người bạn đứng tại các đầu mút phân biệt của các đoạn thẳng. Tony muốn gửi quà Giáng sinh cho các bạn như sau: Trước hết, cậu chọn một đầu mút của mỗi đoạn làm "đích". Sau đó cậu đặt món quà tại đầu mút nơi mình đang đứng. Món quà di chuyển như sau: khi đang ở trên một đoạn thẳng, nó đi về phía đích của đoạn đó; khi tới giao điểm của hai đoạn thẳng, nó đổi sang đoạn thẳng kia và đi về phía đích mới. Nếu món quà tới được một đầu mút, người bạn đứng ở đầu mút đó nhận được quà. Chứng minh rằng Tony có thể gửi quà tới đúng nn người trong số 2n−12n-1 người bạn.
Bước 1 trên 3: Mô hình dây cung và ghép cặp đỉnh đối diện
Vertices 1,…,2n on a circle (Tony at 1);each chord connects k and k+n(mod2n)\text{Vertices }1,\ldots,2n\text{ on a circle (Tony at }1\text{)};\quad\text{each chord connects }k\text{ and }k+n\pmod{2n}
Phân tích chi tiết

Bao mọi (n2)\binom{n}{2} giao điểm trong bằng một đường tròn lớn, kéo dài nn đoạn thẳng thành các dây cung của đường tròn này, và đánh số 2n2n đầu mút dây cung là 1,2,…,2n1,2,\ldots,2n ngược chiều kim đồng hồ bắt đầu từ Tony tại 11. Vì hai dây bất kỳ đều cắt nhau trong đường tròn, mỗi dây có n−1n-1 đầu mút ở mỗi phía, nên nối kk với k+nk+n với 1≤k≤n1\le k\le n.