Math Labs

Bài 6

Cho n≥2n\ge2 là số nguyên, xét một đường tròn với n+1n+1 điểm cách đều nhau được đánh dấu trên đó. Xét tất cả các cách đánh số các điểm này bằng 0,1,…,n0,1,\ldots,n sao cho mỗi số được dùng đúng một lần; hai cách đánh số được coi là giống nhau nếu cách này có được từ cách kia bằng một phép quay đường tròn. Một cách đánh số được gọi là đẹp nếu, với bất kỳ bốn số a<b<c<da<b<c<d mà a+d=b+ca+d=b+c, dây cung nối hai điểm mang số aa và dd không cắt dây cung nối hai điểm mang số bb và cc. Gọi MM là số cách đánh số đẹp, và NN là số cặp số nguyên dương (x,y)(x,y) sao cho x+y≤nx+y\le n và gcd⁡(x,y)=1\gcd(x,y)=1. Chứng minh rằng M=N+1M=N+1.
Bước 1 trên 5: Phân loại vòng đẹp thành tuyến tính hoặc phi tuyến
Bước trướcBước tiếp
Hiểu nôm na

Phép quy nạp chỉ phụ thuộc vào vị trí nhãn lớn nhất có thể chèn sau khi xóa nó.

A ring is linear if its labels form an arithmetic progression modulo n+1\text{A ring is linear if its labels form an arithmetic progression modulo }n+1
Phân tích chi tiết

Gọi một cách đánh số các điểm cách đều là một vòng, và gọi là tuyến tính nếu các nhãn quanh đường tròn lập thành cấp số cộng modulo n+1n+1. Xóa điểm mang nhãn n để được một vòng trên {0,…,n−1}\{0,\ldots,n-1\}. Ta sẽ chứng minh mọi vòng phi tuyến có đúng một mở rộng đẹp bằng n, còn mọi vòng tuyến tính có đúng hai.