[กขฃคฅฆง]

ข้อความเดิมเขียนโดยคุณ Thgx0312555

4. ในงานเลี้ยงปีใหม่มีผู้เข้าร่วม $n+1$ คน (หมายเลขตั้งแต่ $1,2,3,...,n+1$ ) กำลังแลกของขวัญ ถ้าไม่มีใครให้ของขวัญคนเดียวกัน และคนหมายเลข $i$ ให้ของขวัญกับคนหมายเลข $x_i$ และเราทราบว่าคนที่หมายเลข $n+1$ ให้ของขวัญกับคนที่หมายเลข $1$, หลังจากแลกของขวัญเสร็จคนที่ $i$ จะได้แต้มเท่ากับ $x_i-i$ จงพิสูจน์ว่าสำหรับ $r \in \mathbb{Z}$, $1 \le r \le n$ จะสามารถเลือกคน $r$ คนซึ่งมีแต้มรวมอย่างน้อย $r$

solution

ให้ $y_1,y_2,...,y_{\binom{n}{r} }$ คือผลรวมของ $r$ คน ทั้ง $\binom{n}{r} $ แบบ (ไม่รวมหมายเลข $n+1$) จะได้

$y_1+y_2+...+y_{\binom{n}{r} } = \binom{n-1}{r-1} (x_1+...+x_n-(1+2+...+n)) = n\binom{n-1}{r-1} = r\binom{n}{r} $

จะได้ว่ามี $y_i \geqslant r$