[owlpenguin]

ข้อ 5 ครับ... วิธีผมออกจะยาวยืดไปหน่อยนะครับ...

Solution

Lemma 1
$\binom{k}{k}+\binom{k+1}{k}+\cdots +\binom{n}{k}=\binom{n+1}{k+1}$
Proof
ในที่นี้จะพิสูจน์เชิงคอมบินาทอริคโดยเทคนิคการเดินตามบล็อก (Block walking)
สมมติให้จุดเริ่มต้นมีพิกัด $(0,0)$ แล้ะสุดสิ้นสุดมีพิกัดเป็น $(n+1,k+1)$ (ช่องซ้ายคือจำนวนช่องที่เดิน ช่องขวาคือตำแหน่งในแกนตั้งโดย $0$ คือตำแหน่งที่ต่ำสุดดังรูป



ดังนั้นวิธีเดินทั้งหมดโดยที่เดินได้แต่ทางขวาและขึ้นข้างบนมีทั้งหมด $\binom{n+1}{k+1}$ วิธี
คิดอีกทางหนึ่งโดยให้เดินถึงช่อง $(m,k)$ เมื่อ $m=k,k+1,\cdots ,n$ แล้วเดินขึ้นไปทางด้านบนแล้วไปที่จุด $(n+1,k+1)$ สำหรับแต่ละ $m=k,k+1,\cdots ,n$ จะพบว่าในแต่ละกรณีมีวิธีเดินต่อจากจุด $(m,k)$ นั้นๆเพียง 1 วิธีเท่านั้นและวิธีเดินจากจุด $(0,0)$ ไปยังจุด $(m,k)$ มี $\binom{m}{k}$
ดังนั้นจำนวนวิธีในการเดินจากจุด $(0,0)$ ไปยังจุด $(n+1,k+1)$ เท่ากับ
$\binom{k}{k}+\binom{k+1}{k}+\cdots +\binom{n}{k}$

ดังนั้น $\binom{k}{k}+\binom{k+1}{k}+\cdots +\binom{n}{k}=\binom{n+1}{k+1}$ ตามต้องการ

Lemma 2
$\binom{n}{0}^2+\binom{n}{1}^2+\cdots +\binom{n}{n}^2=\binom{2n}{n}$
Proof
พิจารณา $(1+x)^n(1+\frac{1}{x})^n$
$=\frac{1}{x^n}(1+x)^{2n}=\frac{1}{x^n}\left(\binom{2n}{0}+\binom{2n}{1}x+\cdots +\binom{2n}{n}x^n+\cdots +\binom{2n}{2n}x^2n\right)$
สังเกตว่า สัมประสิทธิ์ของพจน์ค่าคงที่คือ $\binom{2n}{n}$
พิจารณา $(1+x)^n(1+\frac{1}{x})^n$ อีกแบบหนึ่งดังนี้
$=\left(\binom{n}{0}+\binom{n}{1}x+\cdots +\binom{n}{n}x^n\right)\left(\binom{n}{0}+\binom{n}{1}\frac{1}{x}+\cdots +\binom{n}{n}\frac{1}{x^n}\right)$
สัมประสิทธิ์ของพจน์ค่าคงที่คือ $\binom{n}{0}^2+\binom{n}{1}^2+\cdots +\binom{n}{n}^2$

$\therefore\binom{n}{0}^2+\binom{n}{1}^2+\cdots +\binom{n}{n}^2=\binom{2n}{n}$ ตามต้องการ

Solution:
พิจารณา $\frac{1}{2551} \bigg (\sum_{A \subset M ; n(A)= k} \min A \, \bigg)$
$\min A$ จะเท่ากับ $1$ เมื่อสมาชิกอื่นในเซต $A$ มีค่ามากกว่า $1$
เนื่องจาก $n(A)=k$ ดังนั้นมีวิธีสร้างเซตที่มี $\min A=$ ได้ทั้งหมด $\binom{2549}{k-1}$ วิธี (เพราะว่าสามารถเลือก $k-1$ สมาชิกที่เหลือได้จากเลข $2,3,\cdots ,2549,2550$ ซึ่งมีทั้งหมด $2549$ จำนวน)
$\min A$ จะเท่ากับ $2$ เมื่อสมาชิกอื่นในเซต $A$ มีค่ามากกว่า $2$
เนื่องจาก $n(A)=k$ ดังนั้นมีวิธีสร้างเซตที่มี $\min A=$ ได้ทั้งหมด $\binom{2548}{k-1}$ วิธี (เพราะว่าสามารถเลือก $k-1$ สมาชิกที่เหลือได้จากเลข $3,4,\cdots ,2549,2550$ ซึ่งมีทั้งหมด $2548$ จำนวน)
พิจารณาในทำนองเดียวกันจนกระทั่งถึงเมื่อ $\min A=2550-k+1$ (เพราะว่าถ้า $\min A>2550-k+1$ แล้ว $n(A)<k$ ซึ่งขัดแย้งกับที่ว่า $n(A)=k$)
จะได้ว่า $\frac{1}{2551} \bigg (\sum_{A \subset M ; n(A)= k} \min A \, \bigg)=\frac{1}{2551}\left(1\binom{2549}{k-1}+2\binom{2548}{k-1}+\cdots +(2550-k+1)\binom{k-1}{k-1}\right)$

พิจารณา $\frac{1}{2551} \bigg (\sum_{A \subset M ; n(A)= k} \max A \, \bigg)$
$\max A$ จะเท่ากับ $2550$ เมื่อสมาชิกอื่นในเซต $A$ มีค่าน้อยกว่า $2550$
เนื่องจาก $n(A)=k$ ดังนั้นมีวิธีสร้างเซตที่มี $\max A=$ ได้ทั้งหมด $\binom{2549}{k-1}$ วิธี (เพราะว่าสามารถเลือก $k-1$ สมาชิกที่เหลือได้จากเลข $1,2,\cdots ,2548,2549$ ซึ่งมีทั้งหมด $2549$ จำนวน)
$\min A$ จะเท่ากับ $2549$ เมื่อสมาชิกอื่นในเซต $A$ มีค่าน้อยกว่า $2549$
เนื่องจาก $n(A)=k$ ดังนั้นมีวิธีสร้างเซตที่มี $\max A=$ ได้ทั้งหมด $\binom{2548}{k-1}$ วิธี (เพราะว่าสามารถเลือก $k-1$ สมาชิกที่เหลือได้จากเลข $1,2,\cdots ,2547,2548$ ซึ่งมีทั้งหมด $2548$ จำนวน)
พิจารณาในทำนองเดียวกันจนกระทั่งถึงเมื่อ $\max A=k$ (เพราะว่าถ้า $\max A<k$ แล้ว $n(A)<k$ ซึ่งขัดแย้งกับที่ว่า $n(A)=k$)
จะได้ว่า $\frac{1}{2551} \bigg (\sum_{A \subset M ; n(A)= k} \max A \, \bigg)=\frac{1}{2551}\left(2550\binom{2549}{k-1}+2549\binom{2548}{k-1}+\cdots +k\binom{k-1}{k-1}\right)$

$\therefore x_k = \frac{1}{2551} \bigg (\sum_{A \subset M ; n(A)= k} (\min A + \max A) \, \bigg)$
$=\frac{1}{2551}\left(1\binom{2549}{k-1}+2\binom{2548}{k-1}+\cdots +(2550-k+1)\binom{k-1}{k-1}\right)+\frac{1}{2551}\left(2550\binom{2549}{k-1}+2549\binom{2548}{k-1}+\cdots +k\binom{k-1}{k-1}\right)$
$=\frac{1}{2551}\left((1+2550)\binom{2549}{k-1}+(2+2549)\binom{2548}{k-1}+\cdots +(2550-k+1+k)\binom{k-1}{k-1}\right)$
$=\frac{2551}{2551}\left(\binom{2549}{k-1}+\binom{2548}{k-1}+\cdots +\binom{k-1}{k-1}\right)$
จาก Lemma 1 ได้ว่า
$\therefore x_k=\binom{2550}{k}$

$\therefore\sum_{i=1}^{2549} x_i^2=\sum_{i=1}^{2549}\binom{2550}{k}^2$
$=\left(\sum_{i=0}^{2550}\binom{2550}{k}^2\right)-\binom{2550}{0}^2-\binom{2550}{2550}^2$
จาก Lemma 2 ได้ว่า
$=\binom{5100}{2550}-2=\frac{5100!}{(2550!)^2}-2$
เนื่องจาก $2551$ เป็นจำนวนเฉพาะ
จาก $2551|5100!$ และ $2551\not|(2550!)^2$ ดังนั้น $2551|\frac{5100!}{(2550!)^2}$
$\therefore\sum_{i=1}^{2549} x_i^2\equiv -2\equiv 2549\pmod{2551}$
ดังนั้น เศษจากการหาร $\therefore\sum_{i=1}^{2549} x_i^2$ ด้วย $2551$ เท่ากับ $2549$

ผมคิดว่าน่าจะแยกโจทย์ของแต่ละระดับเป็นกระทู้ๆไปจะดีกว่านะครับ เพราะว่าถ้าเอามารวมกัน เดี๋ยวเวลาเฉลยของคนละระดับกันแล้วมันอาจจะมีการงงเกิดขึ้นได้นะครับ