|
|
|
Ngoài một số quy định đã được nêu trong phần Quy định của Ghi Danh , mọi người tranh thủ bỏ ra 5 phút để đọc thêm một số Quy định sau để khỏi bị treo nick ở MathScope nhé ! * Quy định về việc viết bài trong diễn đàn MathScope * Nếu bạn muốn gia nhập đội ngũ BQT thì vui lòng tham gia tại đây |
| Ðiều Chỉnh | Xếp Bài |
24-07-2013, 11:19 PM | #1 |
+Thành Viên Danh Dự+ Tham gia ngày: Jul 2010 Đến từ: Event horizon Bài gởi: 2,453 Thanks: 53 Thanked 3,057 Times in 1,288 Posts | [IMO 2013] Bài 6 - Tổ hợp 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. $$ __________________ M. thay đổi nội dung bởi: novae, 25-07-2013 lúc 02:08 AM |
The Following User Says Thank You to novae For This Useful Post: | hieu1411997 (26-07-2013) |
25-07-2013, 08:17 PM | #2 |
Moderator Tham gia ngày: Dec 2012 Đến từ: HCMUS Bài gởi: 557 Thanks: 259 Thanked 402 Times in 216 Posts | |
The Following User Says Thank You to mathandyou For This Useful Post: | hoangqnvip (25-07-2013) |
26-07-2013, 04:19 AM | #3 |
Moderator Tham gia ngày: Nov 2007 Đến từ: cyber world Bài gởi: 413 Thanks: 14 Thanked 466 Times in 171 Posts | 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. __________________ Traum is giấc mơ. thay đổi nội dung bởi: Traum, 26-07-2013 lúc 04:34 AM |
The Following 8 Users Say Thank You to Traum For This Useful Post: | 5434 (26-07-2013), hieu1411997 (26-07-2013), Highschoolmath (26-07-2013), hoangnam94 (26-07-2013), hoangqnvip (26-07-2013), pco (26-07-2013), quocbaoct10 (26-07-2013), trungthu10t (26-07-2013) |
Bookmarks |
|
|