[IMO 2013] Bài 6 - Tổ hợp

[novae]

Cho số nguyên $n \ge 3$. Xét một đường tròn và lấy $n+1$ điểm cách đều nhau trên đường tròn đó. Xét tất cả các cách ghi các số $0,1,\ldots,n$ lên các điểm đã lấy sao cho trong mỗi cách ghi, tại mỗi điểm được ghi một số và mỗi số được ghi đúng một lần. Hai cách ghi được gọi là như nhau nếu cách ghi này có thể nhận được từ cách ghi kia nhờ một phép quay quanh tâm đường tròn. Một cách ghi được gọi là đẹp nếu với bốn số tùy ý $a<b<c<d$ mà $a+d=b+c$, dây cung nối hai điểm được ghi $a$ và $d$ không cắt dây cung nối hai điểm được ghi $b$ và $c$.

Kí hiệu $M$ là số các cách ghi đẹp và kí hiệu $N$ là số các cặp có thứ tự $(x,y)$ các số tự nhiên thỏa mãn đồng thời các điều kiện $x+y \le n$ và $\gcd(x,y)=1$. Chứng minh rằng
$$ M=N+1. $$
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[mathandyou]

Tham khảo ở đây:
[Only registered and activated users can see links. ]

[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[Traum]

Bổ đề: Giả sử có cách đánh số sao cho $a_0 = 0, a_1 = a, a_n = n $ thì ta phải có $(a,n) = 1 $ và $a_k \equiv ka \pmod n $ và cách đánh số đó là duy nhất.

Chứng minh: ta chứng minh bằng quy nạp theo $k $ rằng $a_k\equiv ka \pmod n $.
Ta có $a_1 = a $, nên khẳng định đúng với $k = 1 $. Ta chứng minh với $k + 1 $.
Giả sử $a_{k+1} = x \neq (k+1)a\pmod n $ ta xét các trường hợp sau:

Th1: $x > a $, khi đó ta phải có $x-a $ phải thuộc tập $\{a_1,...,a_k\} $ hay $x - a \equiv la \pmod n $ với $0\le l\le k $, mà $a_{k+1}\neq la \pmod n $ với mọi $0\le l\le k $ nên vô lý.

Th2: $x < a $, khi đó ta có $n-a+x < n $ và dễ thấy vì $(n - a + x + a) = x + n $ nên ta cũng phải có $n-a +x $ xuất hiện trước $x $, hay $n-a+x = la\pmod n $ với $1\le l\le n $, suy ra $x\quiv (l+1)\pmod n $ (mâu thuẫn).

Từ điều trên ta dễ thấy là phải có $(a,n) = 1 $.

Vậy bổ đề được chứng minh.


Trở lại bài toán:

Với mỗi cách đánh số thỏa mãn bài toán đặt $a_0 = 0, a_1 = a, a_n = b $. Giả sử $a < b $ (trường hợp $a > b $ tương tự). Nếu $b = n $ theo bổ đề ta có $(a,n) = 1 $ và với mỗi cặp $(a,n) = 1 $ thì có đúng một cách đánh số thỏa mãn.

Nếu $b < n $, dễ thấy là ta phải có $a + b > n $. Do đã giả sử $b > a $ nên ta có $L = n-b < a $. Ta bỏ đi $L < a $ số $b+1,...n $, khi đó ta thu được cách đánh số thỏa mãn với cặp đỉnh kề $ 0 $ là $a $ và $b $ và max là $b $. Theo bổ đề ta có duy nhất một cách đánh số thỏa mãn với $(a,b) = 1 $ là $0,a \pmod b,2a \pmod b,...,b-a \pmod b, b $. Bây giờ ta chèn lại các số $b+1,...n $ vào cách đánh số này.
Dễ thấy là các số $1,2,..,L $ lần lượt đi liền sau các số $b-a+1,b-a+2,...,b-a+L $ (chú ý là $l\le n-b = L < a $ và hiệu của hai số liền nhau của cách đánh số cho $(a,b) = $1 là $a $ hoặc $a-b $). Đến đây ta phải chèn số $b+l $ vào giữa $b-a+l $ và $l $. Cách chèn này là duy nhất.

Mặt khác có thể chứng minh rằng cách chèn lại các số $b+1,...,n $ sẽ thu được cách đánh số thỏa mãn với $n $ số. (Không khó lắm )

Tổng hợp ta có số cách đánh số thỏa mãn chính bằng số bộ $(a,b) = 1 $ mà $a + b > n, 1\le a,b\le n $. Dễ dàng chứng minh được số này = $1 + \sum\limits_{k=2}^{n} \varphi(k) $. ĐPCM.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]