ปัญหาชิงรางวัลข้อที่ 21: Combinatorial Problem
 

ให้ $n$ เป็นจำนวนนับ และ $m$ เป็นค่าคงที่ที่เป็นจำนวนเต็ม โดยที่ $ m \ge n(n+1)/2 $

ถามว่าสมการ $$ x_1 + x_2 + \dots + x_n = m $$ เมื่อ $ x_1, x_2, \dots , x_n $ เป็นจำนวนเต็ม และ $ x_1 \ge 1, x_2 \ge 2, \dots , x_n \ge n $ จะมีจำนวนคำตอบทั้งหมดกี่คำตอบ

n คำตอบ คับ โดยที่ n เป็นจำนวนนับ

$\displaystyle{ {m-{n \choose 2}+n-1 \choose m-{n \choose 2}} }$ :confused:

$\displaystyle{\left({m-{{n+1} \choose 2}+n-1} \choose {m-{{n+1} \choose 2}}\right)}$ได้ไม่เท่าคุณnooonuiiอะครับ :confused:

ผมคิดอย่างนี้ไม่รู้ถูกปะ ถ้า x1=1 x2=2 ไปเรื่อยๆ เราจะได้ว่า x1+x2+x...+xn = n*n+1/2 ดังนั้น จาก
m = x1+x2+x...+xn = n*n+1/2 แต่เงือนไขคือเมื่อ x1,x2,...,xn เป็นจำนวนเต็ม และ x1≥1,x2≥2,...,xn≥n ดังนั้น m≥n*n+1/2 จะเห็นว่ามีคำตอบมากมายเหลือคณา แต่จำนวนคำตอบต้องเป็นบวกดังนั้นผมจึงให้มันเท่ากับ จำนวนของจำนวนนับทั้งหมด

ผิดจริงด้วยครับ คิดเลขผิด :blood: ไม่ค่อยถูกโฉลกกับโจทย์ combinatorics เลย :cry:

ต้องแสดงวิธีทำด้วยนะครับ

ให้$y_i=x_i-i$
แล้ว$x_1+x_2+\cdots+x_n=m\equiv y_1+y_2+\cdots+y_n=m-{{n+1}\choose2}$โดยที่$y_i\ge0$
ซึ่งจำนวนคำตอบของสมการอันหลังก็หาได้เท่ากับที่พิมพ์ไว้ที่ความเห็นก่อนหน้าครับ :D

ตรงนี้ช่วยอธิบายเพิ่มเติมได้ไหมครับ ว่าจะหาจำนวนคำตอบของสมการ (ไม่ใช่อสมการ) นี้ได้อย่างไร เชื่อว่ายังมีอีกหลายๆคนที่อยากทราบ

สำหรับจำนวนวิธีของคำตอบที่แตกต่างกันสมการข้างต้นนะครับจะเห็นว่า
มีค่าเท่ากับจำนวนวิธีของการใส่บอล$m-{{n+1}\choose2}$ลูกลงในกล่องที่ต่างกัน$n$กล่อง
เพราะว่าในแต่ละกล่องเราสามารถใส่บอลได้ตั้งแต่0ลูกจนถึง$m-{{n+1}\choose2}$เป็นอย่างมาก
มาถึงตรงนี้เราก็สามารถใช้หลักstars and barsได้ละนะครับคือให้ | เป็นตัวคั่นระหว่างกล่อง
และให้บอลแทน * จะได้ว่ามี | อยู่ n-1 ตัวและมี * อยู่ $m-{{n+1}\choose2}$ ตัว
เมื่อเราหาวิธีเรียงสับเปลี่ยนของของเหล่านี้ก็จะได้คำตอบเหมือนที่ตอบไว้ครับ :D

ขอบคุณครับสำหรับคำอธิบาย ผมก็ทำคล้ายๆกันนี้แต่ผมให้ $ y_i = x_i - i + 1 $ แล้วใช้หลัก stars and bars แบบที่ต้องมีของอย่างน้อย 1 ชิ้นในกล่องแต่ละกล่องตามที่คุณ gon เคยอธิบายไว้ ซึ่งผมรู้สึกว่าง่ายกว่าครับ

คำตอบที่ผมคิดได้คือ $$ { m- \frac{n(n-1)}{2} -1 \choose n-1 } \; = \; { m- {n \choose 2} -1 \choose n-1 } $$ ซึ่งก็เท่ากับของน้อง Timestopper_STG ดังนั้นสำหรับข้อนี้น้อง Timestopper_STG รับไป 5 คะแนนเต็มครับ

ป.ล. โจทย์ข้อนี้ผมได้แนวคิดมาจากกระทู้ลูกเต๋าของน้อง Timestopper_STG เองแหละครับ :)